### MY_TIME_HAS_COME's blog

By MY_TIME_HAS_COME, history, 4 weeks ago,

Recently, i have been thinking about this problem : You are given 2 permutations P and Q od length N and 1,2,3,...N appear exactly 1 time in each permutation. You have to answer Q query (Q <= N <= 2e5) with form L1 R1 L2 R2 means that how many element are "on" in range L2 R2 of Q if all element in range L1 R1 of P is "on" all other element in this query is "off"

Ex input : 6

3 2 4 5 1 6

1 2 3 4 5 6

1

2 4 4 6

output : 2

I have tried to use Mo + segment tree with O(N*sqrt(N)*logN) but it seems to be too slow. Anyone have better idea ?

• +4

 » 4 weeks ago, # |   0 Auto comment: topic has been updated by MY_TIME_HAS_COME (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by MY_TIME_HAS_COME (previous revision, new revision, compare).
•  » » » 4 weeks ago, # ^ |   0 My solution: use your Mo solution, but instead of the segment tree use a data structure that you can update in $O(1)$ time and query in $O(\sqrt{n})$ time. Then, complexity will be $O(n \sqrt{n})$.
 » 4 weeks ago, # |   +18 If element $x$ is on position $p$ in $P$, and on position $q$ in $Q$, then add point $(p,q)$ to a 2D-plane. We do this for every $1 \leq x \leq N$.Then, the query $(L_1,R_1,L_2,R_2)$ is equal to: how many points are in the rectangle $(L_1, R_1, L_2, R_2)$?We can solve this problem offline with line sweep and a data structure (Fenwick Tree or Segment Tree) in $O(N \log N)$.