Intersection of Permutations (Codeforces 1093E)
Tags: Others, data structures

You are given two permutations $$$a$$$ and $$$b$$$, both consisting of $$$n$$$ elements. Permutation of $$$n$$$ elements is such a integer sequence that each value from $$$1$$$ to $$$n$$$ appears exactly once in it.You are asked to perform two types of queries with them:  $$$1~l_a~r_a~l_b~r_b$$$ — calculate the number of values which appear in both segment $$$[l_a; r_a]$$$ of positions in permutation $$$a$$$ and segment $$$[l_b; r_b]$$$ of positions in permutation $$$b$$$;  $$$2~x~y$$$ — swap values on positions $$$x$$$ and $$$y$$$ in permutation $$$b$$$. Print the answer for each query of the first type.It is guaranteed that there will be at least one query of the first type in the input.

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — the number of elements in both permutations and the number of queries.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — permutation $$$a$$$. It is guaranteed that each value from $$$1$$$ to $$$n$$$ appears in $$$a$$$ exactly once.The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$) — permutation $$$b$$$. It is guaranteed that each value from $$$1$$$ to $$$n$$$ appears in $$$b$$$ exactly once.Each of the next $$$m$$$ lines contains the description of a certain query. These are either:  $$$1~l_a~r_a~l_b~r_b$$$ ($$$1 \le l_a \le r_a \le n$$$, $$$1 \le l_b \le r_b \le n$$$);  $$$2~x~y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$). 

Output: Print the answers for the queries of the first type, each answer in the new line — the number of values which appear in both segment $$$[l_a; r_a]$$$ of positions in permutation $$$a$$$ and segment $$$[l_b; r_b]$$$ of positions in permutation $$$b$$$.

Note: Consider the first query of the first example. Values on positions $$$[1; 2]$$$ of $$$a$$$ are $$$[5, 1]$$$ and values on positions $$$[4; 5]$$$ of $$$b$$$ are $$$[1, 4]$$$. Only value $$$1$$$ appears in both segments.After the first swap (the second query) permutation $$$b$$$ becomes $$$[2, 1, 3, 5, 4, 6]$$$.After the second swap (the sixth query) permutation $$$b$$$ becomes $$$[5, 1, 3, 2, 4, 6]$$$.

Sample Inputs:
6 7
5 1 4 2 3 6
2 5 3 1 4 6
1 1 2 4 5
2 2 4
1 1 2 4 5
1 2 3 3 5
1 1 6 1 2
2 4 1
1 4 4 1 3

Sample Outputs:
1
1
1
2
0

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_tree(n):
    tree = [[0] * (n + 1) for _ in range(n // l)]
    return tree

def get_sum(i, j):
    s = 0
    treej = tree[j]
    while i > 0:
        s += treej[i]
        i -= i & -i
    return s

def get_sum_segment(s, t, j):
    ans = get_sum(t, j) - get_sum(s - 1, j)
    return ans

def add(i, j, x):
    while i <= n:
        tree[j][i] += x
        i += i & -i

def make_tree2(n):
    tree2 = [[0] * (n + 1) for _ in range(n // l2)]
    return tree2

def get_sum2(i, j):
    s = 0
    treej = tree2[j]
    while i > 0:
        s += treej[i]
        i -= i & -i
    return s

def get_sum_segment2(s, t, j):
    ans = get_sum2(t, j) - get_sum2(s - 1, j)
    return ans

def add2(i, j, x):
    while i <= n:
        tree2[j][i] += x
        i += i & -i
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
(l, l2) = (2000, 20000)
(a0, b0) = ([0] * (n + 1), [0] * (n + 1))
for i in range(n):
    a0[a[i]] = i + 1
    b0[b[i]] = i + 1
x = [0] * (n + 1)
for i in range(1, n + 1):
    x[a0[i]] = b0[i]
n0 = n
while (len(x) - 1) % l2:
    x.append(0)
    n0 += 1
y = [0] * (n + 1)
for i in range(1, n + 1):
    y[x[i]] = i
tree = make_tree(n0)
tree2 = make_tree2(n0)
for i in range(1, n + 1):
    add(x[i], (i - 1) // l, 1)
    add2(x[i], (i - 1) // l2, 1)
ans = []
for _ in range(m):
    t = list(map(int, input().split()))
    if t[0] == 1:
        (la, ra, lb, rb) = (t[1], t[2], t[3], t[4])
        ans0 = 0
        while la <= ra and (not la % l == 1):
            if lb <= x[la] <= rb:
                ans0 += 1
            la += 1
        while la <= ra and (not ra % l == 0):
            if lb <= x[ra] <= rb:
                ans0 += 1
            ra -= 1
        while la < ra:
            if (la - 1) % l2 == 0 and la + l2 <= ra + l:
                ans0 += get_sum_segment2(lb, rb, (la - 1) // l2)
                la += l2
            else:
                ans0 += get_sum_segment(lb, rb, (la - 1) // l)
                la += l
        ans.append(ans0)
    else:
        (u, v) = (t[1], t[2])
        (yu, yv) = (y[u], y[v])
        if not (yu - 1) // l == (yv - 1) // l:
            add(x[yu], (yu - 1) // l, -1)
            add(x[yv], (yv - 1) // l, -1)
            add(x[yu], (yv - 1) // l, 1)
            add(x[yv], (yu - 1) // l, 1)
            if not (yu - 1) // l2 == (yv - 1) // l2:
                add2(x[yu], (yu - 1) // l2, -1)
                add2(x[yv], (yv - 1) // l2, -1)
                add2(x[yu], (yv - 1) // l2, 1)
                add2(x[yv], (yu - 1) // l2, 1)
        (y[u], y[v]) = (yv, yu)
        (x[yu], x[yv]) = (x[yv], x[yu])
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys
import random
input = sys.stdin.readline
rd = random.randint(10 ** 9, 2 * 10 ** 9)

class BIT:

    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, index, val):
        while index <= self.n:
            self.tree[index] += val
            index += index & -index

    def query(self, r):
        res = 0
        while r > 0:
            res += self.tree[r]
            r -= r & -r
        return res

    def query_lr(self, left, right):
        return self.query(right) - self.query(left - 1)
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d1 = {a[i]: i + 1 for i in range(n)}
tree = BIT(n)
queries = []
ans = [-1] * m
for i in range(n):
    queries.append([2, 1, d1[b[i]], i + 1])
for i in range(m):
    q = list(map(int, input().split()))
    if q[0] == 1:
        (x1, x2, y1, y2) = q[1:]
        queries.append([1, x1, x2, y1 - 1, -1, i])
        queries.append([1, x1, x2, y2, 1, i])
        ans[i] = 0
    else:
        (x, y) = q[1:]
        (bx, by) = (b[x - 1], b[y - 1])
        queries.append([2, -1, d1[bx], x])
        queries.append([2, -1, d1[by], y])
        queries.append([2, 1, d1[by], x])
        queries.append([2, 1, d1[bx], y])
        (b[x - 1], b[y - 1]) = (b[y - 1], b[x - 1])
idx = list(range(len(queries)))

def cdq(l, r):
    if l == r:
        return
    mid = l + r >> 1
    cdq(l, mid)
    cdq(mid + 1, r)
    left = l
    for right in range(mid + 1, r + 1):
        if queries[idx[right]][0] == 1:
            (x1, x2, y, val, i) = queries[idx[right]][1:]
            while left <= mid:
                if queries[idx[left]][0] == 1:
                    left += 1
                elif queries[idx[left]][3] <= y:
                    tree.update(queries[idx[left]][2], queries[idx[left]][1])
                    left += 1
                else:
                    break
            ans[i] += val * tree.query_lr(x1, x2)
    for mm in range(l, left):
        if queries[idx[mm]][0] == 2:
            tree.update(queries[idx[mm]][2], -queries[idx[mm]][1])
    tmp = []
    left = l
    right = mid + 1
    while left <= mid and right <= r:
        if queries[idx[left]][3] <= queries[idx[right]][3]:
            tmp.append(idx[left])
            left += 1
        else:
            tmp.append(idx[right])
            right += 1
    while left <= mid:
        tmp.append(idx[left])
        left += 1
    while right <= r:
        tmp.append(idx[right])
        right += 1
    for i in range(l, r + 1):
        idx[i] = tmp[i - l]
cdq(0, len(queries) - 1)
for i in ans:
    if i != -1:
        print(i)

Solution (Python):
import sys
import random
input = sys.stdin.readline
rd = random.randint(10 ** 9, 2 * 10 ** 9)

class BIT:

    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, index, val):
        while index <= self.n:
            self.tree[index] += val
            index += index & -index

    def query(self, r):
        res = 0
        while r > 0:
            res += self.tree[r]
            r -= r & -r
        return res

    def query_lr(self, left, right):
        return self.query(right) - self.query(left - 1)
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d1 = {a[i]: i + 1 for i in range(n)}
tree = BIT(n)
queries = []
ans = [-1] * m
for i in range(n):
    queries.append([2, 1, d1[b[i]], i + 1])
for i in range(m):
    q = list(map(int, input().split()))
    if q[0] == 1:
        (x1, x2, y1, y2) = q[1:]
        queries.append([1, x1, x2, y1 - 1, -1, i])
        queries.append([1, x1, x2, y2, 1, i])
        ans[i] = 0
    else:
        (x, y) = q[1:]
        (bx, by) = (b[x - 1], b[y - 1])
        queries.append([2, -1, d1[bx], x])
        queries.append([2, -1, d1[by], y])
        queries.append([2, 1, d1[by], x])
        queries.append([2, 1, d1[bx], y])
        (b[x - 1], b[y - 1]) = (b[y - 1], b[x - 1])
idx = list(range(len(queries)))

def cdq(l, r):
    if l == r:
        return
    mid = l + r >> 1
    cdq(l, mid)
    cdq(mid + 1, r)
    left = l
    for right in range(mid + 1, r + 1):
        if queries[idx[right]][0] == 1:
            (x1, x2, y, val, i) = queries[idx[right]][1:]
            while left <= mid:
                if queries[idx[left]][0] == 1:
                    left += 1
                elif queries[idx[left]][3] <= y:
                    tree.update(queries[idx[left]][2], queries[idx[left]][1])
                    left += 1
                else:
                    break
            ans[i] += val * tree.query_lr(x1, x2)
    for mm in range(l, left):
        if queries[idx[mm]][0] == 2:
            tree.update(queries[idx[mm]][2], -queries[idx[mm]][1])
    tmp = []
    left = l
    right = mid + 1
    while left <= mid and right <= r:
        if queries[idx[left]][3] <= queries[idx[right]][3]:
            tmp.append(idx[left])
            left += 1
        else:
            tmp.append(idx[right])
            right += 1
    while left <= mid:
        tmp.append(idx[left])
        left += 1
    while right <= r:
        tmp.append(idx[right])
        right += 1
    for i in range(l, r + 1):
        idx[i] = tmp[i - l]
cdq(0, len(queries) - 1)
for i in ans:
    if i != -1:
        print(i)