→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | jiangly | 3976 |
| 2 | tourist | 3815 |
| 3 | jqdai0815 | 3682 |
| 4 | ksun48 | 3614 |
| 5 | orzdevinwang | 3526 |
| 6 | ecnerwala | 3514 |
| 7 | Benq | 3482 |
| 8 | hos.lyric | 3382 |
| 9 | gamegame | 3374 |
| 10 | heuristica | 3357 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | -is-this-fft- | 165 |
| 3 | Um_nik | 161 |
| 3 | atcoder_official | 161 |
| 5 | djm03178 | 157 |
| 6 | Dominater069 | 156 |
| 7 | adamant | 154 |
| 8 | luogu_official | 152 |
| 9 | awoo | 151 |
| 10 | TheScrasse | 147 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jan/19/2025 02:07:26 (i1).
Desktop version, switch to mobile version.
Supported by
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
Yeah it is some sort of different than usual segment tree problems..Working on both the original and permutated version is kind of looking hard to handle..
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.