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↵
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 ?
↵
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 ?
