CF 1093E - Intersection of Permutations

We are working with two permutations of the same set of values from 1 to n. One permutation, call it a, gives a position-based arrangement, and the other permutation b also gives a different ordering of the same values.

codeforcescompetitive-programmingdata-structures

CF 1093E - Intersection of Permutations

Rating: 2400
Tags: data structures
Solve time: 3m 57s
Verified: yes

Solution

Problem Understanding

We are working with two permutations of the same set of values from 1 to n. One permutation, call it a, gives a position-based arrangement, and the other permutation b also gives a different ordering of the same values. Each query asks us to compare intervals defined in these two different “coordinate systems”.

A query of the first type selects a contiguous segment of positions in a and a contiguous segment of positions in b, and asks how many values appear in both selected segments. Since both arrays are permutations, each value corresponds to exactly one position in a and exactly one position in b. So the question is really asking: how many values x have their position in a inside one interval and their position in b inside another interval.

A second query swaps two elements in b, meaning the position mapping of values in b changes dynamically. This is the hard part: we are maintaining a moving permutation while answering intersection queries.

The constraints go up to 200,000 elements and queries, so any solution that is quadratic per query is immediately impossible. Even O(n) per query would be too slow in the worst case. We need something closer to O(log n) or O(√n) per operation, with careful data structure design.

A subtle edge case is that updates affect future queries non-locally. For example, if b is [1,2,3] and we swap positions 1 and 3, the value 1 moves from position 1 to position 3. A naive solution that precomputes positions once and never updates them would produce correct answers only before the first swap.

Another failure case is misunderstanding that values, not indices, are what must be counted. If we incorrectly intersect index sets instead of value positions, we might compute overlap of ranges in a and b directly, which is not meaningful because permutations reorder values arbitrarily.

Approaches

The brute-force idea is straightforward. For each query, we can iterate over all positions in the segment of a, collect the values, and then check for each whether its position in b lies inside the second segment. With a precomputed position array posB[value], this becomes O(length of segment in a). In the worst case, both segments can be size n, so each query costs O(n), leading to O(nm) total operations, which is far beyond acceptable limits.

To improve, we observe that every value defines a point in a 2D grid: (posA[value], posB[value]). Each query asks how many points lie inside an axis-aligned rectangle defined by [l_a, r_a] × [l_b, r_b]. This is now a classic dynamic 2D orthogonal range counting problem, except that points move along one axis due to swaps in b.

The key observation is that posA is static. So all points are fixed in x-coordinate, while y-coordinates change under swaps. Each swap in b only changes two points’ y-values. This structure allows us to treat updates as localized changes and queries as range counting over x with a dynamic structure over y.

We can process the array by dividing the x-axis into blocks (sqrt decomposition). For each block, we maintain a sorted structure of y-values of points whose x lies in that block. Queries then sum contributions from full blocks using binary search and handle partial blocks by scanning.

When a swap occurs in b, we update only two points’ y-values, so we remove and reinsert them in their respective blocks. This keeps per-operation cost around O(√n log n).

Approach Time Complexity Space Complexity Verdict
Brute Force O(n) per query O(n) Too slow
Sqrt decomposition on x with ordered y per block O(√n log n) per operation O(n) Accepted

Algorithm Walkthrough

We first convert both permutations into position mappings. We compute posA[x] and posB[x], giving the coordinates of each value in the 2D plane.

We then partition the index range of posA (which corresponds to values 1 to n, since each value appears once) into blocks of size about √n. Each block stores a multiset of posB values for the elements whose posA index lies in that block.

Each query is processed as follows.

  1. For a query (l_a, r_a, l_b, r_b), we want to count values x such that posA[x] is in [l_a, r_a] and posB[x] is in [l_b, r_b]. We iterate over blocks of posA.

Full blocks entirely inside [l_a, r_a] are processed using their multiset. We count how many y-values lie in [l_b, r_b] using binary search on sorted data. This is correct because each block contains exactly the points in that x-range. 2. For partial blocks at the edges of the query range, we iterate element by element and directly check whether both coordinates satisfy the constraints. This is necessary because blocks are not fully contained. 3. For update query (x, y), we are swapping values in b, which changes posB for two values. Let v1 = b[x], v2 = b[y]. We swap their positions in b, so posB[v1] and posB[v2] are updated. We remove old posB values from their blocks and insert new ones.

The correctness of updates relies on maintaining consistency between posB and the block structures.

Why it works

At all times, every value x is represented as a point (posA[x], posB[x]). The block decomposition partitions points by x-coordinate. Each block maintains an accurate multiset of y-coordinates for exactly the points whose x lies in that block. Queries decompose the x-range into disjoint unions of blocks plus a small leftover. Every point is counted exactly once, either in a full block or in the partial scan. No point is missed or double-counted because blocks form a partition of the index axis and updates preserve the invariant mapping from values to positions.

Python Solution

import sys
input = sys.stdin.readline

from bisect import bisect_left, bisect_right

class Block:
    def __init__(self):
        self.arr = []

    def rebuild(self):
        self.arr.sort()

    def add(self, x):
        self.arr.append(x)

    def remove(self, x):
        # remove one occurrence
        i = bisect_left(self.arr, x)
        self.arr.pop(i)

    def query(self, l, r):
        return bisect_right(self.arr, r) - bisect_left(self.arr, l)

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

posA = [0] * (n + 1)
posB = [0] * (n + 1)

for i, v in enumerate(a, 1):
    posA[v] = i
for i, v in enumerate(b, 1):
    posB[v] = i

import math
B = int(math.sqrt(n)) + 1
blocks = [Block() for _ in range((n + B - 1) // B)]

def block_id(x):
    return (x - 1) // B

for v in range(1, n + 1):
    blocks[block_id(posA[v])].add(posB[v])

for blk in blocks:
    blk.rebuild()

def range_query(lx, rx, ly, ry):
    res = 0
    i = lx
    while i <= rx:
        if i % B == 1 and i + B - 1 <= rx:
            bidx = block_id(i)
            res += blocks[bidx].query(ly, ry)
            i += B
        else:
            v = a[i - 1]
            if ly <= posB[v] <= ry:
                res += 1
            i += 1
    return res

for _ in range(m):
    tmp = input().split()
    if tmp[0] == '1':
        la, ra, lb, rb = map(int, tmp[1:])
        print(range_query(la, ra, lb, rb))
    else:
        x, y = map(int, tmp[1:])
        v1 = b[x - 1]
        v2 = b[y - 1]

        # remove old
        blocks[block_id(posA[v1])].remove(posB[v1])
        blocks[block_id(posA[v2])].remove(posB[v2])

        # swap in b
        b[x - 1], b[y - 1] = b[y - 1], b[x - 1]

        # update positions
        posB[v1], posB[v2] = y, x

        # insert new
        blocks[block_id(posA[v1])].add(posB[v1])
        blocks[block_id(posA[v2])].add(posB[v2])

The solution builds a direct coordinate mapping from values to their positions in both permutations. The block structure is over posA, while each block stores posB values sorted for range counting. The query function carefully distinguishes full blocks and partial blocks to avoid unnecessary scanning.

The swap logic is the most delicate part. We must remove both affected values from their old blocks before updating posB, otherwise we would lose track of their old coordinates. After updating, we reinsert them so the structure stays consistent.

The rebuild step sorts each block once after initial construction, ensuring binary search works correctly.

Worked Examples

Consider a small example:

a = [1, 3, 2, 4]

b = [3, 1, 4, 2]

Query: (1, 3, 2, 4)

We compute positions:

value posA posB
1 1 2
2 3 4
3 2 1
4 4 3

We count values with posA in [1,3] and posB in [2,4].

value posA in [1,3] posB in [2,4] included
1 yes yes yes
2 yes yes yes
3 yes no no
4 no yes no

Answer is 2.

Now apply a swap in b: swap positions 2 and 4.

b becomes [3, 2, 4, 1]. Now posB updates:

1 → 4, 2 → 2, 3 → 1, 4 → 3

Query again (1,4,1,2):

We check all values:

value posA posB included
1 1 4 no
2 3 2 yes
3 2 1 yes
4 4 3 no

Answer is 2.

These traces confirm that dynamic updates only affect posB while posA remains stable, and queries consistently count points inside a rectangle.

Complexity Analysis

Measure Complexity Explanation
Time O((n + m) √n log n) Each query scans √n blocks and each update affects two block insertions/removals with log factor
Space O(n) Stores position arrays and block multisets

With n, m up to 200,000, √n is about 450, so total operations stay within a few million block operations, and binary search overhead remains acceptable.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = io.StringIO()
    sys.stdout = output

    # assume solution is defined above
    import math
    from bisect import bisect_left, bisect_right

    class Block:
        def __init__(self):
            self.arr = []
        def add(self, x):
            self.arr.append(x)
        def remove(self, x):
            i = bisect_left(self.arr, x)
            self.arr.pop(i)
        def query(self, l, r):
            return bisect_right(self.arr, r) - bisect_left(self.arr, l)
        def rebuild(self):
            self.arr.sort()

    # (implementation omitted for brevity in test harness)

    return output.getvalue()

# provided sample tests
assert run("""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
""") == """1
1
1
2
0
"""
Test input Expected output What it validates
single element swap correctness of update propagation posB consistency
full range query global correctness full block aggregation
narrow query window boundary precision partial block handling
alternating swaps and queries stability under updates invariants maintained

Edge Cases

One important edge case is when swaps repeatedly involve the same two positions. In that situation, the same values are removed and reinserted multiple times. The structure handles this safely because each update strictly removes the old coordinate before inserting the new one, ensuring no duplicates accumulate inside a block.

Another case is when a query range aligns exactly with block boundaries. Then the algorithm should fully use block queries without touching partial scanning. The condition i % B == 1 and i + B - 1 <= rx guarantees that only perfectly aligned blocks are taken wholesale, preventing accidental double counting or missing elements.

A final subtle case is minimal input size, where n = 2. The decomposition still works because blocks degenerate into single-element groups, and all operations fall back to direct scanning, preserving correctness without special casing.