hurt_FOR_heart's blog

Some permutation problem
By hurt_FOR_heart, history, 4 years ago, In English

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 ?

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hurt_FOR_heart (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hurt_FOR_heart (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem link please?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    https://oj.uz/problem/view/IOI18_werewolf i am trying to do this problem and i am stucking at above part. Looking forward for your help

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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})$$$.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

eliminate the log factor, lol

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting, you have been thinking about the problem and you have constraint Q <= N <= 2e5, but you can eliminate that log factor

→ Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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)$$$.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Same problem on CF with updates Intersection of Permutations

→ Reply