### MY_TIME_HAS_COME's blog

By MY_TIME_HAS_COME, history, 3 months 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

By MY_TIME_HAS_COME, history, 9 months ago,

Hello, at problem E last contest I have do segment tree and binary search which reach a good complexity O((n+q)log(maxY)log(n)) but i dont know why It just give me a TLE judgement on test 18 Maybe my poor implementation ? Or there's some infinite loop ? Or I just make a wrong calculation in complexity ? I still cant find my mistake so I hope u guy could help me. Here is my code: https://codeforces.com/contest/1440/submission/98824111 Thanks in advance.