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

this problem appeared in the latest ieeextreme contest and it had a segtree beat like solution , dont remember it cuz i suck at DS stuff

I have wondered of this for a long time! I'm so happy someone brought it up

I found a sqrt-ish solution. (Sorry, I still don't know latex.)

1. Idea 1: Since each add operation and query operation is independent, we can independently calculate the contributions for 0 → 2, 0 → 3, 1 → 2, and 1 → 3. After computing these four contributions, simply sum all the answers together.

2. Idea 2: For 0 → 2 and 1 → 3, a simple segment tree can be used for maintenance.

3. Idea 3: For 0 → 3, construct an array b, where b[i] = a[p[i]]. Then divide both arrays a and b into sqrt(n) blocks. For each pair of blocks, calculate how much the sum of the corresponding block in b would change if a block in a undergoes a global +1. Maintain this information using prefix sums. During modification operations:

• For entire blocks, simply read and modify the information from the prefix sum.
• For scattered elements, perform the modifications directly with brute force.

For the contribution of a whole block of a to a single point of b, since p is a permutation, a point of b can only be obtained by transferring a point of a. It is only necessary to check the value of the full block of a that has been modified.

1. Idea 4: For 1 → 2, the operations are almost identical to those for 0 → 3.

By following this approach, the complexity is O(n^1.5) without including logarithmic factors.

I used GPT for the translation, but I assure you that the thought process is human-sourced and not AI-generated garbage.