codeforces-scrape

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

2030.md (33902B)


      1 Source: https://codeforces.com/blog/entry/135218
      2 
      3 Below is a timeline of the changes made to the round from start to finish. I hope this can depict what setting a contest is actually like for aspiring problemsetters. Please give me feedback about this in the comments. What else about the round would you like to know? Was this helpful?
      4 
      5 **Round Timeline**
      6 
      7 To denote problems, I will use quotes to denote the number of problems proposed for that postion so far (e.g. A' represents the first A proposed for the round, A'' represents second A proposed, etc). If the problem is in the final set, then it will be **bolded**. For dates, I will use the american standard notation (mm/dd).
      8 
      9 Also, I will not go in detail about why problems were rejected/unused because they might appear in the future.
     10 
     11 8/11: [Codeforces Round 965 (Div. 2)](/contest/1998 "Codeforces Round 965 (Div. 2)") has just concluded and [sum](/profile/sum "Мастер sum") has shipped himself off to college and won't have time due to ~~attending frat parties~~ his studies. I invite [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") to problemset with me. We decide to get cooking straight away.
     12 
     13 8/12: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes D'. Gets accepted.
     14 
     15 8/13: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes E'. Problem accepted for backup.
     16 
     17 8/14: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes D''. Problem accepted for backup.
     18 
     19 8/19: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes E'', F' and G'. Both gets accepted for main set at the time. Seriously, bro just became the new BledDest.
     20 
     21 8/21: We got bored and decided to focus on [Codeforces Round 971 (Div. 4)](/contest/2009 "Codeforces Round 971 (Div. 4)"). Due to difficulty issues, we transfered problem E from that contest to problem B1 and B2 for this contest. B2 ultimately became **D** :)
     22 
     23 8/22: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes B', but [satyam343](/profile/satyam343 "Мастер satyam343") buffs it into **F** instead. Somewhere along the lines I also came up with A' and B'', both getting initially accepted.
     24 
     25 8/23: Round gets put up for testing with 7 problems.
     26 
     27 8/25: I came up with an idea for D'''. Also, [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes **C**, but initially gets ignored lmao.
     28 
     29 8/26: [satyam343](/profile/satyam343 "Мастер satyam343") modifies B'' into D''''. Later, I also propose E''''.
     30 
     31 8/28: [satyam343](/profile/satyam343 "Мастер satyam343") tries to modifies B'' again into C''. [sum](/profile/sum "Мастер sum") wakes up from his slumber and proposes F''.
     32 
     33 8/29: I propose A''.
     34 
     35 8/31: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes D''''' and gets accepted.
     36 
     37 9/2: [satyam343](/profile/satyam343 "Мастер satyam343") buffs D''' and it became [NOTEQUALTREE](https://www.codechef.com/problems/NOTEQUALTREE).
     38 
     39 9/6: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") and [satyam343](/profile/satyam343 "Мастер satyam343") modifies D' and it becomes **G** (G1). Later, [A_G](/profile/A_G "Международный гроссмейстер A_G") solved it in subquadratic, and it became G2.
     40 
     41 9/9: I modify B'' into D''''''.
     42 
     43 9/11: [satyam343](/profile/satyam343 "Мастер satyam343") modifies B'' into D'''''''. We hold a poll in our testing server to choose the victor among D'''''' and D'''''''.
     44 
     45 9/12: I invent and propose C''', but wasn't accepted. [satyam343](/profile/satyam343 "Мастер satyam343") modifies B'' into D'''''''', but unused due to difficulty issues.
     46 
     47 9/14: I invent and propose D''''''''', which was unused due to difficulty issues. Later that night, the aforementioned poll concludes, crowning D'''''' with 7 votes to 2. However, both candidates had difficulty issues so we still decided against using any of them (essentially we polled for nothing).
     48 
     49 9/15: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes B'''' and gets initially accepted, however, was later rejected.
     50 
     51 9/17: I propose A''' but it wasn't great.
     52 
     53 9/20: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") brings **C** up again and it gets prepared.
     54 
     55 9/23: [satyam343](/profile/satyam343 "Мастер satyam343") modifies B'' into D'''''''''', but as the original author of B'', I didn't like it.
     56 
     57 9/24: [satyam343](/profile/satyam343 "Мастер satyam343") modifies D''''''''' into D''''''''''', and it gets prepared.
     58 
     59 9/28: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") modifies a unused problem I proposed for [Codeforces Round 965 (Div. 2)](/contest/1998 "Codeforces Round 965 (Div. 2)") into A'''', but unused due to difficulty issues.
     60 
     61 9/30: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes and prepares **B**. Later that night, [satyam343](/profile/satyam343 "Мастер satyam343") has conflicting thoughts whether to replace D''''''''''' yet again, but I  ~~held him at gunpoint to accept the problem~~  spent 30 minutes convincing him that it is a good problem. This problem became **E**. For those of you who enjoyed the problem, you're welcome lmao.
     62 
     63 10/02 — 10/17: Final testing and preparation.
     64 
     65 10/13: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") proposes current **A**.
     66 
     67 ## Please check out this amazing animated [video tutorial](https://www.youtube.com/watch?v=CpSIK4YPi00) by one of our beloved testers [redpanda](/profile/redpanda "Эксперт redpanda")!!!
     68 
     69 #### [2030A - Подарок от орангутана](/contest/2030/problem/A "Codeforces Round 979 (Div. 2)")
     70 
     71 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED")   
     72  Analysis: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED")
     73 
     74 **Solution** 
     75 
     76 First, what is the maximum possible value of $c_i-b_j$ for any $i,j$? Since $c_i$ is the maximum element of some subset of $a$ and $b_i$ is the minimum element of some subset of $a$, the maximum possible value of $c_i-b_j$ is $max(a)-min(a)$.
     77 
     78 Also note that $c_1=b_1$ for any reordering of $a$. By reordering such that the largest element of $a$ appears first and the smallest element of $a$ appears second, the maximum possible value of the score is achieved. This results in a score of $(max(a)-min(a))\cdot(n-1)$.
     79 
     80 **Code (Python)**
     81 
     82 ```
     83 for i in range(int(input())):
     84     n = int(input())
     85     mx = 0
     86     mn= 1000000
     87     lst = input().split()
     88     for j in range(n):
     89         x = int(lst[j])
     90         mx = max(mx, x)
     91         mn = min(mn, x)
     92     print((mx-mn)*(n-1))
     93 ```
     94 
     95 #### [2030B - Минимизируйте единичность](/contest/2030/problem/B "Codeforces Round 979 (Div. 2)")
     96 
     97 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED")   
     98  Analysis: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED")
     99 
    100 **Solution** 
    101 
    102 **Observation**: $f(t)-g(t)$ is odd.
    103 
    104 Proof: $f(t)+g(t)$ is the set of all non-empty subsets of $t$, which is $2^{|t|}-1$, which is odd. The sum and difference of two integers has the same parity, so $f(t)-g(t)$ is always odd.
    105 
    106 By including exactly one $1$ in the string $s$, we can make $f(s)=2^{n-1}-1$ and $g(s)=2^{n-1}$, or $f(s)-g(s)=1$ by the multiplication principle. Clearly, this is the best we can do. So, we print out any string with exactly one $1$.
    107 
    108 **Code (C++)**
    109 
    110 ```
    111 #include <bits/stdc++.h>
    112 using namespace std;
    113 
    114 int main() {
    115     int t;
    116     cin >> t;
    117     while(t--) {
    118         int n;
    119         cin >> n;
    120         cout << '1';
    121         for(int i = 1; i < n; i++) cout << '0';
    122         cout << endl;
    123     }
    124 }
    125 ```
    126 
    127 #### [2030C - ИСТИННАЯ битва](/contest/2030/problem/C "Codeforces Round 979 (Div. 2)")
    128 
    129 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED")   
    130  Analysis: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED")
    131 
    132 **Solution** 
    133 
    134 Let's understand what Alice wants to do. She wants to separate a statement that evaluates to `true` between two `or`'s. This guarantees her victory since `or` is evaluated after all `and`'s.
    135 
    136 First, if the first or last boolean is `true`, then Alice instantly wins by placing `or` between the first and second, or second to last and last booleans.
    137 
    138 Otherwise, if there are two `true`'s consecutively, Alice can also win. Alice may place `or` before the first of the two on her first move. If Bob does not put his operator between the two `true`'s, then Alice will put an `or` between the two `true`'s on her next move and win. Otherwise, Bob does place his operator between the two `true`'s. However, no matter what Bob placed, the two `true`'s will always evaluate to `true`, so on her second move Alice can just place an `or` on the other side of the two `true`'s to win.
    139 
    140 We claim these are the only two cases where Alice wins. This is because otherwise, there does not contain two `true`'s consecutively. Now, whenever Alice places an `or` adjacent to a `true`, Bob will respond by placing `and` after the `true`, which will invalidate this clause to be false.
    141 
    142 **Code (C++)**
    143 
    144 ```
    145 #include <bits/stdc++.h>
    146 using namespace std;
    147 
    148 int main() {
    149     int t;
    150     cin >> t;
    151     while(t--) {
    152         int n;
    153         cin >> n;
    154         string s;
    155         cin >> s;
    156         vector<int> v(n);
    157         for(int i = 0; i < n; i++) {
    158             if(s[i]=='1') v[i]=1;
    159         }
    160         bool win = false;
    161         if(v[0]||v[n-1]) win=true;
    162         for(int i = 1; i < n; i++) {
    163             if(v[i]&&v[i-1]) win=true;
    164         }
    165         if(win) cout << "YES" << endl;
    166         else cout << "NO" << endl;
    167     }
    168 }
    169 ```
    170 
    171 #### [2030D - Любимая перестановка ЧТД](/contest/2030/problem/D "Codeforces Round 979 (Div. 2)")
    172 
    173 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED"), [cry](/profile/cry "Международный мастер cry")   
    174  Analysis: [cry](/profile/cry "Международный мастер cry")
    175 
    176 **Solution** 
    177 
    178 Observation: Through a series of swaps, we can swap an element from position $i$ to position $j$ (WLOG, assume $i \lt j$) if there is no such $k$ such that $i \leq k \lt j$ such that $s_k = \texttt{L}$ and $s_{k+1} = \texttt{R}$.
    179 
    180 Let's mark all indices $i$ such that $s_i = \texttt{L}$ and $s_{i+1} = \texttt{R}$ as bad. If $pos_i$ represents the position of $i$ in $p$, then we must make sure it is possible to swap from $\min(i, pos_i)$ to $\max(i, pos_i)$. As you can see, we can model these conditions as intervals. We must make sure there are no bad indices included in any intervals.
    181 
    182 We need to gather indices $i$ such that $i$ is included in at least one interval. This can be done with difference array. Let $d_i$ denote the number of intervals that include $i$. If $d_i \gt 0$, then we need to make sure $i$ is not a bad index.
    183 
    184 We can keep all bad indices in a set. Notice that when we update $i$, we can only potentially toggle indices $i$ and $i-1$ from good to bad (or vice versa). For example, if $s_i = \texttt{L}$, $s_i = \texttt{R}$, $d_i \gt 0$ and index $i$ is not in the bad set, then we will insert it. After each query, if the bad set is empty, then the answer is "YES".
    185 
    186 **Code (C++)**
    187 
    188 ```
    189 #include <bits/stdc++.h>
    190 
    191 using namespace std;
    192 
    193 int main() {
    194     int t;
    195     cin >> t;
    196     while(t--) {
    197         int n,q;
    198         cin >> n >> q;
    199         vector<int> perm(n);
    200         for(int i = 0; i < n; i++) cin >> perm[i];
    201         for(int i = 0; i < n; i++) perm[i]--;
    202         vector<int> invperm(n);
    203         for(int i = 0; i < n; i++) invperm[perm[i]]=i;
    204         vector<int> diffArr(n);
    205         for(int i = 0; i < n; i++) {
    206             diffArr[min(i, invperm[i])]++;
    207             diffArr[max(i, invperm[i])]--;
    208         }
    209         for(int i = 1; i < n; i++) diffArr[i]+=diffArr[i-1];
    210         string s;
    211         cin >> s;
    212         set<int> problems;
    213         for(int i = 0; i < n-1; i++) {
    214             if(s[i]=='L'&&s[i+1]=='R'&&diffArr[i]!=0) {
    215                 problems.insert(i);
    216             } 
    217         }
    218         while(q--) {
    219             int x;
    220             cin >> x;
    221             x--;
    222             if(s[x]=='L') {
    223                 s[x]='R';
    224             } else {
    225                 s[x]='L';
    226             }
    227             if(s[x-1]=='L'&&s[x]=='R'&&diffArr[x-1]!=0) {
    228                 problems.insert(x-1);
    229             } else {
    230                 problems.erase(x-1);
    231             }
    232             if(s[x]=='L'&&s[x+1]=='R'&&diffArr[x]!=0) {
    233                 problems.insert(x);
    234             } else {
    235                 problems.erase(x);
    236             }
    237             if(problems.size()) {
    238                 cout << "NO" << endl;
    239             } else {
    240                 cout << "YES" << endl;
    241             }
    242         }
    243     }
    244 }
    245 ```
    246 
    247 #### [2030E - MEXимизируйте счёт](/contest/2030/problem/E "Codeforces Round 979 (Div. 2)")
    248 
    249 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED"), [cry](/profile/cry "Международный мастер cry"), [satyam343](/profile/satyam343 "Мастер satyam343")   
    250  Analysis: [cry](/profile/cry "Международный мастер cry")
    251 
    252 **Solution** 
    253 
    254 Observation: The score of $b$ is equivalent to $f_0$ + $\min(f_0, f_1)$ + $\ldots$ + $\min(f_0, \ldots, f_{n-1})$ where $f_i$ stores the frequency of integer $i$ in $b$.
    255 
    256 Intuition: We can greedily construct the $k$ arrays by repeating this step: Select the minimum $j$ such that $f_j = 0$ and $\min(f_0, \ldots f_{j-1}) \gt 0$, and construct the array $[0, 1, \ldots, j-1]$. This is optimal because every element we add will increase the MEX by $1$, which will increase the score by $1$. If we add $j$, the MEX will not increase. Also, when we add an element, we cannot increase the score by more than $1$. Adding less than $j$ elements cannot increase MEX for future arrays.
    257 
    258 From this observation, we can see that only the frequency array of $a$ matters. From now on, let's denote the frequency of $i$ in $a$ as $f_i$. We can find the sum over all subsequences using dynamic programming.
    259 
    260 Let's denote $dp[i][j]$ as the number of subsequences containing only the first $i$ integers and $min(f_0, \ldots, f_i) = j$. Initially, $dp[0][i] = \binom{f_0}{i}$. To transition, we need to consider two cases:
    261 
    262 In the first case, let's assume $j \lt \min(f_0, \ldots, f_{i-1})$. The number of subsequences that can be created is $(\sum_{k=j+1}^n dp[i-1][k]) \cdot \binom{f_i}{j}$. That is, all the subsequences from previous length such that it is possible for $j$ to be the new minimum, multiplied by the number of subsequences where $f_i = j$.
    263 
    264 In the second case, let's assume $j \geq \min(f_0, \ldots, f_{i-1})$. The number of subsequences that can be created is $(\sum_{k=j}^{f_i} \binom{f_i}{k}) \cdot dp[i-1][j]$. That is, all subsequences containing at least $j$ elements of $i$, multiplied by all previous subsequences with minimum already equal to $j$.
    265 
    266 The total score is $dp[i][j] \cdot j \cdot 2^{f_{i+1} + \dots + f_{n-1}}$ over the length of the prefix $i$ and prefix minimum $j$.
    267 
    268 We can speed up the calculations for both cases using suffix sums, however, this still yields an $O(n^2)$ algorithm. However, $j$ is bounded to the interval $[1, f_i]$ for each $i$. Since the sum of $f_i$ is $n$, the total number of secondary states is $n$. This becomes just a constant factor, so the total complexity is $O(n)$.
    269 
    270 **Code (C++)**
    271 
    272 ```
    273 #include <bits/stdc++.h>
    274 #define int long long
    275 #define ll long long 
    276 #define pii pair<int,int> 
    277 #define piii pair<pii,pii>
    278 #define fi first
    279 #define se second
    280 #pragma GCC optimize("O3,unroll-loops")
    281 #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
    282 using namespace std;
    283 
    284 const int MX = 2e5;
    285 ll fact[MX+1];
    286 ll ifact[MX+1];
    287 ll MOD=998244353;
    288  
    289 ll binPow(ll base, ll exp) {
    290     ll ans = 1;
    291     while(exp) {
    292         if(exp%2) {
    293             ans = (ans*base)%MOD;
    294         }
    295         base = (base*base)%MOD;
    296         exp /= 2;
    297     }
    298     return ans;
    299 }
    300  
    301 int nCk(int N, int K) {
    302     if(K>N||K<0) {
    303         return 0;
    304     }
    305     return (fact[N]*((ifact[K]*ifact[N-K])%MOD))%MOD;
    306 }
    307  
    308 void ICombo() {
    309 	fact[0] = 1;
    310     for(int i=1;i<=MX;i++) {
    311         fact[i] = (fact[i-1]*i)%MOD;
    312     }    
    313     ifact[MX] = binPow(fact[MX],MOD-2);
    314     for(int i=MX-1;i>=0;i--) {
    315         ifact[i] = (ifact[i+1]*(i+1))%MOD;
    316     }
    317 }
    318 
    319 void solve() {
    320     int n, ans=0; cin >> n;
    321     vector<int> c(n);
    322     for (int r:c) {
    323         cin >> r; c[r]++; 
    324     }
    325     vector<vector<int>> dp(n,vector<int>(1));
    326     vector<int> ps, co; 
    327     for (int i = 1; i <= c[0]; i++) dp[0].push_back(nCk(c[0],i));
    328     for (int i = 1; i < n; i++) {
    329         ps.resize(1); co=ps; 
    330         for (int r:dp[i-1]) ps.push_back((ps.back()+r)%MOD); 
    331         int m=ps.size()-1;
    332         dp[i].resize(min(m,c[i]+1));
    333         for (int j = 0; j <= c[i]; j++) co.push_back((co.back()+nCk(c[i],j))%MOD);
    334         for (int j = 1; j < dp[i].size(); j++) dp[i][j]=nCk(c[i],j)*(ps[m]-ps[j]+MOD)%MOD+(co.back()-co[j+1]+MOD)*dp[i-1][j]%MOD; 
    335     }
    336     int j=0;
    337     for (auto r:dp) {
    338         n-=c[j++];
    339         for (int i = 1; i < r.size(); i++) (ans+=i*r[i]%MOD*binPow(2,n))%=MOD;
    340     }
    341     cout << ans << "\n"; 
    342 }
    343 
    344 int32_t main() {
    345 	ios::sync_with_stdio(0); cin.tie(0);
    346         ICombo();
    347 	int t = 1; cin >> t;
    348 	while (t--) solve();
    349 }
    350 ```
    351 
    352 #### [2030F - Орангутано-одобренный массив](/contest/2030/problem/F "Codeforces Round 979 (Div. 2)")
    353 
    354 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED"), [satyam343](/profile/satyam343 "Мастер satyam343")   
    355  Analysis: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED")
    356 
    357 **Solution** 
    358 
    359 First, let's try to find whether a single array is orangutan-approved or not.
    360 
    361 **Claim**: The array $b$ of size $n$ is not orangutan-approved if and only if there exists indices $1\leq w \lt x \lt y \lt z \leq n$ such that $b_w=b_y$, $b_x=b_z$, and $b_w\neq b_x$.
    362 
    363 **Proof**: Let's prove this with strong induction. For $n=0$, the claim is true because the empty array is orangutan-approved. Now, let's suppose that the claim is true for all $m \lt n$.
    364 
    365 Now, let $s$ be a sorted sequence such that $x$ is in $s$ if and only if $b_x=b_1$. Suppose $s$ is length $k$. We can split the array $b$ into disjoint subarrays $c_1, c_2, \ldots, c_k$ such that $c_i$ is the subarray $b[s_i+1\ldots s_{i+1}-1]$ for all $1 \leq i \lt k$ and $c_k=b[s_k+1\ldots n]$ That is, $c_i$ is the subarray that lies between each occurrence of $b_1$ in the array $b$.
    366 
    367 First, we note that the set of unique elements of $c_i$ and $c_j$ cannot contain any elements in common for all $i\neq j$. This is because suppose that there exists $i$ and $j$ such that $i \lt j$ and the set of unique values in $c_i$ and $c_j$ both contain $y$. Then, in the original array $b$, there must exist a subsequence $b_1, y, b_1, y$. This makes our premise false.
    368 
    369 By our inductive claim, each of the arrays $c_1, c_2, \ldots, c_k$ must be orangutan-approved. Since there are no overlapping elements, we may delete each of the arrays $c_1, c_2, \ldots, c_k$ separately. Finally, the array $b$ is left with $k$ copies of $b_1$, and we can use one operation to delete all remaining elements in the array $b$.
    370 
    371 Now, how do we solve for all queries? First, precompute the array $last$, which is the array containing for each $i$ the largest index $j \lt i$ such that $a[j]=a[i]$. Let's then use two pointers to compute the last element $j \lt i$ such that $a[j\ldots i]$ is orangutan-approved but $a[j-1\ldots i]$ is not, and store this in an array called $left$. Let's also keep a maximum segment tree $next$ such that $next[i]$ is the first element $j \gt i$ such that $a_j=a_i$. As we sweep from $i-1$ to $i$, we do the following:
    372 
    373 1. Set $L=left[i-1]$
    374 2. Otherwise, while $\max(next[L...last[i]-1] \gt last[i]$ and $last[i]\neq-1$), increment $L$ by $1$.
    375 3. Set $left[i]=L$
    376 
    377 When the $left$ array is fully calculated, we can solve each query in $O(1)$.
    378 
    379 **Code (C++)**
    380 
    381 ```
    382 #pragma GCC optimize("Ofast")
    383  
    384 #include <bits/stdc++.h> 
    385 using namespace std;
    386 #define ll long long
    387 #define nline "\n"
    388 #define f first
    389 #define s second
    390 #define sz(x) x.size()
    391 #define all(x) x.begin(),x.end()
    392 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    393 const ll INF_ADD=1e18;
    394 const ll MOD=1e9+7;
    395 const ll MAX=1048579;
    396 class ST {
    397 public:
    398     vector<ll> segs;
    399     ll size = 0;
    400     ll ID = 0;
    401  
    402     ST(ll sz) {
    403         segs.assign(2 * sz, ID);
    404         size = sz;  
    405     }   
    406    
    407     ll comb(ll a, ll b) {
    408         return max(a, b);  
    409     }
    410  
    411     void upd(ll idx, ll val) {
    412         segs[idx += size] = val;
    413         for(idx /= 2; idx; idx /= 2) segs[idx] = comb(segs[2 * idx], segs[2 * idx + 1]);
    414     }
    415  
    416     ll query(ll l, ll r) {
    417         ll lans = ID, rans = ID;
    418         for(l += size, r += size + 1; l < r; l /= 2, r /= 2) {
    419             if(l & 1) lans = comb(lans, segs[l++]);
    420             if(r & 1) rans = comb(segs[--r], rans);
    421         }
    422         return comb(lans, rans);
    423     }
    424 }; 
    425 void solve(){
    426   ll n,q,l=1; cin>>n>>q;
    427   ST track(n+5);
    428   vector<ll> a(n+5),last(n+5,0),lft(n+5);
    429   for(ll i=1;i<=n;i++){
    430     cin>>a[i];
    431     ll till=last[a[i]];
    432     while(track.query(l,till)>=till+1){
    433       l++;
    434     }
    435     if(till){
    436       track.upd(till,i);
    437     }
    438     lft[i]=l;
    439     last[a[i]]=i;
    440   }
    441   while(q--) {
    442     ll l,r; cin>>l>>r;
    443     if(lft[r]<=l){
    444       cout<<"YES\n";
    445     } 
    446     else{
    447       cout<<"NO\n";
    448     }
    449   }
    450 }
    451 int main()                                                                                 
    452 {         
    453   ios_base::sync_with_stdio(false);                         
    454   cin.tie(NULL);                                  
    455   ll test_cases=1;                 
    456   cin>>test_cases;
    457   while(test_cases--){
    458     solve();
    459   }
    460 }
    461 ```
    462 
    463 #### [2030G1 - Уничтожение Вселенной (простая версия)](/contest/2030/problem/G1 "Codeforces Round 979 (Div. 2)") and [2030G2 - Уничтожение Вселенной (сложная версия)](/contest/2030/problem/G2 "Codeforces Round 979 (Div. 2)")
    464 
    465 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED"), [satyam343](/profile/satyam343 "Мастер satyam343")   
    466  Analysis: [satyam343](/profile/satyam343 "Мастер satyam343")
    467 
    468 **Solution (Easy Version)**
    469 
    470 To find the score of a set of intervals $([l_1, r_1], [l_2, r_2], \ldots, [l_v, r_v])$, we follow these steps:
    471 
    472 Initially, the score is set to $0$.
    473 
    474 We perform the following process repeatedly:
    475 
    476 * Let $x$ be the interval with the smallest $r_i$ among all active intervals.
    477 * Let $y$ be the interval with the largest $l_i$ among all active intervals.
    478 * If $r_x \lt l_y$, add $l_y - r_x$ to the score, mark intervals $x$ and $y$ as inactive, and continue the process.
    479 * If $r_x \geq l_y$, stop the process.
    480 
    481 At the end of this process, all active intervals will intersect at least one common point.
    482 
    483 Now, we need to prove that the process indeed gives us the minimum possible score. We can prove this by induction.
    484 
    485 Let $S$ be some set of intervals, and let $x$ and $y$ be the intervals defined above. Consider the set $S' = S \setminus {x, y}$ (i.e., $S'$ is the set $S$ excluding $x$ and $y$). We claim that:
    486 
    487 $ \text{score}(S) \geq \text{score}(S') + \text{distance}(x, y) $
    488 
    489 This is true because, for $x$ and $y$ to intersect, we must perform at least $\text{distance}(x, y)$ operations. Our construction achieves the lower bound of $\text{score}(S') + \text{distance}(x, y)$. Thus,
    490 
    491 $ \text{score}(S) = \text{score}(S') + \text{distance}(x, y) $
    492 
    493 During the process, we pair some intervals (possibly none). Specifically, in the $k$-th step, we pair the interval with the $k$-th smallest $r_i$ with the interval having the $k$-th largest $l_j$, and add the distance between them to the score.
    494 
    495 In the problem G1, we can compute the contribution of each pair of intervals as follows:
    496 
    497 Suppose we consider a pair $(i, j)$. Without loss of generality, assume that $r_i \lt l_j$.
    498 
    499 The pair $(i, j)$ will be considered in some subset $S$ if there are exactly $x$ intervals $p$ such that $r_p \lt r_i$ and exactly $x$ intervals $p$ such that $l_p \gt l_j$, for some non-negative integer $x$.
    500 
    501 Let there be $g$ intervals $p$ such that $r_p \lt r_i$ and $h$ intervals $p$ such that $l_p \gt l_j$.
    502 
    503 For $(i, j)$ to be paired in some subset $S$, we must choose $x$ intervals from the $g$ intervals on the left and $x$ intervals from the $h$ intervals on the right, for some non-negative integer $x$. There are no restrictions on the remaining $n - 2 - g - h$ intervals.
    504 
    505 Therefore, the contribution of $(i, j)$ is:
    506 
    507 $ \sum_{x = 0}^{g} (l_j - r_i) \cdot \binom{g}{x} \cdot \binom{h}{x} \cdot 2^{n - 2 - g - h} $
    508 
    509 We can simplify this sum using the identity:
    510 
    511 $ \sum_{x = 0}^{g} \binom{g}{x} \cdot \binom{h}{x} = \binom{g + h}{g} $
    512 
    513 (This is a form of the Vandermonde Identity.)
    514 
    515 Thus, the contribution of $(i, j)$ becomes:
    516 
    517 $ (l_j - r_i) \cdot \binom{g + h}{g} \cdot 2^{n - 2 - g - h} $
    518 
    519 This can be computed in $O(1)$ time.
    520 
    521 Note that in the explanation above, we assumed that the interval endpoints are distinct for simplicity. If they are not, we can order the intervals based on their $l_i$ values to maintain consistency.
    522 
    523 **Solution (Hard Version)**
    524 
    525 Let us find the contribution of $r[i]$, the right endpoint of $i$-th interval.
    526 
    527 Let $x$ be the number of intervals $j$ such that $r[j] \lt r[i]$, and let $y$ be the number of intervals $j$ such that $l[j] \gt r[i]$.
    528 
    529 To determine the contribution of $r[i]$ to the final answer, we consider selecting $p$ intervals from the $x$ intervals to the left and $q$ intervals from the $y$ intervals to the right, with the constraint that $p \lt q$. We require $p \lt q$ so that interval $i$ is paired with some other interval on the right (as discussed in the solution for G1). Therefore, the contribution of $r[i]$ can be expressed as:
    530 
    531 $ \text{Contribution} = -r[i] \cdot \text{ways}(x, y) \cdot 2^{n - 1 - x - y} $
    532 
    533 Here, $\text{ways}(x, y)$ represents the number of valid selections where $p \lt q$.
    534 
    535 **Calculating $\text{ways}(x, y)$**
    536 
    537 To compute $\text{ways}(x, y)$, we can use the Vandermonde identity to simplify the expression:
    538 
    539 $ \text{ways}(x, y) = \sum_{\substack{0 \leq p \lt q \leq y}} \binom{x}{p} \binom{y}{q} $
    540 
    541 This can be rewritten as:
    542 
    543 $ \text{ways}(x, y) = \sum_{p=0}^{x} \sum_{k=1}^{y} \binom{x}{p} \binom{y}{p + k} $
    544 
    545 Define the function $g(k)$ as:
    546 
    547 $ g(k) = \sum_{p=0}^{x} \binom{x}{p} \binom{y}{p + k} $
    548 
    549 By applying the Vandermonde identity, we get:
    550 
    551 $ g(k) = \binom{x + y}{x + k} $
    552 
    553 Thus, the total number of ways is:
    554 
    555 $ \text{ways}(x, y) = \sum_{k=1}^{y} \binom{x + y}{x + k} $
    556 
    557 We can simplify this summation using the property of binomial coefficients:
    558 
    559 $ \text{ways}(x, y) = 2^{x + y} - h(x + y, x) $
    560 
    561 where the function $h(p, q)$ is defined as:
    562 
    563 $ h(p, q) = \sum_{i=0}^{q} \binom{p}{i} $
    564 
    565 **Efficient Computation of $h(p, q)$**
    566 
    567 Note that:
    568 
    569 $ h(p, q) = 2 \cdot h(p - 1, q) - \binom{p - 1}{q} $
    570 
    571 Suppose throughout the solution, we call the function $h(p, q)$ $d$ times for pairs $(p_1, q_1), (p_2, q_2), \ldots, (p_d, q_d)$, in that order. We can observe that:
    572 
    573 $ \sum_{i=2}^{d} |p_i - p_{i-1}| + |q_i - q_{i-1}| = O(n) $
    574 
    575 Since $h(p_i, q_i)$ can be computed from $h(p_{i-1}, q_{i-1})$ in $|p_i - p_{i-1}| + |q_i - q_{i-1}|$ operations, the amortized time complexity for this part is $O(n)$.
    576 
    577 **Final Contribution**
    578 
    579 Combining the above results, the contribution of $r[i]$ to the answer is:
    580 
    581 $ -r[i] \cdot \left(2^{x + y} - h(x + y, x)\right) \cdot 2^{n - 1 - x - y} $
    582 
    583 A similar calculation can be applied to the contribution of $l[i]$. By summing these contributions across all relevant intervals, we obtain the final answer.
    584 
    585 **G1 Code (C++)**
    586 
    587 ```
    588 #pragma GCC optimize("Ofast")
    589  
    590 #include <bits/stdc++.h>   
    591 #include <ext/pb_ds/tree_policy.hpp>
    592 #include <ext/pb_ds/assoc_container.hpp>
    593 using namespace __gnu_pbds;   
    594 using namespace std;
    595 #define ll long long
    596 #define ld long double
    597 #define nline "\n"
    598 #define f first
    599 #define s second
    600 #define sz(x) (ll)x.size()
    601 #define vl vector<ll>
    602 const ll INF_MUL=1e13;
    603 const ll INF_ADD=1e18;
    604 #define all(x) x.begin(),x.end()
    605 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    606 typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
    607 //--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------     
    608 const ll MOD=998244353;
    609 const ll MAX=500500;
    610 vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1);
    611 ll binpow(ll a,ll b,ll MOD){
    612     ll ans=1;
    613     a%=MOD;  
    614     while(b){
    615         if(b&1)
    616             ans=(ans*a)%MOD;
    617         b/=2;
    618         a=(a*a)%MOD;
    619     }
    620     return ans;
    621 }
    622 ll inverse(ll a,ll MOD){
    623     return binpow(a,MOD-2,MOD);
    624 } 
    625 void precompute(ll MOD){
    626     for(ll i=2;i<MAX;i++){
    627         fact[i]=(fact[i-1]*i)%MOD;
    628     }
    629     inv_fact[MAX-1]=inverse(fact[MAX-1],MOD);
    630     for(ll i=MAX-2;i>=0;i--){
    631         inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD;
    632     }
    633 }
    634 ll nCr(ll a,ll b,ll MOD){
    635     if((a<0)||(a<b)||(b<0))
    636         return 0;   
    637     ll denom=(inv_fact[b]*inv_fact[a-b])%MOD;
    638     return (denom*fact[a])%MOD;  
    639 }
    640 ll l[MAX],r[MAX],lft[MAX],rght[MAX],power[MAX];
    641 void solve(){ 
    642   ll n; cin>>n;
    643   power[0]=1;
    644   for(ll i=1;i<=n;i++){
    645     cin>>l[i]>>r[i];
    646     power[i]=(power[i-1]*2ll)%MOD;
    647   }
    648   for(ll i=1;i<=n;i++){
    649     lft[i]=rght[i]=0;
    650     for(ll j=1;j<=n;j++){
    651       if(make_pair(r[i],i)>make_pair(r[j],j)){
    652         lft[i]++;
    653       }
    654       if(make_pair(l[i],i)<make_pair(l[j],j)){
    655         rght[i]++;
    656       }
    657     }
    658   }
    659   ll ans=0;
    660   for(ll i=1;i<=n;i++){
    661     for(ll j=1;j<=n;j++){
    662       if(r[i]<l[j]){
    663         ll found=lft[i]+rght[j];
    664         ll now=nCr(found,lft[i],MOD)*(l[j]-r[i]);
    665         now%=MOD;
    666         ll remaining=n-found-2;
    667         ans=(ans+now*power[remaining])%MOD;
    668       }
    669     }
    670   }
    671   cout<<ans<<nline;
    672   return;    
    673 }  
    674 int main()                                                                                 
    675 {         
    676   ios_base::sync_with_stdio(false);                         
    677   cin.tie(NULL);                              
    678   ll test_cases=1;                 
    679   cin>>test_cases;
    680   precompute(MOD);
    681   while(test_cases--){
    682     solve();
    683   }
    684   cout<<fixed<<setprecision(12);  
    685   cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
    686 }
    687 ```
    688 
    689 **G2 Code (C++)**
    690 
    691 ```
    692 #pragma GCC optimize("Ofast")
    693  
    694 #include <bits/stdc++.h>   
    695 #include <ext/pb_ds/tree_policy.hpp>
    696 #include <ext/pb_ds/assoc_container.hpp>
    697 using namespace __gnu_pbds;   
    698 using namespace std;
    699 #define ll long long
    700 #define ld long double
    701 #define nline "\n"
    702 #define f first
    703 #define s second
    704 #define sz(x) (ll)x.size()
    705 #define vl vector<ll>
    706 const ll INF_MUL=1e13;
    707 const ll INF_ADD=1e18;
    708 #define all(x) x.begin(),x.end()
    709 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    710 typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
    711 //--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------     
    712 const ll MOD=998244353;
    713 const ll MAX=5000500;
    714 vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1);
    715 ll binpow(ll a,ll b,ll MOD){
    716     ll ans=1;
    717     a%=MOD;  
    718     while(b){
    719         if(b&1)
    720             ans=(ans*a)%MOD;
    721         b/=2;
    722         a=(a*a)%MOD;
    723     }
    724     return ans;
    725 }
    726 ll inverse(ll a,ll MOD){
    727     return binpow(a,MOD-2,MOD);
    728 } 
    729 void precompute(ll MOD){
    730     for(ll i=2;i<MAX;i++){
    731         fact[i]=(fact[i-1]*i)%MOD;
    732     }
    733     inv_fact[MAX-1]=inverse(fact[MAX-1],MOD);
    734     for(ll i=MAX-2;i>=0;i--){
    735         inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD;
    736     }
    737 }
    738 ll nCr(ll a,ll b,ll MOD){
    739     if((a<0)||(a<b)||(b<0))
    740         return 0;   
    741     ll denom=(inv_fact[b]*inv_fact[a-b])%MOD;
    742     return (denom*fact[a])%MOD;  
    743 }
    744 ll l[MAX],r[MAX],power[MAX];
    745 ll ans=0,on_left=0,on_right,len;
    746 ll x=0,y=0,ways=0,inv2;
    747 ll getv(){
    748   while(x>=len+1){
    749     ways=((ways+nCr(x-1,y,MOD))*inv2)%MOD;
    750     x--;
    751   }
    752   while(x<=len-1){
    753     ways=(2ll*ways-nCr(x,y,MOD)+MOD)%MOD;
    754     x++;
    755   }
    756   while(y<=on_left-1){
    757     ways=(ways+nCr(x,y+1,MOD))%MOD;
    758     y++;
    759   }
    760   return ways;
    761 }
    762 void solve(){ 
    763   ll n; cin>>n;
    764   power[0]=1;
    765   vector<array<ll,2>> track;
    766   multiset<ll> consider;
    767   for(ll i=1;i<=n;i++){
    768     cin>>l[i]>>r[i];
    769     track.push_back({r[i],l[i]});
    770     consider.insert(l[i]);
    771     power[i]=(power[i-1]*2ll)%MOD;
    772   }
    773   ans=on_left=0;
    774   on_right=len=n;
    775   x=y=0; ways=1;
    776   sort(all(track));
    777   for(auto it:track){
    778     while(!consider.empty()){
    779       if(*consider.begin() <= it[0]){
    780         consider.erase(consider.begin());
    781         on_right--,len--;
    782       }
    783       else{
    784         break;
    785       }
    786     }
    787     ll now=power[len]-getv();
    788     now=(now*power[n-1-len])%MOD;
    789     now=(now*it[0])%MOD;
    790     ans=(ans+MOD-now)%MOD;
    791     on_left++,len++;
    792   }
    793   track.clear(); consider.clear();
    794   for(ll i=1;i<=n;i++){
    795     track.push_back({l[i],r[i]});
    796     consider.insert(r[i]);
    797   }
    798   sort(all(track));
    799   reverse(all(track));
    800   on_left=0;
    801   on_right=len=n;
    802   x=y=0; ways=1;
    803   for(auto it:track){
    804     while(!consider.empty()){
    805       if(*(--consider.end()) >= it[0]){
    806         consider.erase(--consider.end());
    807         on_right--,len--;
    808       }
    809       else{
    810         break;
    811       }
    812     }
    813     ll now=power[len]-getv();
    814     now=(now*power[n-1-len])%MOD;
    815     now=(now*it[0])%MOD;
    816     ans=(ans+now)%MOD;
    817     on_left++,len++;
    818   }
    819   ans=(ans+MOD)%MOD;
    820   cout<<ans<<nline;
    821   return;    
    822 }  
    823 int main()                                                                                 
    824 {         
    825   ios_base::sync_with_stdio(false);                         
    826   cin.tie(NULL);                              
    827   ll test_cases=1;                 
    828   cin>>test_cases;
    829   precompute(MOD);
    830   inv2=inverse(2,MOD);
    831   while(test_cases--){
    832     solve();
    833   }
    834   cout<<fixed<<setprecision(12);  
    835   cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
    836 }
    837 ```