Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/07/2026 15:09:03 (g2).
Desktop version, switch to mobile version.
Supported by
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.)
First, we divide all queries into s blocks. Then, in each block, we will answer queries one by one. To answer a query, we will look at how much each update contributes. For same type queries (0 and 2, or 1 and 3), it's trivial, but for different type updates it's a bit harder. We have to calculate how many x in [l, r] contained in [p_l, p_r]. It can be done with a persistent segment tree (for p array, count how many values in range [lq, rq] is smaller or equal to r, and substract the same value for (l-1)). Persistent segment tree can be calculated at the beginning. After all queries are completed in a block, we will calculate all changes to the array in again O(|block|logN). In total, picking block size as sqrt(N), we will have O(Nsqrt(N)logN) complexity. (Then, we will hope it passes the tests :).)
Idea 1: Since each add operation and query operation is independent, we can independently calculate the contributions for
0 → 2,0 → 3,1 → 2, and1 → 3. After computing these four contributions, simply sum all the answers together.Idea 2: For
0 → 2and1 → 3, a simple segment tree can be used for maintenance.Idea 3: For
0 → 3, construct an arrayb, whereb[i] = a[p[i]]. Then divide both arraysaandbintosqrt(n)blocks. For each pair of blocks, calculate how much the sum of the corresponding block inbwould change if a block inaundergoes a global+1. Maintain this information using prefix sums. During modification operations: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 → 2, the operations are almost identical to those for0 → 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.