csp坐标变换(其二)

根据引用中的提示，我们可以使用线段树来解决这个问题，时间复杂度为O(n*log(m))。具体步骤如下：

1.将所有的操作按照时间顺序排序，同时将所有的坐标离散化，得到一个新的坐标系。

2.建立一棵线段树，每个节点维护一个区间内的点的数量。

3.按照时间顺序依次处理每个操作，如果是修改操作，则在线段树上修改对应的节点；如果是查询操作，则在线段树上查询对应区间内的点的数量。

4.将查询结果转换回原坐标系。

下面是一个Python实现的例子：

class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * (4 * n)
        self.lazy = [0] * (4 * n)

    def push_up(self, node):
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def push_down(self, node, left, right):
        if self.lazy[node]:
            mid = (left + right) // 2
            self.tree[node * 2] += self.lazy[node] * (mid - left + 1)
            self.tree[node * 2 + 1] += self.lazy[node] * (right - mid)
            self.lazy[node * 2] += self.lazy[node]
            self.lazy[node * 2 + 1] += self.lazy[node]
            self.lazy[node] = 0

    def update(self, node, left, right, l, r, val):
        if l <= left and right <= r:
            self.tree[node] += val * (right - left + 1)
            self.lazy[node] += val
            return
        self.push_down(node, left, right)
        mid = (left + right) // 2
        if l <= mid:
            self.update(node * 2, left, mid, l, r, val)
        if r > mid:
            self.update(node * 2 + 1, mid + 1, right, l, r, val)
        self.push_up(node)

    def query(self, node, left, right, l, r):
        if l <= left and right <= r:
            return self.tree[node]
        self.push_down(node, left, right)
        mid = (left + right) // 2
        res = 0
        if l <= mid:
            res += self.query(node * 2, left, mid, l, r)
        if r > mid:
            res += self.query(node * 2 + 1, mid + 1, right, l, r)
        return res


n, m, q = map(int, input().split())
x = []
for i in range(n):
    x.append(int(input()))
x.sort()
x = {x[i]: i + 1 for i in range(n)}
tree = SegmentTree(m)
for i in range(m):
    tree.update(1, 1, m, i + 1, i + 1, 1)
for i in range(q):
    op, l, r = map(int, input().split())
    if op == 1:
        tree.update(1, 1, m, x[l], x[l], -1)
        tree.update(1, 1, m, x[r], x[r], 1)
        x[l], x[r] = x[r], x[l]
    else:
        print(tree.query(1, 1, m, l, r))