codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1830.md (43272B)


      1 Source: https://codeforces.com/blog/entry/116527
      2 
      3 ## [1831A — Twin Permutations](https://codeforces.com/contest/1831/problem/A)
      4 
      5 Author: [Gheal](/profile/Gheal "Candidate Master Gheal")
      6 
      7 **Hints**
      8 
      9 **Hint 1**
     10 
     11 If $a_i+b_i \le a_{i+1}+b_{i+1}$, then $a_i+b_i$ can be equal to $a_{i+1}+b_{i+1}$.
     12 
     13 **Hint 2**
     14 
     15 Building on the idea from the first hint, can we build a permutation $b$ such that $a_1+b_1=a_2+b_2=\ldots=a_n+b_n$?
     16 
     17 **Solution**
     18 
     19 Since $a_i+b_i \le a_{i+1}+b_{i+1}$, then $a_i+b_i$ can be equal to $a_{i+1}+b_{i+1}$.
     20 
     21 Therefore, any permutation $b$ which satisfies $a_1+b_1=a_2+b_2=\ldots=a_n+b_n$ is a valid answer.
     22 
     23 If $b_i=n+1-a_i$, then:
     24 
     25 1. $b$ is a permutation;
     26 2. $a_1+b_1=a_2+b_2=\ldots=a_n+b_n=n+1$
     27 
     28 Consequently, $b=[n+1-a_1,n+1-a_2,\ldots,n+1-a_i,\ldots,n+1-a_n]$ is a valid answer.
     29 
     30 Time complexity per test case : $O(N)$
     31 
     32 **Code (Gheal, C++)**
     33 
     34 ```
     35 #include<bits/stdc++.h>
     36 
     37 using namespace std;
     38 typedef long long ll;
     39 void tc(){
     40     ll n;
     41     cin>>n;
     42     for(ll i=0;i<n;i++){
     43         ll x;
     44         cin>>x;
     45         cout<<n+1-x<<' ';
     46     }
     47     cout<<'\n';
     48 }
     49 int main()
     50 {
     51     ios_base::sync_with_stdio(false); cin.tie(0);
     52     ll t; cin>>t; while(t--)
     53         tc();
     54     return 0;
     55 }
     56 ```
     57 
     58 **Rate Problem**
     59 
     60 Good problem
     61 
     62 Ok problem
     63 
     64 Bad problem
     65 
     66 Didn't solve it, idk
     67 
     68 ## [1831B — Array Merging](https://codeforces.com/contest/1831/problem/B)
     69 
     70 Author: [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006")
     71 
     72 **Hints**
     73 
     74 **Hint 1**
     75 
     76 When we merge two arrays $a$ and $b$, we can force the resulting array to have $[a_{l_1},a_{l_1+1},\ldots,a_{r_1},b_{l_2},b_{l_2+1},\ldots,b_{r_1}]$ as a subarray, for some $1 \le l_1 \le r_1 \le n$ and $1 \le l_2 \le r_2 \le n$.
     77 
     78 **Hint 2**
     79 
     80 If $a_{l_1}=b_{l_1}$, then we can achieve a contiguous sequence of $(r_1-l_1+1)+(r_2-l_2+1)$ equal elements in the resulting array.
     81 
     82 **Solution**
     83 
     84 Let $max_a(x)$ be the length of the longest subarray from $a$ containing only elements equal to $x$. If $x$ doesn't appear in $a$, then $max_a(x)=0$.
     85 
     86 Similarly, let $max_b(x)$ be the length of the longest subarray from $b$ containing only elements equal to $x$. If $x$ doesn't appear in $b$, then $max_b(x)=0$.
     87 
     88 $max_a$ and $max_b$ can be computed in $O(N)$ by scanning the array while updating current maximal subarray.
     89 
     90 When merging two arrays, it is possible to force a particular subarray $[a_{l_1},a_{l_1+1},\ldots,a_{r_1}]$ to be adjacent to another particular subarray $[b_{l_2},b_{l_2+1},\ldots,b_{r_2}]$ in the merged array.
     91 
     92 **Proof**
     93 
     94 We can construct the merged array as follows:
     95 
     96 $[a_1,a_2,\ldots,a_{l_1-1}]+[b_1,b_2,\ldots,b_{l_2-1}]+[a_{l_1},a_{l_1+1},\ldots,a_{r_1},b_{l_2},b_{l_2+1},\ldots,b_{r_2}]+[\ldots]$
     97 
     98 If $a_{l_1}=b_{l_2}$, then the merged array will have a subarray consisting of $(r_1-l_1+1)+(r_2-l_2+1)$ equal elements.
     99 
    100 Therefore, the answer is equal to:
    101 
    102 $max_{i=1}^{2 \cdot n}(max_a(i)+max_b(i))$
    103 
    104 Time complexity per testcase: $O(N)$.
    105 
    106 **Code (tibinyte, C++)**
    107 
    108 ```
    109 #include <bits/stdc++.h>
    110 
    111 using namespace std;
    112 
    113 int32_t main()
    114 {
    115     cin.tie(nullptr)->sync_with_stdio(false);
    116     int q;
    117     cin >> q;
    118     while (q--)
    119     {
    120         int n;
    121         cin >> n;
    122         vector<int> a(n + 1);
    123         vector<int> b(n + 1);
    124         for (int i = 1; i <= n; ++i)
    125         {
    126             cin >> a[i];
    127         }
    128         for (int i = 1; i <= n; ++i)
    129         {
    130             cin >> b[i];
    131         }
    132         vector<int> fa(n + n + 1);
    133         vector<int> fb(n + n + 1);
    134         int p = 1;
    135         for (int i = 2; i <= n; ++i)
    136         {
    137             if (a[i] != a[i - 1])
    138             {
    139                 fa[a[i - 1]] = max(fa[a[i - 1]], i - p);
    140                 p = i;
    141             }
    142         }
    143         fa[a[n]] = max(fa[a[n]], n - p + 1);
    144 
    145         p = 1;
    146         for (int i = 2; i <= n; ++i)
    147         {
    148             if (b[i] != b[i - 1])
    149             {
    150                 fb[b[i - 1]] = max(fb[b[i - 1]], i - p);
    151                 p = i;
    152             }
    153         }
    154         fb[b[n]] = max(fb[b[n]], n - p + 1);
    155 
    156         int ans = 0;
    157         for (int i = 1; i <= n + n; ++i)
    158         {
    159             ans = max(ans, fa[i] + fb[i]);
    160         }
    161 
    162         cout << ans << '\n';
    163     }
    164 }
    165 ```
    166 
    167 **Rate problem**
    168 
    169 Good problem
    170 
    171 Ok problem
    172 
    173 Bad problem
    174 
    175 Didn't solve it, idk
    176 
    177 ## [1830A — Copil Copac Draws Trees](https://codeforces.com/contest/1830/problem/A)
    178 
    179 Author: [alecs](/profile/alecs "Candidate Master alecs")
    180 
    181 **Hints**
    182 
    183 **Hint 1**
    184 
    185 What is the answer if $n=3$?
    186 
    187 **Hint 2**
    188 
    189 The previous case can be generalised to find the answer for any tree.
    190 
    191 **Solution**
    192 
    193 This problem can be solved via dynamic programming. From here on out, step $1$ from the statement will be called a "scan".
    194 
    195 Let $dp[i]$ be the number of scans needed to activate node $i$, and $id[i]$ be the index (in the order from the input) of the edge which activated node $i$.
    196 
    197 Intially, since only $1$ is active, $dp[1]=1$ and $id[1]=0$.
    198 
    199 We will perform a dfs traversal starting from node $1$. When we process an edge $(u,v)$, one of the following two cases can happen:
    200 
    201 1. If $index((u,v)) \ge id[u]$, we can visit $v$ in the same scan as $u$:
    202 
    203 $dp[v]=dp[u]$, $id[v]=index((u,v))$
    204 
    205 1. If $index((u,v)) \lt id[u]$, $v$ will be visited in the next scan after $dp[u]$:
    206 
    207 $dp[v]=dp[u]+1$, $id[v]=index((u,v))$
    208 
    209 The answer is $max_{i=1}^n(dp[i])$.
    210 
    211 Time complexity per test case: $O(n)$
    212 
    213 **Code (Gheal, C++)**
    214 
    215 ```
    216 #include<bits/stdc++.h>
    217 
    218 using namespace std;
    219 const int NMAX = 2e5+5;
    220 int dp[NMAX], id[NMAX];
    221 vector<pair<int,int>> edg[NMAX];
    222 void dfs(int u){
    223     for(auto it : edg[u]){
    224         if(dp[it.first] == 0){
    225             dp[it.first] = dp[u] + (it.second <= id[u]);
    226             id[it.first] = it.second;
    227             dfs(it.first);
    228         }
    229     }
    230 }
    231 void tc(){
    232     int n;
    233     cin>>n;
    234     for(int i=1; i<=n; i++) dp[i] = id[i] = 0, edg[i].clear();
    235     for(int i=1; i<n; i++){
    236         int u,v;
    237         cin>>u>>v;
    238         edg[u].push_back({v,i});
    239         edg[v].push_back({u,i});
    240     }
    241     dp[1] = 1;
    242     dfs(1);
    243     int ans = 0;
    244     for(int i=1; i<=n; i++) ans=max(ans,dp[i]);
    245     cout<<ans<<'\n';
    246 }
    247 int main()
    248 {
    249     ios_base::sync_with_stdio(false);
    250     int t;
    251     cin>>t;
    252     while(t--)
    253         tc();
    254     return 0;
    255 }
    256 ```
    257 
    258 **Code (alecs, C++)**
    259 
    260 ```
    261 #include <bits/stdc++.h>
    262 
    263 const int NMAX = 3e5 + 5, INF = 1e9;
    264 
    265 int n, f[NMAX], d[NMAX];
    266 std :: vector < std :: pair < int, int > > G[NMAX];
    267 
    268 void DFS(int node, int t) {
    269     f[node] = true;
    270 
    271     for (int i = 0; i < G[node].size(); ++ i) {
    272         int u = G[node][i].first, c = G[node][i].second;
    273 
    274         if (f[u] == false) {
    275             d[u] = (c < t) + d[node];
    276             DFS(u, c);
    277         }
    278     }
    279 
    280     return;
    281 }
    282 
    283 int main() {
    284     std :: ios_base :: sync_with_stdio(false);
    285     std :: cin.tie(nullptr);
    286     
    287     int tc;
    288     
    289     std :: cin >> tc;
    290     
    291     while (tc --) {
    292         std :: cin >> n;
    293     
    294         for (int i = 1, u, v; i < n; ++ i) {
    295             std :: cin >> u >> v;
    296     
    297             G[u].push_back({v, i});
    298             G[v].push_back({u, i});
    299         }
    300         
    301         for (int i = 1; i <= n; ++ i)
    302             f[i] = false;
    303     
    304         d[1] = 0;
    305         DFS(1, n);
    306     
    307         int Max = 0;
    308     
    309         for (int i = 1; i <= n; ++ i)
    310             Max = std :: max(Max, d[i]);
    311     
    312         std :: cout << Max << "\n";
    313         
    314         for (int i = 1; i <= n; ++ i)
    315             G[i].clear();
    316     }
    317 
    318     return 0;
    319 }
    320 ```
    321 
    322 **Rate problem**
    323 
    324 Good problem
    325 
    326 Ok problem
    327 
    328 Bad problem
    329 
    330 Didn't solve it, idk
    331 
    332 ## [1830B — The BOSS Can Count Pairs](https://codeforces.com/contest/1830/problem/B)
    333 
    334 Author: [Gheal](/profile/Gheal "Candidate Master Gheal")
    335 
    336 **Hints**
    337 
    338 **Hint 1**
    339 
    340 Since $b_i \le n$ and $b_j \le n$, $b_i+b_j = a_i \cdot a_j \le 2 \cdot n$.
    341 
    342 **Hint 2**
    343 
    344 Since $a_i \cdot a_j \le 2 \cdot n$, then $\min(a_i,a_j) \le \sqrt{2 \cdot n}$.
    345 
    346 **Solution**
    347 
    348 Since $b_i \le n$ and $b_j \le n$, $b_i+b_j = a_i \cdot a_j \le 2 \cdot n$. Therefore, $\min(a_i,a_j) \le \sqrt{2 \cdot n}$.
    349 
    350 Let $lim=\sqrt{2 \cdot n}$ and $fr[a_i][b_i]$ be the number of pairs $(a_i,b_i)$ from the input such that $a_i \le lim$.
    351 
    352 A pair $(i,j)$ is *good* if it satisfies $a_i \cdot a_j=b_i+b_j$.
    353 
    354 Firstly, we'll count the number of good pairs $(i,j)$ such that $a_i=a_j$. Since $min(a_i,a_j) \le lim$, we can see that $a_i=a_j \le lim$.
    355 
    356 This sum can be written as:
    357 
    358 $\frac{\sum_{i=1}^{n}fr[a_i][a_i \cdot a_i - b_i]-\sum_{i=1}^{lim}fr[i][\frac{i \cdot i}{2}]}{2}$
    359 
    360 The remaining good pairs will have $a_i \neq a_j$, and instead of counting the pairs which have $i \lt j$, we can count the pairs which have $a_i \gt a_j$.
    361 
    362 Since $a_j=min(a_i,a_j)$, we can say that $a_j \le lim$.
    363 
    364 Substituting $a_j$ for $j$, this second sum can be written as:
    365 
    366 $\sum_{i=1}^n \sum_{j=1}^{min(a_i-1,\frac{2\cdot n}{a_i})}fr[j][a_i \cdot j-b_i]$
    367 
    368 Since we've already established that $j \le lim = \sqrt{2 \cdot n}$, calculating this sum takes $O(n\sqrt{n})$ time.
    369 
    370 **Be especially careful when calculating these sums, as $a_i \cdot a_i - b_i$ and $a_i \cdot j-b_i$ can end up being either negative or greater than $n$.**
    371 
    372 Time complexity per testcase: $O(n \sqrt n)$
    373 
    374 **Code (Gheal, C++)**
    375 
    376 ```
    377 #include<bits/stdc++.h>
    378 
    379 using namespace std;
    380 typedef long long ll;
    381 const ll NMAX=2e5+5,SQRMAX=635,MOD=1e9+7;
    382 
    383 int fr[SQRMAX][NMAX];
    384 ll a[NMAX],b[NMAX];
    385 void tc(){
    386     ll n,ans=0;
    387     cin>>n;
    388     ll lim=sqrt(n*2);
    389     for(ll i=0;i<n;i++){
    390         cin>>a[i];
    391     }
    392     for(ll i=0;i<n;i++){
    393         cin>>b[i];
    394         if(a[i]<=lim)
    395             fr[a[i]][b[i]]++;
    396     }
    397     for(ll i=0;i<n;i++){
    398         if(a[i]<=lim){
    399             if(a[i]*a[i]-b[i]>=1 && a[i]*a[i]-b[i]<=n)
    400                 ans+=fr[a[i]][a[i]*a[i]-b[i]];
    401         }
    402     }
    403     for(ll i=2;i<=lim;i+=2)
    404         ans-=fr[i][i*i/2];
    405     ans/=2;
    406 
    407     for(ll i=0;i<n;i++){
    408         for(ll j=1;j<=lim && j<a[i] && j*a[i]<=2*n;j++){
    409             if(j*a[i]-b[i]>=1 && j*a[i]-b[i]<=n)
    410                 ans+=fr[j][j*a[i]-b[i]];
    411         }
    412     }
    413     for(ll i=0;i<n;i++){
    414         if(a[i]<=lim)
    415             fr[a[i]][b[i]]=0;
    416     }
    417     cout<<ans<<'\n';
    418 }
    419 int main()
    420 {
    421     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    422     ll t;
    423     cin>>t;
    424     while(t--)
    425         tc();
    426     return 0;
    427 }
    428 ```
    429 
    430 **Code (Vladithur, Python)**
    431 
    432 ```
    433 for _ in range(int(input())):
    434     n = int(input())
    435     
    436     ta = list(map(int, input().split()))
    437     tb = list(map(int, input().split()))
    438     
    439     a = [(x, y) for x, y in zip(ta, tb)]
    440     a.sort()
    441     
    442     cnt = [0] * (2 * n + 1)
    443     pr = 0
    444     ans = 0
    445     
    446     for i in range(n):
    447         if pr != a[i][0]:
    448             pr = a[i][0]
    449             
    450             if pr * pr > 2 * n:
    451                 break
    452                 
    453             cnt = [0] * (2 * n + 1)
    454             for j in range(i + 1, n):
    455                 t = a[i][0] * a[j][0] - a[j][1]
    456                 if t >= 0 and t <= 2 * n:
    457                     cnt[t] += 1
    458         
    459         ans += cnt[a[i][1]]
    460         
    461         if i + 1 < n:
    462             t = a[i][0] * a[i + 1][0] - a[i + 1][1]
    463             if t >= 0 and t <= 2 * n:
    464                 cnt[t] -= 1
    465     
    466     print(ans)
    467 ```
    468 
    469 **Rate problem**
    470 
    471 Good problem
    472 
    473 Ok problem
    474 
    475 Bad problem
    476 
    477 Didn't solve it, idk
    478 
    479 ## [1830C — Hyperregular Bracket Strings](https://codeforces.com/contest/1830/problem/C)
    480 
    481 Author: [Gheal](/profile/Gheal "Candidate Master Gheal")
    482 
    483 **Hints**
    484 
    485 **Hint 1**
    486 
    487 While not necessarily a hint, this problem cannot be solved without knowing that there are $C_n=\frac{1}{n+1}\binom{2n}{n}$ Regular Bracket Strings of length $2 \cdot n$.
    488 
    489 **Hint 2**
    490 
    491 What's the answer if $q=1$?
    492 
    493 **Hint 3**
    494 
    495 What's the answer if $q=2$ and the two intervals partially overlap?
    496 
    497 **Hint 4**
    498 
    499 Based on the previous hint, we can get rid of all partially overlapping intervals. The remaining intervals will have a tree-like structure.
    500 
    501 **Hint 5**
    502 
    503 Finding the tree is actually unnecessary and also very difficult.
    504 
    505 **Hint 6**
    506 
    507 The brackets on the positions covered by the same **subset** of intervals must form an RBS.
    508 
    509 **Hint 7**
    510 
    511 Hashing. Xor hashing specifically.
    512 
    513 **Solution**
    514 
    515 First and foremost, the number of regular bracket strings of length $2 \cdot n$ is equal to $C_n=\frac{1}{n+1}\binom{2n}{n}$.
    516 
    517 Secondly, for a bracket string $\overline{s_1s_2 \ldots s_k}$, let:
    518 
    519 $f(s_i) = \begin{cases} 1, & \text{if }s_i=\text{'('} \\ -1, & \text{if }s_i=\text{')'} \end{cases}$$\Delta_i=\sum_{j=1}^i f(s_j)$
    520 
    521 A bracket string $\overline{s_1s_2 \ldots s_k}$ is a regular bracket string if both of the following statements are true:
    522 
    523 1. $\Delta_k=0$
    524 2. $\Delta_i \ge 0, i=\overline{1,k}$
    525 
    526 From now on we'll call a set of indices $i_1 \lt i_2 \lt \ldots \lt i_k$ a *group* if $\overline{s_{i_1}s_{i_2}\ldots s_{i_k}}$ must be an RBS.
    527 
    528 There are two main cases to consider, both of which can be proven with the aforementioned conditions for a string to be an RBS:
    529 
    530 **Case 1: Included intervals**
    531 
    532 Let's consider two intervals $[l_1,r_1]$ and $[l_2,r_2]$ such that $l_1 \le l_2 \le r_2 \le r_1$.
    533 
    534 The two groups formed by these intervals are:
    535 
    536 * $[l_2,r_2]$
    537 * $[l_1,l_2-1] \cup [r_2+1,r_1]$
    538 
    539 **Case 2: Partially overlapping intervals**
    540 
    541 Let's consider two intervals $[l_1,r_1]$ and $[l_2,r_2]$ such that $l_1 \lt l_2 \le r_1 \lt r_2$.
    542 
    543 The three groups formed by these two intervals are:
    544 
    545 * $[l_1,l_2-1]$
    546 * $[l_2,r_1]$
    547 * $[r_1+1,r_2]$
    548 
    549 By taking both of these cases into account, we can conclude that all indices $i_k$ covered by the same **subset** of intervals are part of the same group.
    550 
    551 Finding the subset of intervals which cover a certain index $i$ can be implemented using difference arrays and xor hashing.
    552 
    553 **How does xor hashing on difference arrays work?**
    554 
    555 Each interval $[l_i,r_i]$ will be assigned a random 64-bit value $v_i$.
    556 
    557 The value of a subset of intervals $i_1,i_2,\ldots,i_k$ is equal to $v_{i_1} \wedge v_{i_2} \wedge \ldots \wedge v_{i_k}$.
    558 
    559 For each interval $[l_i,r_i]$, $\text{diff}[l_i] \wedge = v_i$, $\text{diff}[r_i+1] \wedge = v_i$.
    560 
    561 The value of the subset of intervals which cover position $i$ is equal to $\text{diff}[1] \wedge \text{diff}[2] \wedge \ldots \wedge \text{diff}[i]$.
    562 
    563 Time complexity: $O(maxn \cdot log(mod))$ for precomputing every $C_n$, and $O(k\cdot log(k))$ per test case.
    564 
    565 **Code (Gheal, C++)**
    566 
    567 ```
    568 #include<bits/stdc++.h>
    569 
    570 using namespace std;
    571 typedef long long ll;
    572 const int NMAX=3e5+5, MOD=998244353;
    573 
    574 mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    575 uniform_int_distribution<ll> rnd(0,LLONG_MAX);
    576 
    577 ll fact[NMAX], invfact[NMAX], C[NMAX];
    578 
    579 ll binPow(ll x, ll y){
    580     ll ans=1;
    581     for(;y ;y>>=1, x = x*x%MOD)
    582         if(y&1)
    583             ans = ans*x%MOD;
    584     return ans;
    585 }
    586 map<ll,ll> diff,freq;
    587 void add_interval(ll l, ll r){
    588     ll Hash = rnd(gen);
    589     diff[l] ^= Hash, diff[r+1] ^= Hash;
    590 }
    591 void tc(){
    592     ll n,k;
    593     cin>>n>>k;
    594     diff.clear(), freq.clear();
    595     add_interval(1,n); /// the initial string must be an RBS
    596 
    597     for(ll i=0;i<k;i++){
    598         ll l,r;
    599         cin>>l>>r;
    600         add_interval(l,r);
    601     }
    602     ll Hash = diff[1];
    603 
    604     for(map<ll,ll> :: iterator it=next(diff.begin()); it!=diff.end(); it++){
    605         freq[Hash] += it->first - prev(it)->first;
    606         Hash ^= it->second;
    607     }
    608 
    609     ll ans=1;
    610 
    611     for(const auto& it : freq)
    612         ans=ans*C[it.second]%MOD;
    613 
    614     cout<<ans<<'\n';
    615 }
    616 
    617 int main()
    618 {
    619     fact[0] = invfact[0] = 1;
    620     for(ll i=1; i<NMAX; i++){
    621         fact[i] = fact[i-1] * i % MOD;
    622         invfact[i] = binPow(fact[i], MOD - 2);
    623     }
    624 
    625     for(ll i=0; i*2<NMAX; i++) C[i*2] = fact[i*2] * invfact[i] % MOD * invfact[i+1] % MOD;
    626 
    627     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    628     ll t;
    629     cin>>t;
    630     while(t--)
    631         tc();
    632     return 0;
    633 }
    634 ```
    635 
    636 **Rate problem**
    637 
    638 Good problem
    639 
    640 Ok problem
    641 
    642 Bad problem
    643 
    644 Didn't solve it, idk
    645 
    646 ## [1830D — Mex Tree](https://codeforces.com/contest/1830/problem/D)
    647 
    648 Author: [Gheal](/profile/Gheal "Candidate Master Gheal")
    649 
    650 **Hints**
    651 
    652 **Hint 1**
    653 
    654 Why is bipartite coloring not always optimal?
    655 
    656 **Hint 2**
    657 
    658 How good is a bipartite coloring actually?
    659 
    660 **Solution**
    661 
    662 Disclaimer: I ( [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006") ) wanted to cut $O(n \sqrt{n})$ memory because I thought that setting 1024 MB memory limit would spoil the solution. So only blame me for this.
    663 
    664 We will do a complementary problem which is finding the minimum loss of a coloring. The initial cost is the maximum possible cost, $n \cdot (n+1)$.
    665 
    666 If we analyze how good a bipartite coloring of the given tree is we can note that $loss \le 2 \cdot n$
    667 
    668 Now suppose the tree has a connected component of size $k$. We can note that in such a coloring $loss \ge \frac{k \cdot (k+1)}{2}$
    669 
    670 By the $2$ claims above, we can note that in an optimal coloring, the maximum size $k$ of a connected component respects $\frac{k \cdot (k+1)}{2} \le 2 \cdot n$. Thus we can safely say $k \le \sqrt{4 \cdot n}$.
    671 
    672 Now let $dp_{i,j,color}$ be the minimum loss if we color the subtree of $i$ and the connected component of vertex $i$ has size $j$. We can calculate this in a knapsack style by adding subtrees successively. The computation takes $O(n \cdot \sqrt{n})$ if we use the $7$-th trick from [this](https://codeforces.com/blog/entry/100910) blog.
    673 
    674 Now we are only left to optimize memory, since now it's $O(n \cdot \sqrt{n})$. We can directly apply [this](https://codeforces.com/blog/entry/113453) to get linear memory.
    675 
    676 However, the bound of $k \le \sqrt{4 \cdot n}$ is overestimated, for $n=200000$ it can be proven that the worst case for $k$ is $258$.
    677 
    678 **Proof Sketch**
    679 
    680 Assume have a connected component of size $k$ we want it to be colored $0$ across all optimal colorings. Then we can attach to each node some subtrees such that after flipping its whole subtree the total cost doesn't increase. We will assume all subtrees are leaves for simplicity. Doing such, we can get some inequalities about the number of leaves we need to attatch to each node.
    681 
    682 In a star tree, the number of leaves we should attatch to nodes has the smallest sum.
    683 
    684 **Code (tibinyte, C++)**
    685 
    686 ```
    687 #include <bits/stdc++.h>
    688 #define int long long
    689 
    690 using namespace std;
    691 
    692 const int lim = 893;
    693 const int inf = 1e16;
    694 
    695 struct dp_state
    696 {
    697     vector<int> a;
    698     vector<int> b;
    699     void init()
    700     {
    701         a.resize(lim + 1, inf);
    702         b.resize(lim + 1, inf);
    703         a[1] = 1;
    704         b[1] = 2;
    705     }
    706 };
    707 
    708 int32_t main()
    709 {
    710     cin.tie(nullptr)->sync_with_stdio(false);
    711     int q;
    712     cin >> q;
    713     while (q--)
    714     {
    715         int n;
    716         cin >> n;
    717         vector<vector<int>> g(n + 1);
    718         vector<int> sz(n + 1);
    719 
    720         for (int i = 1; i < n; ++i)
    721         {
    722             int x, y;
    723             cin >> x >> y;
    724             g[x].push_back(y);
    725             g[y].push_back(x);
    726         }
    727 
    728         function<int(int, int)> shuffle_kids = [&](int node, int parent)
    729         {
    730             int sz = 1;
    731             pair<int, int> best;
    732             for (int i = 0; i < (int)g[node].size(); ++i)
    733             {
    734                 if (g[node][i] != parent)
    735                 {
    736                     int sz2 = shuffle_kids(g[node][i], node);
    737 
    738                     best = max(best, {sz2, i});
    739 
    740                     sz += sz2;
    741                 }
    742             }
    743             if (!g[node].empty())
    744             {
    745                 swap(g[node][0], g[node][best.second]);
    746             }
    747             return sz;
    748         };
    749         shuffle_kids(1, 0);
    750 
    751         vector<vector<int>> merged(2 * lim + 1, vector<int>(2, inf));
    752 
    753         function<dp_state(int, int)> dfs = [&](int node, int parent)
    754         {
    755             dp_state dp;
    756             sz[node] = 1;
    757             bool hasinit = false;
    758             for (auto i : g[node])
    759             {
    760                 if (i != parent)
    761                 {
    762                     dp_state qui = dfs(i, node);
    763                     if (!hasinit)
    764                     {
    765                         dp.init();
    766                         hasinit = true;
    767                     }
    768                     for (int j = 0; j <= min(sz[node], lim) + min(sz[i], lim); ++j)
    769                     {
    770                         merged[j][0] = merged[j][1] = inf;
    771                     }
    772                     for (int k = 1; k <= min(sz[node], lim); ++k)
    773                     {
    774                         for (int l = 1; l <= min(sz[i], lim); ++l)
    775                         {
    776                             merged[k][0] = min(merged[k][0], dp.a[k] + qui.b[l]);
    777                             merged[k][1] = min(merged[k][1], dp.b[k] + qui.a[l]);
    778                             merged[k + l][0] = min(merged[k + l][0], dp.a[k] + qui.a[l] + k * l);
    779                             merged[k + l][1] = min(merged[k + l][1], dp.b[k] + qui.b[l] + k * l * 2);
    780                         }
    781                     }
    782                     sz[node] += sz[i];
    783                     for (int k = 1; k <= min(sz[node], lim); ++k)
    784                     {
    785                         dp.a[k] = merged[k][0];
    786                         dp.b[k] = merged[k][1];
    787                     }
    788                 }
    789             }
    790             if (!hasinit)
    791             {
    792                 dp.init();
    793                 hasinit = true;
    794             }
    795             return dp;
    796         };
    797         dp_state dp = dfs(1, 0);
    798         int ans = inf;
    799         for (int i = 1; i <= lim; ++i)
    800         {
    801             ans = min(ans, dp.a[i]);
    802             ans = min(ans, dp.b[i]);
    803         }
    804         cout << n * (n + 1) - ans << '\n';
    805     }
    806 }
    807 ```
    808 
    809 **Rate problem**
    810 
    811 Good problem
    812 
    813 Ok problem
    814 
    815 Bad problem
    816 
    817 Didn't solve it, idk
    818 
    819 ## [1830E — Bully Sort](https://codeforces.com/contest/1830/problem/E)
    820 
    821 Author: [cadmiumky](/profile/cadmiumky "Candidate Master cadmiumky")
    822 
    823 Thanks to [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") for the solution!
    824 
    825 **Solution**
    826 
    827 First of all, we notice that if some element moves left, it will never move right.
    828 
    829 **Proof**
    830 
    831 Proving this is not hard, imagine $S$ to be the set of suffix minimas. Then if an element is in $S$ we know that $p_x \le x$.
    832 
    833 Since after every bully swap an element cannot disappear from $S$ and after each bully swap, the $2$ swapped elements can only get closer to their desired position, we conclude the proof.
    834 
    835 Obviously, if an element moves right, it will never move left since it will continue to move right until it reaches its final position.
    836 
    837 By the $2$ claims above, we conclude that left and right movers are distinct.
    838 
    839 Now suppose we swap indicies $i$ and $j$ and note that such swap kills $2 \cdot (j-i) - 1$ inversions and the left mover $j$ moves $j-i$ steps.
    840 
    841 Now the magic is that if we let $s$ be the sum over $2 \cdot (i-p_i)$ for all left movers we have $s - ans = inversions$, thus our answer is just $s-inversions$.
    842 
    843 Now to handle the data structure part, we just need to be able to calculate inversions while being able to perform point updates. There are many ways to do this, for example for using a fenwick tree and a bitwise trie/ordered_set in $O(nlog^2n)$.
    844 
    845 **Code (tibinyte, fenwick tree + ordered_set C++)**
    846 
    847 ```
    848 #include <bits/stdc++.h>
    849 
    850 #include <ext/pb_ds/assoc_container.hpp>
    851 
    852 #include <ext/pb_ds/tree_policy.hpp>
    853 
    854 using namespace std;
    855 
    856 using namespace __gnu_pbds;
    857 
    858 #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
    859 
    860 typedef long long ll;
    861 
    862 /*               .___                 __                 __           .__
    863   ____  ____   __| _/____     _______/  |______ ________/  |_  ______ |  |__   ___________   ____
    864 _/ ___\/  _ \ / __ |/ __ \   /  ___/\   __\__  \\_  __ \   __\/  ___/ |  |  \_/ __ \_  __ \_/ __ \
    865 \  \__(  <_> ) /_/ \  ___/   \___ \  |  |  / __ \|  | \/|  |  \___ \  |   Y  \  ___/|  | \/\  ___/
    866  \___  >____/\____ |\___  > /____  > |__| (____  /__|   |__| /____  > |___|  /\___  >__|    \___  >
    867      \/           \/    \/       \/            \/                 \/       \/     \/            \/
    868 */
    869 
    870 struct bit
    871 {
    872   int n;
    873   vector<ordered_set> lesgo;
    874   void resize(int _n)
    875   {
    876     n = _n;
    877     lesgo = vector<ordered_set>(n + 1);
    878   }
    879   void update(int pos, int val, int sign)
    880   {
    881     for (int i = pos; i <= n; i += i & (-i))
    882     {
    883       if (sign == -1)
    884       {
    885         lesgo[i].erase(val);
    886       }
    887       if (sign == 1)
    888       {
    889         lesgo[i].insert(val);
    890       }
    891     }
    892   }
    893   int query_smaller(int pos, int val)
    894   {
    895     int ans = 0;
    896     for (int i = pos; i; i -= i & (-i))
    897     {
    898       ans += lesgo[i].order_of_key(val);
    899     }
    900     return ans;
    901   }
    902   int query_greater(int pos, int val)
    903   {
    904 
    905     int ans = 0;
    906     for (int i = pos; i; i -= i & (-i))
    907     {
    908       int sz = lesgo[i].size();
    909       ans += sz - lesgo[i].order_of_key(val + 1);
    910     }
    911     return ans;
    912   }
    913   int query_smaller(int st, int dr, int val)
    914   {
    915     return query_smaller(dr, val) - query_smaller(st - 1, val);
    916   }
    917   int query_greater(int st, int dr, int val)
    918   {
    919     return query_greater(dr, val) - query_greater(st - 1, val);
    920   }
    921 };
    922 
    923 int32_t main()
    924 {
    925   cin.tie(nullptr)->sync_with_stdio(false);
    926   int n, q;
    927   cin >> n >> q;
    928   vector<int> a(n + 1);
    929   for (int i = 1; i <= n; ++i)
    930   {
    931     cin >> a[i];
    932   }
    933   bit lesgo;
    934   lesgo.resize(n);
    935   for (int i = 1; i <= n; ++i)
    936   {
    937     lesgo.update(i, a[i], 1);
    938   }
    939 
    940   ll inv = 0;
    941 
    942   for (int i = 1; i <= n; ++i)
    943   {
    944     inv += lesgo.query_greater(1, i, a[i]);
    945   }
    946 
    947   ll sum = 0;
    948 
    949   for (int i = 1; i <= n; ++i)
    950   {
    951     sum += max(a[i] - i, 0);
    952   }
    953 
    954   while (q--)
    955   {
    956     int x, y;
    957     cin >> x >> y;
    958     if (x != y)
    959     {
    960       lesgo.update(x, a[x], -1);
    961       lesgo.update(y, a[y], -1);
    962       sum -= max(a[x] - x, 0);
    963       sum -= max(a[y] - y, 0);
    964       if (x + 1 <= y - 1)
    965       {
    966         int lesgo1 = lesgo.query_smaller(x + 1, y - 1, a[x]);
    967         int lesgo2 = lesgo.query_greater(x + 1, y - 1, a[y]);
    968         inv += 2 * (y - x - 1 - lesgo1 - lesgo2);
    969       }
    970 
    971       if (a[x] > a[y])
    972       {
    973         inv--;
    974       }
    975       else
    976       {
    977         inv++;
    978       }
    979 
    980       swap(a[x], a[y]);
    981       sum += max(a[x] - x, 0);
    982       sum += max(a[y] - y, 0);
    983       lesgo.update(x, a[x], 1);
    984       lesgo.update(y, a[y], 1);
    985     }
    986     cout << sum + sum - inv << '\n';
    987   }
    988 }
    989 ```
    990 
    991 **Code (tibinyte, sqrt decomposition, C++)**
    992 
    993 ```
    994 #include <bits/stdc++.h>
    995 
    996 using namespace std;
    997 
    998 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    999 
   1000 int random(int st, int dr)
   1001 {
   1002   uniform_int_distribution<int> dist(st, dr);
   1003   return dist(rng);
   1004 }
   1005 
   1006 typedef long long ll;
   1007 
   1008 /*               .___                 __                 __           .__
   1009   ____  ____   __| _/____     _______/  |______ ________/  |_  ______ |  |__   ___________   ____
   1010 _/ ___\/  _ \ / __ |/ __ \   /  ___/\   __\__  \\_  __ \   __\/  ___/ |  |  \_/ __ \_  __ \_/ __ \
   1011 \  \__(  <_> ) /_/ \  ___/   \___ \  |  |  / __ \|  | \/|  |  \___ \  |   Y  \  ___/|  | \/\  ___/
   1012  \___  >____/\____ |\___  > /____  > |__| (____  /__|   |__| /____  > |___|  /\___  >__|    \___  >
   1013      \/           \/    \/       \/            \/                 \/       \/     \/            \/
   1014 */
   1015 
   1016 struct decomp
   1017 {
   1018   vector<int> a;
   1019   vector<pair<int, int>> buckets;
   1020   vector<int> sp;
   1021   vector<int> spbucket;
   1022   vector<int> wh;
   1023   const int sz = 400;
   1024   void resize(int n)
   1025   {
   1026     a = vector<int>(n + 1);
   1027     sp = vector<int>(n + 1);
   1028     wh = vector<int>(n + 1);
   1029     for (int i = 1; i <= n; i += sz)
   1030     {
   1031       int st = i;
   1032       int dr = min(n, st + sz - 1);
   1033       for (int j = st; j <= dr; ++j)
   1034       {
   1035         wh[j] = (int)buckets.size();
   1036       }
   1037       buckets.push_back({st, dr});
   1038       spbucket.push_back(0);
   1039     }
   1040   }
   1041   void update(int pos, int x)
   1042   {
   1043     a[pos] += x;
   1044     int qui = wh[pos];
   1045     sp[buckets[qui].first] = a[buckets[qui].first];
   1046     for (int i = buckets[qui].first + 1; i <= buckets[qui].second; ++i)
   1047     {
   1048       sp[i] = sp[i - 1] + a[i];
   1049     }
   1050     spbucket[0] = sp[buckets[0].second];
   1051     for (int i = 1; i < (int)buckets.size(); ++i)
   1052     {
   1053       spbucket[i] = spbucket[i - 1] + sp[buckets[i].second];
   1054     }
   1055   }
   1056   int query(int pos)
   1057   {
   1058     int qui = wh[pos];
   1059     int ans = sp[pos];
   1060     if (qui)
   1061     {
   1062       ans += spbucket[qui - 1];
   1063     }
   1064     return ans;
   1065   }
   1066 };
   1067 
   1068 struct geralt
   1069 {
   1070   vector<int> a;
   1071   vector<decomp> lesgo;
   1072   vector<pair<int, int>> buckets;
   1073   vector<int> wh;
   1074   const int sz = 3000;
   1075   void resize(int n)
   1076   {
   1077     a = vector<int>(n + 1);
   1078     wh = vector<int>(n + 1);
   1079     for (int i = 1; i <= n; i += sz)
   1080     {
   1081       int st = i;
   1082       int dr = min(n, st + sz - 1);
   1083       for (int j = st; j <= dr; ++j)
   1084       {
   1085         wh[j] = (int)buckets.size();
   1086       }
   1087       buckets.push_back({st, dr});
   1088       lesgo.push_back({});
   1089       lesgo.back().resize(n);
   1090     }
   1091   }
   1092   void update(int pos, int val)
   1093   {
   1094     int qui = wh[pos];
   1095     if (a[pos] != 0)
   1096     {
   1097       lesgo[qui].update(a[pos], -1);
   1098     }
   1099     a[pos] = val;
   1100     lesgo[qui].update(a[pos], 1);
   1101   }
   1102   int query_brute(int st, int dr, int val)
   1103   {
   1104     int ans = 0;
   1105     for (int i = st; i <= dr; ++i)
   1106     {
   1107       if (a[i] <= val)
   1108       {
   1109         ans++;
   1110       }
   1111     }
   1112     return ans;
   1113   }
   1114   int query_smaller(int st, int dr, int val) // number of values <= val in st...dr
   1115   {
   1116     if (wh[st] == wh[dr])
   1117     {
   1118       return query_brute(st, dr, val);
   1119     }
   1120     int qui1 = wh[st], qui2 = wh[dr];
   1121     int ans = query_brute(st, buckets[qui1].second, val) + query_brute(buckets[qui2].first, dr, val);
   1122     qui1++;
   1123     qui2--;
   1124     for (int i = qui1; i <= qui2; ++i)
   1125     {
   1126       ans += lesgo[i].query(val);
   1127     }
   1128     return ans;
   1129   }
   1130   int query_greater(int st, int dr, int val) // number of values > val in st...dr
   1131   {
   1132     return (dr - st + 1) - query_smaller(st, dr, val);
   1133   }
   1134 };
   1135 
   1136 int32_t main()
   1137 {
   1138   cin.tie(nullptr)->sync_with_stdio(false);
   1139   int n, q;
   1140   cin >> n >> q;
   1141   vector<int> a(n + 1);
   1142   for (int i = 1; i <= n; ++i)
   1143   {
   1144     cin >> a[i];
   1145   }
   1146 
   1147   geralt lesgo;
   1148   lesgo.resize(n);
   1149 
   1150   ll inv = 0;
   1151 
   1152   for (int i = 1; i <= n; ++i)
   1153   {
   1154     lesgo.update(i, a[i]);
   1155     inv += lesgo.query_greater(1, i, a[i]);
   1156   }
   1157 
   1158   ll sum = 0;
   1159 
   1160   for (int i = 1; i <= n; ++i)
   1161   {
   1162     sum += max(a[i] - i, 0);
   1163   }
   1164 
   1165   while (q--)
   1166   {
   1167     int x, y;
   1168     cin >> x >> y;
   1169     if (x != y)
   1170     {
   1171       sum -= max(a[x] - x, 0);
   1172       sum -= max(a[y] - y, 0);
   1173       if (x + 1 <= y - 1)
   1174       {
   1175         int lesgo1 = lesgo.query_smaller(x + 1, y - 1, a[x]);
   1176         int lesgo2 = lesgo.query_greater(x + 1, y - 1, a[y]);
   1177         inv += 2 * (y - x - 1 - lesgo1 - lesgo2);
   1178       }
   1179 
   1180       if (a[x] > a[y])
   1181       {
   1182         inv--;
   1183       }
   1184       else
   1185       {
   1186         inv++;
   1187       }
   1188 
   1189       swap(a[x], a[y]);
   1190       sum += max(a[x] - x, 0);
   1191       sum += max(a[y] - y, 0);
   1192       lesgo.update(x, a[x]);
   1193       lesgo.update(y, a[y]);
   1194     }
   1195     cout << sum + sum - inv << '\n';
   1196   }
   1197 }
   1198 ```
   1199 
   1200 **Code (errorgorn, divide and conquer, C++)**
   1201 
   1202 ```
   1203 #include <bits/stdc++.h>
   1204 using namespace std;
   1205 
   1206 #define ll long long
   1207 #define ii pair<int,int>
   1208 #define i4 tuple<int,int,int,int>
   1209 #define fi first
   1210 #define se second
   1211 #define endl '\n'
   1212 #define debug(x) cout << #x << ": " << x << endl
   1213 
   1214 #define pub push_back
   1215 #define pob pop_back
   1216 #define puf push_front
   1217 #define pof pop_front
   1218 #define lb lower_bound
   1219 #define ub upper_bound
   1220 
   1221 #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
   1222 #define all(x) (x).begin(),(x).end()
   1223 #define sz(x) (int)(x).size()
   1224 
   1225 mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
   1226 
   1227 struct FEN{ //we want to count the reverse
   1228 	int arr[500005];
   1229 	
   1230 	void update(int i,int k){
   1231 		i=500005-i;
   1232 		
   1233 		while (i<500005){
   1234 			arr[i]+=k;
   1235 			i+=i&-i;
   1236 		}
   1237 	}
   1238 	
   1239 	int query(int i){
   1240 		i=500005-i;
   1241 		
   1242 		int res=0;
   1243 		while (i){
   1244 			res+=arr[i];
   1245 			i-=i&-i;
   1246 		}
   1247 		return res;
   1248 	}
   1249 } fen;
   1250 
   1251 int n,q;
   1252 int arr[500005];
   1253 long long ans[50005];
   1254 
   1255 void dnc(int l,int r,vector<i4> upd,vector<i4> que){
   1256 	vector<i4> updl,updr;
   1257 	vector<i4> quel,quer;
   1258 	
   1259 	int m=l+r>>1;
   1260 	
   1261 	for (auto [a,b,c,d]:upd){
   1262 		if (c<=m) updl.pub({a,b,c,d});
   1263 		else updr.pub({a,b,c,d});
   1264 	}
   1265 	
   1266 	for (auto [a,b,c,d]:que){
   1267 		if (c<=m) quel.pub({a,b,c,d});
   1268 		else quer.pub({a,b,c,d});
   1269 	}
   1270 	
   1271 	int i=0;
   1272 	for (auto it:quer){
   1273 		while (i<sz(updl) && get<0>(updl[i])<get<0>(it)){
   1274 			fen.update(get<1>(updl[i]),get<3>(updl[i]));
   1275 			i++;
   1276 		}
   1277 		
   1278 		ans[get<2>(it)]+=fen.query(get<1>(it))*get<3>(it);
   1279 	}
   1280 	while (i){
   1281 		i--;
   1282 		fen.update(get<1>(updl[i]),-get<3>(updl[i]));
   1283 	}
   1284 	
   1285 	if (l!=m) dnc(l,m,updl,quel);
   1286 	if (m+1!=r) dnc(m+1,r,updr,quer);
   1287 }
   1288 
   1289 signed main(){
   1290 	ios::sync_with_stdio(0);
   1291 	cin.tie(0);
   1292 	cout.tie(0);
   1293 	cin.exceptions(ios::badbit | ios::failbit);
   1294 	
   1295 	cin>>n>>q;
   1296 	rep(x,1,n+1) cin>>arr[x];
   1297 	
   1298 	vector<i4> upd,que;
   1299 	
   1300 	rep(x,1,n+1) upd.pub({x,arr[x],-1,1});
   1301 	rep(x,1,n+1) que.pub({x,arr[x],0,-1});
   1302 	rep(x,1,n+1) ans[0]+=abs(x-arr[x]);
   1303 	
   1304 	rep(x,1,q+1){
   1305 		int a,b;
   1306 		cin>>a>>b;
   1307 		
   1308 		if (a==b) continue;
   1309 		if (arr[a]<arr[b]) ans[x]--;
   1310 		else ans[x]++;
   1311 		
   1312 		upd.pub({a,arr[a],x-1,-1});
   1313 		upd.pub({b,arr[b],x-1,-1});
   1314 		ans[x]-=abs(a-arr[a])+abs(b-arr[b]);
   1315 		
   1316 		swap(arr[a],arr[b]);
   1317 		
   1318 		upd.pub({a,arr[a],x,1});
   1319 		upd.pub({b,arr[b],x,1});
   1320 		ans[x]+=abs(a-arr[a])+abs(b-arr[b]);
   1321 		
   1322 		que.pub({b,arr[b],x,-2});
   1323 		que.pub({b,arr[a],x,2});
   1324 		que.pub({a,arr[b],x,2});
   1325 		que.pub({a,arr[a],x,-2});
   1326 		
   1327 	}
   1328 	
   1329 	sort(all(upd)),sort(all(que));
   1330 	
   1331 	dnc(-1,q,upd,que);
   1332 	
   1333 	rep(x,1,q+1) ans[x]+=ans[x-1];
   1334 	rep(x,1,q+1) cout<<ans[x]<<" "; cout<<endl;
   1335 }
   1336 ```
   1337 
   1338 **Rate problem**
   1339 
   1340 Good problem
   1341 
   1342 Ok problem
   1343 
   1344 Bad problem
   1345 
   1346 Didn't solve it, idk
   1347 
   1348 ## [1830F — The Third Grace](https://codeforces.com/contest/1830/problem/F)
   1349 
   1350 Author: [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006")
   1351 
   1352 Thanks to [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") for the editorial!
   1353 
   1354 **Solution**
   1355 
   1356 Let $dp_i$ be the maximum sum of costs of activated points that are $ \lt i$ over all states that has point $i$ activated.
   1357 
   1358 When we transition from $dp_i$ to $dp_j$, we need to add the cost contributed by point $i$. The number of ranges where point $i$ is the largest coordinate within it are the ranges $[l,r]$ which satisfy $l \leq i \leq r \lt j$. So we have $dp_j = \max\limits_{i \lt j}(dp_i + p_i \cdot S_{i,j})$ where $S_{i,j}$ is the number of ranges $[l,r]$ which satisfy $l \leq i \leq r \lt j$. Now, we note that $S_{i,j} z$
   1359 
   1360 With some work, we can get calculate this $dp$ in $O(n^2)$. But this will be too slow, let's try to speed this up.
   1361 
   1362 Let us define $dp_{i,j} = \max\limits_{k \leq i}(dp_k + p_k \cdot S_{k,j})$. We have $dp_{j-1,j}=dp_j$. Our goal is to go from (implictly) storing $dp_{i,i+1},dp_{i,i+2},\ldots,dp_{i,n}$ to $dp_{i+1,i+2},dp_{i+1,i+3},\ldots,dp_{i+1,n}$. As $dp_i + p_i \cdot S_{i,j}$ looks like a linear function w.r.t. $S_{i,j}$, we can try to use convex hull data structures to maintain it.
   1363 
   1364 Let's figure out how $S_{i+1,j}$ relates to $S_{i,j}$. We need to subtract the number of ranges with $r=i$ and add the number of ranges with $l=i+1$ and $r \lt j$. This corresponds to $S_{i,*}$ and $S_{i+1,*}$ differing by amortized $O(1)$ suffix increment updates. Also, note that $S_{i,*}$ is non-decreasing.
   1365 
   1366 So we want to support the following data structure: Initially we have an arrays $A$ and $X$ that are both initially $0$. Handle the following updates:
   1367 
   1368 * `1 m c` $A_i \gets \max(A_i,m \cdot X_i + c)$ for all $i$
   1369 * `2 j k` $X_i \gets X_i + k$ for all $j \leq i$. It is guaranteed that $X$ will always be non-decreasing.
   1370 * `3 i` find $A_i$
   1371 
   1372 This can be maintained in a lichao tree in $O(log ^2)$ time. In each lichao node, we need to store $s,m,e$, the start, middle and end indices and their corresponding $X$ values $X_s,X_m,X_e$ respectively. This way, we can support operations $1$ and $3$ already.
   1373 
   1374 To support operation $2$, note that in a lichao tree, you can use $O(log^2)$ time to push down all lines that covers a certain point (refer to <https://codeforces.com/blog/entry/86731)>. This way, all lines in the li chao tree are in $[1,j)$ or $[j,n]$, so you can do lazy updates on both the coordinates of the lines and the $X$ values.
   1375 
   1376 The time complexity is $O(n \log^2)$.
   1377 
   1378 There is another solution that works in $O(m \log^3)$ that we are unable to optimize further yet. Let us flip the array so that the condition is on the activated point with the smallest coordinate. Then we have $dp_j = \max\limits_{i \lt j}(dp_i + p_j \cdot S_{i,j})$ where $S_{i,j}$ counts the number of ranges $[l,r]$ such that $i \lt l \leq j \leq r$.
   1379 
   1380 Now, we want to store the linear function $dp_i + x \cdot S_{i,j}$ in some sort of data structure so that we can evaluate the maximum value with $x=p_j$. Unfortunately, the value of $S_{i,j}$ can change by suffix additions, similar to above.
   1381 
   1382 But since $S_{i,j}$ is non-increasing here, that means the optimal $i$ that maximizes $dp_i + x \cdot S_{i,j}$ decreases when $x$ increases. That is, for $l_1 \leq r_1 \lt l_2 \leq r_2$ and we have two data structures that can get the maximum $f_j(x)=dp_i+x \cdot S_{i,j}$ for $l_j \leq i \leq r_j$ respectively. We can combine these $2$ data structures to make it for $[l_1,r_1] \cup [l_2,r_2]$ by binary searching the point $X$ where for all $x \leq X$, $f_1(x) \leq f_2(x)$ and for all $X \leq x,f_1(x) \geq f_2(x)$. Since querying this data structure takes $O(\log n)$, it takes $O(\log ^2)$ time to combine two such data structures. If we use a segment tree, we only need to rebuild $O(\log^3)$ different data structures (the rest can be handled using lazy tags), giving us a time complexity of $O(\log^3)$.
   1383 
   1384 **Code (errorgorn, C++)**
   1385 
   1386 ```
   1387 //もう布団の中から出たくない
   1388 //布団の外は寒すぎるから
   1389 //布団の中から出たくない
   1390 //布団の中はあたたかすぎるから
   1391 
   1392 #include <bits/stdc++.h>
   1393 using namespace std;
   1394 
   1395 #pragma GCC optimize("O3,unroll-loops")
   1396 #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
   1397 
   1398 #define int long long
   1399 #define ll long long
   1400 #define ii pair<ll,ll>
   1401 #define iii pair<ii,ll>
   1402 #define fi first
   1403 #define se second
   1404 #define endl '\n'
   1405 #define debug(x) cout << #x << ": " << x << endl
   1406 
   1407 #define pub push_back
   1408 #define pob pop_back
   1409 #define puf push_front
   1410 #define pof pop_front
   1411 #define lb lower_bound
   1412 #define ub upper_bound
   1413 
   1414 #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
   1415 #define all(x) (x).begin(),(x).end()
   1416 #define sz(x) (int)(x).size()
   1417 
   1418 mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
   1419 
   1420 const ll INF=1e18;
   1421 
   1422 struct line{
   1423 	ll m,c;
   1424 	
   1425 	line (ll _m,ll _c){
   1426 		m=_m,c=_c;
   1427 	}
   1428 	
   1429 	ll get(ll x){
   1430 		return m*x+c;
   1431 	}
   1432 };
   1433 
   1434 struct node{
   1435 	int s,e,m;
   1436 	int vs=0,ve=0,vm=0;
   1437 	line val={0,-INF};
   1438 	int lazy=0;
   1439 	node *l,*r;
   1440 	
   1441 	node(int _s,int _e){
   1442 		s=_s,e=_e,m=s+e>>1;
   1443 		
   1444 		if (s!=e){
   1445 			l=new node(s,m);
   1446 			r=new node(m+1,e);
   1447 		}
   1448 	}
   1449 	
   1450 	void propo(){
   1451 		if (lazy==0) return;
   1452 		
   1453 		val.c-=val.m*lazy;
   1454 		vs+=lazy;
   1455 		ve+=lazy;
   1456 		vm+=lazy;
   1457 		
   1458 		if (s!=e){
   1459 			l->lazy+=lazy;
   1460 			r->lazy+=lazy;
   1461 		}
   1462 		lazy=0;
   1463 	}
   1464 	
   1465 	void update(int i){
   1466 		if (s==i) lazy++;
   1467 		else{
   1468 			if (val.c!=-INF){
   1469 				l->propo(),r->propo();
   1470 				l->update(val),r->update(val);
   1471 				val={0,-INF};
   1472 			}
   1473 			
   1474 			if (m<i) r->update(i);
   1475 			else l->update(i),r->update(m+1);
   1476 			
   1477 			l->propo(),r->propo();
   1478 			vs=l->vs,vm=l->ve,ve=r->ve;
   1479 		}
   1480 	}
   1481 	
   1482 	void update(line i){
   1483 		bool lo=i.get(vs)>val.get(vs);
   1484 		bool mi=i.get(vm)>val.get(vm);
   1485 		bool hi=i.get(ve)>val.get(ve);
   1486 		
   1487 		if (mi) swap(i,val);
   1488 		
   1489 		if (s==e || i.c==-INF || lo==hi) return;
   1490 		
   1491 		l->propo(),r->propo();
   1492 		if (lo!=mi) l->update(i);
   1493 		else r->update(i);
   1494 	}
   1495 	
   1496 	ii query(ll i){
   1497 		propo();
   1498 		
   1499         if (s==e) return {val.get(vs),vs};
   1500 		else if (i<=m){
   1501 			auto temp=l->query(i);
   1502 			return {max(temp.fi,val.get(temp.se)),temp.se};
   1503 		}
   1504 		else{
   1505 			auto temp=r->query(i);
   1506 			return {max(temp.fi,val.get(temp.se)),temp.se};
   1507 		}
   1508 	}
   1509 } *root;
   1510 
   1511 const int maxn = 1e6;
   1512 const int maxm = 1e6;
   1513 
   1514 int n,m;
   1515 ii arr[maxn+1];
   1516 ii brr[maxm+1];
   1517 
   1518 int ans[maxm+1];
   1519 
   1520 signed main(){
   1521 	ios::sync_with_stdio(0);
   1522 	cin.tie(0);
   1523 	cout.tie(0);
   1524 	cin.exceptions(ios::badbit | ios::failbit);
   1525 	
   1526 	int TC;
   1527 	cin>>TC;
   1528 	while (TC--){
   1529 		cin>>n>>m;
   1530 		rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se;
   1531 		rep(x,1,m+1){
   1532             cin>>brr[x].se;
   1533             brr[x].fi = x;
   1534         }
   1535     
   1536 		sort(arr+1,arr+n+1);
   1537 		
   1538 		root=new node(0,m+1);
   1539 		root->update({0,0});
   1540 		
   1541 		int curr=1;
   1542 		rep(x,0,m+2){
   1543 			while (curr<=n && arr[curr].fi==x) root->update(arr[curr++].se+1);
   1544 			auto temp=root->query(x);
   1545 			root->update({brr[x].se,temp.fi-brr[x].se*temp.se});
   1546 		}
   1547 		
   1548 		cout<<root->query(m+1).fi<<endl;
   1549 	}
   1550 }
   1551 ```
   1552 
   1553 **Code (valeriu, C++)**
   1554 
   1555 ```
   1556 #include <bits/stdc++.h>
   1557 #define all(x) (x).begin(),(x).end()
   1558 using namespace std;
   1559 
   1560 using ll = long long;
   1561 using ld = long double;
   1562 
   1563 //#define int ll
   1564 #define sz(x) ((int)(x).size())
   1565 
   1566 using pii = pair<ll,ll>;
   1567 using tii = tuple<int,int,int>;
   1568 
   1569 const int nmax = 5e5 + 5, qmax = 2e6 + 5;
   1570 const ll inf = 1e18 + 5; 
   1571 
   1572 struct line {
   1573   ll m = 0, b = -inf;
   1574   ll operator()(const ll& x) const {
   1575      return m * x + b;
   1576   }
   1577   bool operator ==(const line& x) const { return m == x.m && b == x.b; }
   1578 };
   1579 
   1580 int M;
   1581 
   1582 namespace AINT {
   1583   struct Node {
   1584     int vl = 0, vmid = 0, vr = 0;
   1585     line val = line{0, -inf};
   1586     Node() {;}
   1587     void operator += (const int &x) { vl += x, vmid += x, vr += x; val.b -= val.m * x; }
   1588   } aint[qmax * 4];
   1589   int lazy[qmax * 4];
   1590   
   1591   void push(int node) {
   1592     lazy[2 * node] += lazy[node];
   1593     aint[2 * node] += lazy[node];
   1594     lazy[2 * node + 1] += lazy[node];
   1595     aint[2 * node + 1] += lazy[node];
   1596     lazy[node] = 0;
   1597   }
   1598   void pushline(line x, int node = 1, int cl = 0, int cr = M) {
   1599     bool l = x(aint[node].vl) > aint[node].val(aint[node].vl), m = x(aint[node].vmid) > aint[node].val(aint[node].vmid), r = x(aint[node].vr) > aint[node].val(aint[node].vr);
   1600     if(m) swap(x, aint[node].val);
   1601     if(cl == cr || x == line() || l == r) return;
   1602     
   1603     int mid = cl + cr >> 1;
   1604     push(node);
   1605     if(m != l) pushline(x, 2 * node, cl, mid);
   1606     else pushline(x, 2 * node + 1, mid + 1, cr);
   1607     return;
   1608   }
   1609   void add(int l, int node = 1, int cl = 0, int cr = M) {
   1610     if(cl >= l) {
   1611       lazy[node]++;
   1612       aint[node] += 1;
   1613       return;
   1614     }
   1615     if(cr < l) return;
   1616     int mid = cl + cr >> 1;
   1617     
   1618     push(node);
   1619     
   1620     pushline(aint[node].val, 2 * node, cl, mid);
   1621     pushline(aint[node].val, 2 * node + 1, mid + 1, cr);
   1622     aint[node].val = line{0, -inf};
   1623     
   1624     add(l, 2 * node, cl, mid);
   1625     add(l, 2 * node + 1, mid + 1, cr);
   1626     aint[node].vl = aint[2 * node].vl;
   1627     aint[node].vmid = aint[2 * node].vr;
   1628     aint[node].vr = aint[2 * node + 1].vr;
   1629   }
   1630   pii query(ll p, int node = 1, int cl = 0, int cr = M) {
   1631     if(cl == cr) return pii{aint[node].val(aint[node].vl), aint[node].vl};
   1632     int mid = cl + cr >> 1;
   1633     push(node);
   1634     auto [mxv, atrv] = p <= mid? query(p, 2 * node, cl, mid) : query(p, 2 * node + 1, mid + 1, cr);
   1635     return pii{max(mxv, aint[node].val(atrv)), atrv};
   1636   } 
   1637   
   1638   void init(int node = 1, int cl = 0, int cr = M) {
   1639     aint[node] = Node();
   1640     lazy[node] = 0;
   1641     if(cl == cr) return;
   1642     int mid = cl + cr >> 1;
   1643     init(2 * node, cl, mid);
   1644     init(2 * node + 1, mid + 1, cr);
   1645     return;
   1646   }
   1647 };
   1648 
   1649 vector<int> atraddp[qmax];
   1650 ll val[qmax];
   1651 
   1652 void testcase() {
   1653   int n, m;
   1654   cin >> n >> m;
   1655   M = m + 2;
   1656   for(int i = 0, l, r; i < n; i++) {
   1657     cin >> l >> r;
   1658     atraddp[l].emplace_back(r + 1);
   1659   }
   1660   for(int i = 1; i <= m; i++)
   1661     cin >> val[i];
   1662   
   1663   AINT::init();
   1664   AINT::pushline({0, 0});
   1665   
   1666   for(int i = 0; i < m + 2; i++) {
   1667     for(auto x : atraddp[i])
   1668       AINT::add(x);
   1669     auto [a, b] = AINT::query(i);
   1670     //cerr << a << ' ' << b << '\n';
   1671     AINT::pushline({val[i], a - val[i] * b});
   1672   }
   1673   
   1674   for(int i = 0; i < m + 2; i++)
   1675     atraddp[i].clear();
   1676   
   1677   cout << AINT::query(m + 1).first << '\n';
   1678 }
   1679 
   1680 signed main() {
   1681   cin.tie(0) -> sync_with_stdio(0);
   1682   int t;
   1683   cin >> t;
   1684   while(t--) testcase();
   1685   
   1686 }
   1687 
   1688 /**
   1689       Anul asta se da centroid.
   1690 -- Surse oficiale
   1691 */
   1692 ```
   1693 
   1694 **Rate problem**
   1695 
   1696 Good problem
   1697 
   1698 Ok problem
   1699 
   1700 Bad problem
   1701 
   1702 Didn't solve it, idk
   1703 
   1704 If there is anything wrong or unclear in this editorial, feel free to ping me or any of the other authors in the comments.