codeforces-scrape

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

2266.md (24149B)


      1 Source: https://codeforces.com/blog/entry/156984
      2 
      3 Thanks for participating in [Codeforces Round 1122 (Div. 3)](/contest/2266 "Codeforces Round 1122 (Div. 3)")!
      4 
      5 **Rate the contest!**
      6 
      7 **Quality**
      8 
      9 * Excellent contest
     10 * Good contest
     11 * Average contest
     12 * Bad contest
     13 * Horrible contest
     14 
     15 **Difficulty**
     16 
     17 * Trivial contest
     18 * Easy contest
     19 * Average contest
     20 * Hard contest
     21 * Impossible contest
     22 
     23 [2266A - Good Contest](/contest/2266/problem/A "Codeforces Round 1122 (Div. 3)")
     24 
     25 **Hint**
     26 
     27 How many participants can possibly have solved all three problems?
     28 
     29 **Solution**
     30 
     31 At most $\min(a_1,a_2,a_3)$ participants could have solved all three problems. This is achievable by making the same $\min(a_1,a_2,a_3)$ participants solve every problem, then distributing the remaining solves arbitrarily.
     32 
     33 Thus, the answer is $n-\min(a_1,a_2,a_3)$.
     34 
     35 The complexity is $O(1)$ per test case.
     36 
     37 **Code (C++)**
     38 
     39 ```
     40 #include <bits/stdc++.h>
     41 using namespace std;
     42 
     43 void solve() {
     44     int N; cin >> N;
     45     int a, b, c; cin >> a >> b >> c;
     46     int m = min({a,b,c});
     47     cout << N-m << endl;
     48 }
     49 
     50 int main() {
     51     int T; cin >> T;
     52     while (T--) {solve();}
     53 }
     54 ```
     55 
     56 **Rate the problem!**
     57 
     58 **Difficulty**
     59 
     60 * Trivial problem
     61 * Easy problem
     62 * Average problem
     63 * Hard problem
     64 * Impossible problem
     65 
     66 **Quality**
     67 
     68 * Excellent problem
     69 * Good problem
     70 * Average problem
     71 * Bad problem
     72 * Horrible problem
     73 
     74 [2266B - Three Piles](/contest/2266/problem/B "Codeforces Round 1122 (Div. 3)")
     75 
     76 **Hint 1**
     77 
     78 Consider the cases $a\geq b$ and $a \lt b$ separately.
     79 
     80 **Hint 2**
     81 
     82 If Alice ever takes stones, she should take all of them.
     83 
     84 **Solution**
     85 
     86 If $a\geq b$, Alice takes all $c$ stones immediately. There is nothing left for Bob to use to reduce her lead, so the score is $a+c-b$.
     87 
     88 Now suppose $a \lt b$. Alice can take $0$ stones, and Bob will also take $0$ because he is already ahead and taking more stones would only increase the score. This gives $b-a$. Otherwise, Alice should take all $c$ stones at once. Taking only part of them gives a difference between the two cases of taking none and taking all, so it cannot be better than both. Taking all gives $|a+c-b|$.
     89 
     90 If $a+c \lt b$, this is smaller than $b-a$. Otherwise, it equals $a+c-b$. Therefore, the answer is $\max(|a-b|,a+c-b)$.
     91 
     92 The complexity is $O(1)$ per test case.
     93 
     94 **Code (C++)**
     95 
     96 ```
     97 #include <bits/stdc++.h>
     98 using namespace std;
     99 
    100 void solve() {
    101     int a, b, c; cin >> a >> b >> c;
    102     cout << max(abs(a-b),(a+c-b)) << endl;
    103 }
    104 
    105 int main() {
    106     int T; cin >> T;
    107     while (T--) {solve();}
    108 }
    109 ```
    110 
    111 **Rate the problem!**
    112 
    113 **Difficulty**
    114 
    115 * Trivial problem
    116 * Easy problem
    117 * Average problem
    118 * Hard problem
    119 * Impossible problem
    120 
    121 **Quality**
    122 
    123 * Excellent problem
    124 * Good problem
    125 * Average problem
    126 * Bad problem
    127 * Horrible problem
    128 
    129 [2266C - AND, OR, Sort!](/contest/2266/problem/C "Codeforces Round 1122 (Div. 3)")
    130 
    131 **Hint 1**
    132 
    133 If a prefix contains both $0$ and $1$, what are its bitwise AND and bitwise OR?
    134 
    135 **Hint 2**
    136 
    137 A sorted binary string is determined by one split point.
    138 
    139 **Solution**
    140 
    141 If a prefix contains both $0$ and $1$, its AND is $0$ and its OR is $1$, so its last character can be changed to either value.
    142 
    143 If $s_1=1$, the first character can never change, so the final string must be all ones. Every zero can be changed using OR, giving the number of zeros as the answer.
    144 
    145 Now suppose $s_1=0$. Fix the point after which the ones start. For a split after $i$, we need to change every one in $[1,i]$ and every zero in $[i+1,n]$. We can first change the required zeros on the right using OR, then change the required ones on the left using AND. A split inside the initial block of zeros is never better than moving it to the end of that block.
    146 
    147 So, scan every split while maintaining the number of ones on the left and zeros on the right, and take the minimum.
    148 
    149 The complexity is $O(n)$ per test case.
    150 
    151 **Code (C++)**
    152 
    153 ```
    154 #include <bits/stdc++.h>
    155 using namespace std;
    156 
    157 void solve() {
    158     int N; cin >> N;
    159     string s; cin >> s;
    160     int z = 0;
    161     int o = 0;
    162     for (int i = 0; i < N; i++) {z+=(s[i]=='0');}
    163     if (s[0]=='1') {cout << z << endl; return;}
    164     int aa = 1e9;
    165     for (int i = 0; i < N; i++) {
    166         o+=(s[i]=='1');
    167         z-=(s[i]=='0');
    168         aa=min(aa,o+z);
    169     }
    170     cout << aa << endl;
    171 }
    172 
    173 int main() {
    174     int T; cin >> T;
    175     while (T--) {solve();}
    176 }
    177 ```
    178 
    179 **Rate the problem!**
    180 
    181 **Difficulty**
    182 
    183 * Trivial problem
    184 * Easy problem
    185 * Average problem
    186 * Hard problem
    187 * Impossible problem
    188 
    189 **Quality**
    190 
    191 * Excellent problem
    192 * Good problem
    193 * Average problem
    194 * Bad problem
    195 * Horrible problem
    196 
    197 [2266D - Falling Concrete](/contest/2266/problem/D "Codeforces Round 1122 (Div. 3)")
    198 
    199 **Hint 1**
    200 
    201 Look at how the height and position of each section change after an operation.
    202 
    203 **Hint 2**
    204 
    205 A section moving one position to the right gains $1$ height, while a section moving one position to the left loses $1$ height.
    206 
    207 **Solution**
    208 
    209 During an operation, every section passed over moves one position to the right and gains $1$ height. The section being moved goes $j-i$ positions to the left and loses exactly $j-i$ height. Thus, for every section, $\text{height}-\text{position}$ never changes. The section initially at position $i$ therefore always keeps the value $a_i-i$.
    210 
    211 We can also reorder the sections however we want by building the desired order from left to right and repeatedly moving the required section into the next position.
    212 
    213 Suppose $k$ consecutive positions starting at $p$ are flat at height $h$. Their invariant values are $h-p,h-p-1,\ldots,h-p-k+1$, which are $k$ distinct consecutive integers. The reverse is also true: if $k$ sections have consecutive values $a_i-i$, placing them in decreasing order makes their heights equal.
    214 
    215 Therefore, the answer is the longest consecutive run among the distinct values $a_i-i$. Put them in a set and scan in increasing order.
    216 
    217 The complexity is $O(n\log n)$ per test case.
    218 
    219 **Code (C++)**
    220 
    221 ```
    222 #include <bits/stdc++.h>
    223 using namespace std;
    224 
    225 void solve() {
    226     int N; cin >> N;
    227     set<int> s;
    228     for (int i = 1; i <= N; i++) {
    229         int a; cin >> a;
    230         s.insert(a-i);
    231     }
    232     int aa = 0;
    233     int tt = 0;
    234     int c = -1e9;
    235     for (auto x : s) {
    236         if (x!=c+1) {aa=max(aa,tt); tt=0;}
    237         tt++;
    238         c=x;
    239     }
    240     aa=max(aa,tt);
    241     cout << aa << endl;
    242 }
    243 
    244 int main() {
    245     int T; cin >> T;
    246     while (T--) {solve();}
    247 }
    248 ```
    249 
    250 **Rate the problem!**
    251 
    252 **Difficulty**
    253 
    254 * Trivial problem
    255 * Easy problem
    256 * Average problem
    257 * Hard problem
    258 * Impossible problem
    259 
    260 **Quality**
    261 
    262 * Excellent problem
    263 * Good problem
    264 * Average problem
    265 * Bad problem
    266 * Horrible problem
    267 
    268 [2266E - Prime Destruction](/contest/2266/problem/E "Codeforces Round 1122 (Div. 3)")
    269 
    270 **Hint**
    271 
    272 Use DP. Let $dp_i$ be the minimum number of operations needed to turn one $i$ into elements which are all at most $k$.
    273 
    274 **Solution**
    275 
    276 Let $dp_i$ be the minimum number of operations needed to turn one $i$ into elements which are all at most $k$. Clearly, $dp_i=0$ for $i\leq k$.
    277 
    278 For $i \gt k$, suppose we choose a prime divisor $p$ of $i$. One operation gives us $p$ copies of $i/p$, and these copies can then be handled independently. Thus, $dp_i=\min_{p\mid i,\ p\text{ prime}}(1+p\cdot dp_{i/p})$.
    279 
    280 Since $i/p \lt i$, compute the DP in increasing order. We can precompute the distinct prime divisors of every number with a sieve. Finally, the original elements are independent, so the answer is $\sum dp_{a_i}$.
    281 
    282 The complexity is $O(n\log\log n)$ per test case after preprocessing.
    283 
    284 **Bonus**
    285 
    286 Can you solve the problem for all $f(1),f(2),\ldots,f(n)$?
    287 
    288 This was actually the original version of the problem!
    289 
    290 **Code (C++)**
    291 
    292 ```
    293 #include <bits/stdc++.h>
    294 using namespace std;
    295 
    296 vector<long long> pf[200001];
    297 long long dp[200001];
    298 bool cmp[200001];
    299 
    300 void pre() {
    301     for (long long i = 2; i <= 200000; i++) {
    302         if (!cmp[i]) {
    303             cmp[i]=true;
    304             for (long long j = 2*i; j <= 200000; j+=i) {
    305                 pf[j].push_back(i);
    306                 cmp[j]=true;
    307             }
    308             pf[i].push_back(i);
    309         }
    310     }
    311 }
    312 
    313 void solve() {
    314     long long N, K; cin >> N >> K;
    315     long long aa = 0;
    316     vector<long long> dp(N+1,1e18);
    317     for (long long i = 1; i <= N; i++) {
    318         if (i<=K) {dp[i]=0;}
    319         for (auto x : pf[i]) {dp[i]=min(dp[i],dp[i/x]*x+1);}
    320     }
    321     for (long long i = 0; i < N; i++) {
    322         long long a; cin >> a;
    323         aa+=dp[a];
    324     }
    325     cout << aa << endl;
    326 }
    327 
    328 int main() {
    329     pre();
    330     long long T; cin >> T;
    331     while (T--) {solve();}
    332 }
    333 ```
    334 
    335 **Rate the problem!**
    336 
    337 **Difficulty**
    338 
    339 * Trivial problem
    340 * Easy problem
    341 * Average problem
    342 * Hard problem
    343 * Impossible problem
    344 
    345 **Quality**
    346 
    347 * Excellent problem
    348 * Good problem
    349 * Average problem
    350 * Bad problem
    351 * Horrible problem
    352 
    353 [2266F - MEX Replacement](/contest/2266/problem/F "Codeforces Round 1122 (Div. 3)")
    354 
    355 **Hint 1**
    356 
    357 Work backwards from one copy of the value you want to create.
    358 
    359 **Hint 2**
    360 
    361 Process the values from large to small, and let $q$ be the number of copies of the current value that you need.
    362 
    363 **Hint 3**
    364 
    365 If you need $q$ copies of $x$ but only have $c \lt q$, the missing $q-c$ copies of $x$ each force another copy of every smaller value.
    366 
    367 **Solution**
    368 
    369 We check whether a value $M$ can appear, then binary search the largest valid $M$. The largest initial value is already present, so only larger values need to be checked.
    370 
    371 Work backwards from one copy of $M$. At first we need one copy of every value below it, so set $q=1$ and process the values downwards. Suppose we currently need $q$ copies of $x \gt 0$, and there are $c$ copies of $x$ in the initial multiset. If $c\geq q$, we use $q$ of them and have $c-q$ extras. If $c \lt q$, the missing $q-c$ copies of $x$ each require another copy of every smaller value. Thus, $q$ becomes $q+(q-c)=2q-c$.
    372 
    373 So the transition is $q\leftarrow q+\max(0,q-c)$. Extra positive elements cannot save us at another positive level, but they can all be turned into zeros by taking them alone. We count these extras, and when we reach $0$, the check succeeds exactly when the initial zeros plus all extras are at least $q$.
    374 
    375 Missing values are easy to skip. If there are $d$ missing values in a row, then $q$ doubles $d$ times, so multiply it by $2^d$ at once. We can also cap $q$ once it becomes larger than the total number of elements to avoid overflow.
    376 
    377 If $M$ is possible, then every smaller value is also possible, since all of them have to exist while building $M$. Therefore, binary search works. After sorting the pairs, one check is $O(n)$.
    378 
    379 The complexity is $O(n\log n+n\log C)$ per test case, where $C$ is the binary search range.
    380 
    381 **Bonus**
    382 
    383 Can you get a much smaller upper bound for the binary search?
    384 
    385 **Bonus Answer**
    386 
    387 Let $mx=\max x_i$.
    388 
    389 You only need to search up to about $mx+50$. Once we go much further than $mx$, there are many consecutive missing values, and every missing value doubles $q$, so the required number of elements grows too quickly.
    390 
    391 Thus, we can binary search only on $[mx,mx+50]$, giving $O(n\log 50)$ checks after sorting.
    392 
    393 The exact proof and bound are left to the reader :)
    394 
    395 **Code (C++)**
    396 
    397 ```
    398 #include <bits/stdc++.h>
    399 using namespace std;
    400 
    401 bool check(long long mid, vector<pair<long long, long long>> &A) {
    402     long long n = 1;
    403     long long ex = 0;
    404     long long p = mid;
    405     for (long long i = 0; i < A.size(); i++) {
    406         if (p-A[i].first+(63-__builtin_clzll(n))>60) {return false;}
    407         n<<=(p-A[i].first-1);
    408         if (!A[i].first) {ex+=A[i].second; break;}
    409         if (A[i].second>n) {ex+=A[i].second-n;}
    410         else {n=(n<<1)-A[i].second;}
    411         p=A[i].first;
    412     }
    413     return (ex>=n);
    414 }
    415 
    416 void solve() {
    417     long long N; cin >> N;
    418     vector<pair<long long, long long>> A;
    419     long long lo = 0;
    420     long long hi = 1000000100;
    421     for (long long i = 0; i < N; i++) {
    422         long long a, b; cin >> a >> b;
    423         A.push_back({a,b});
    424         lo=max(lo,a);
    425     }
    426     sort(A.rbegin(),A.rend());
    427     if (A.back().first) {A.push_back({0,0});}
    428     while (lo<hi) {
    429         long long mid = (lo+hi+1)/2;
    430         if (check(mid,A)) {lo=mid;}
    431         else {hi=mid-1;}
    432     }
    433     cout << lo << endl;
    434 }
    435 
    436 int main() {
    437     long long T; cin >> T;
    438     while (T--) {solve();}
    439 }
    440 ```
    441 
    442 **Rate the problem!**
    443 
    444 **Difficulty**
    445 
    446 * Trivial problem
    447 * Easy problem
    448 * Average problem
    449 * Hard problem
    450 * Impossible problem
    451 
    452 **Quality**
    453 
    454 * Excellent problem
    455 * Good problem
    456 * Average problem
    457 * Bad problem
    458 * Horrible problem
    459 
    460 [2266G - Modular Tree](/contest/2266/problem/G "Codeforces Round 1122 (Div. 3)")
    461 
    462 **Hint 1**
    463 
    464 Process the tree from the leaves upward.
    465 
    466 **Hint 2**
    467 
    468 A node can always be brought back to its original value after changing it.
    469 
    470 **Hint 3**
    471 
    472 For every node $i$, its reachable values have the form $(a_i+g_ix)\bmod b_i$ for some integer $x$. Find $g_i$.
    473 
    474 **Solution**
    475 
    476 For every node $u$, let $g_u$ be such that its reachable values are exactly $(a_u+g_ux)\bmod b_u$. We compute $g_u$ from the leaves upward.
    477 
    478 Suppose $v$ is a child of $u$. If $g_v=b_v$, then $v$ is fixed at $a_v$. Otherwise, its value can change from $a_v$ by multiples of $g_v$. Let $S_u$ be the sum of the initial values of all direct children of $u$. We can add $S_u$ to $u$ by leaving all children at their initial values, and every non-fixed child $v$ lets us vary this amount by multiples of $g_v$. Therefore, $g_u=\gcd(b_u,S_u,g_v\text{ for all non-fixed children }v)$.
    479 
    480 For a leaf, this gives $g_u=b_u$, as expected. Once we know $g_u$, the largest reachable value is $a_u+\left\lfloor\frac{b_u-1-a_u}{g_u}\right\rfloor g_u$.
    481 
    482 These maxima can all be achieved together. We can first set a node to its maximum, then continue working strictly inside its children's subtrees without changing that node. So after computing all $g_u$ bottom-up, we simply sum the maximum reachable value of every node.
    483 
    484 The complexity is $O(n\log 10^9)$ per test case.
    485 
    486 **Code (C++)**
    487 
    488 ```
    489 #include <bits/stdc++.h>
    490 using namespace std;
    491 
    492 void dfs(long long node, long long par, vector<long long> &A, vector<long long> &B, vector<long long> &g, vector<vector<long long>> &adj) {
    493     long long gc = 0;
    494     long long tt = 0;
    495     for (auto x : adj[node]) {
    496         if (x != par) {
    497             dfs(x,node,A,B,g,adj);
    498             if (g[x]!=B[x]) {gc=gcd(gc,g[x]);}
    499             tt+=A[x];
    500         }
    501     }
    502     gc=gcd(gc,tt);
    503     gc=gcd(gc,B[node]);
    504     g[node]=gc;
    505 }
    506 
    507 void solve() {
    508     long long N; cin >> N;
    509     vector<long long> A; A.push_back(-1);
    510     vector<long long> B; B.push_back(-1);
    511     vector<vector<long long>> adj(N+1);
    512     for (long long i = 0; i < N; i++) {
    513         long long a; cin >> a;
    514         A.push_back(a);
    515     }
    516     for (long long i = 0; i < N; i++) {
    517         long long a; cin >> a;
    518         B.push_back(a);
    519     }
    520     for (long long i = 0; i < N-1; i++) {
    521         long long a, b; cin >> a >> b;
    522         adj[a].push_back(b);
    523         adj[b].push_back(a);
    524     }
    525     vector<long long> g(N+1); //init to 0 for identity gcd
    526     dfs(1,0,A,B,g,adj);
    527     long long aa = 0;
    528     for (long long i = 1; i <= N; i++) {aa+=((B[i]-A[i]-1)/g[i])*g[i]+A[i];}
    529     cout << aa << endl;
    530 }
    531 
    532 int main() {
    533     long long T; cin >> T;
    534     while (T--) {solve();}
    535 }
    536 ```
    537 
    538 **Rate the problem!**
    539 
    540 **Difficulty**
    541 
    542 * Trivial problem
    543 * Easy problem
    544 * Average problem
    545 * Hard problem
    546 * Impossible problem
    547 
    548 **Quality**
    549 
    550 * Excellent problem
    551 * Good problem
    552 * Average problem
    553 * Bad problem
    554 * Horrible problem
    555 
    556 [2266H - Deque Malfunction](/contest/2266/problem/H "Codeforces Round 1122 (Div. 3)")
    557 
    558 **Hint 1**
    559 
    560 We only need to keep one occurrence of every value $1,2,\ldots,n$. What can we do with every other occurrence?
    561 
    562 **Hint 2**
    563 
    564 Let $t_i$ be the arrival position of the occurrence of $i$ which stays in the final deque. When can $i$ be inserted without a malfunction?
    565 
    566 **Hint 3**
    567 
    568 An element can be inserted normally exactly when $t_i$ is a prefix minimum or a suffix minimum of $t_1,t_2,\ldots,t_n$.
    569 
    570 **Hint 4**
    571 
    572 Fix the position of the global minimum. The prefix minima and suffix minima can be optimized separately.
    573 
    574 **Solution**
    575 
    576 If some value from $1$ to $n$ never appears, the answer is $-1$. Otherwise, choose one occurrence of each value to keep. Every unused occurrence can simply be pushed to an end and immediately removed from that same end.
    577 
    578 Let $t_i$ be the position of the chosen occurrence of $i$. We can push $i$ to the front normally exactly when every chosen value which arrived earlier is larger than $i$, or $t_i \lt \min(t_1,\ldots,t_{i-1})$. Similarly, we can push it to the back exactly when $t_i \lt \min(t_{i+1},\ldots,t_n)$. Thus, a value avoids a malfunction exactly when $t_i$ is a prefix minimum or a suffix minimum. The global minimum is counted in both, so if there are $L$ prefix minima and $R$ suffix minima, we keep $L+R-1$ values for free.
    579 
    580 Now optimize the prefix minima. Process the values $1,2,\ldots,n$. Let $dp[p]$ be the maximum number of prefix minima so far when the smallest chosen arrival position is $p$. For an occurrence at position $t$, making it the new minimum gives $new[t]=1+\max_{p \gt t}dp[p]$. All of these transitions must be calculated before adding the states for the current value.
    581 
    582 An old state with minimum $p$ can stay unchanged only if the current value has some occurrence after $p$. If $last_i$ is its last occurrence, every state with $p \gt last_i$ must therefore be deleted. For value $1$, every occurrence simply starts with value $1$.
    583 
    584 After all values are processed, let $L[p]$ be the best number of prefix minima whose global minimum is at position $p$. Run the same DP with the values in reverse order to get $R[p]$ for suffix minima. For a fixed $p$, the two sides can be combined independently, sharing only the global minimum itself. Therefore, the maximum number of values which avoid a malfunction is $\max_p(L[p]+R[p]-1)$, and the answer is $n-\max_p(L[p]+R[p]-1)$.
    585 
    586 **Implementation 1: Lazy Segment Tree**
    587 
    588 Store the DP in a segment tree. For an occurrence $t$, the transition needs the maximum on $(t,m]$. After calculating all transitions for the current value, clear the suffix after $last_i$ and insert the new states.
    589 
    590 A lazy segment tree supports the suffix clear and range maximum queries in $O(\log m)$, so the total complexity is $O(m\log m)$.
    591 
    592 **Code (Lazy Segment Tree)**
    593 
    594 ```
    595 #include <bits/stdc++.h>
    596 using namespace std;
    597 
    598 struct lst { //cur range add range max, change accordingly, no need for l,r in range add range mx
    599     vector<int> seg;
    600     vector<bool> tg;
    601     vector<int> lz;
    602     int sz = 1;
    603     int id = 0; //change sent
    604     int acc(int x, int y) {return max(x,y);} //other more complex lst can do range set and range add
    605     void pull(int n) {seg[n]=acc(seg[n<<1],seg[(n<<1)|1]);}
    606     void apply(int n, int l, int r, int v) {seg[n]=v; tg[n]=true; lz[n]=v;} //if something else, change id, acc, apply, and how lz accumulates/replaces in push
    607     void push(int n, int l, int r) {if (!tg[n]) {return;} tg[n]=false; apply(n<<1,l,(l+r)/2,lz[n]); apply((n<<1)|1,(l+r)/2+1,r,lz[n]); lz[n]=0;}
    608     lst(vector<int> A) { //inp 0 index
    609         while (sz<A.size()) {sz<<=1;}
    610         seg.assign(2*sz,id);
    611         tg.assign(2*sz,false); //in case 0 is a range set
    612         lz.assign(2*sz,0);
    613         for (int i = 0; i < A.size(); i++) {seg[sz+i]=A[i];}
    614         for (int i = sz-1; i >= 1; i--) {pull(i);}
    615     }
    616     int qq(int n, int l, int r, int sl, int sr) {
    617         if (sl>r||sr<l) {return id;}
    618         if (l<=sl&&sr<=r) {return seg[n];}
    619         push(n,sl,sr);
    620         return acc(qq(n<<1,l,r,sl,(sl+sr)/2),qq((n<<1)|1,l,r,(sl+sr)/2+1,sr));
    621     }
    622     void uu(int n, int l, int r, int sl, int sr, int v) {
    623         if (sl>r||sr<l) {return;}
    624         if (l<=sl&&sr<=r) {apply(n,sl,sr,v); return;}
    625         push(n,sl,sr);
    626         uu(n<<1,l,r,sl,(sl+sr)/2,v);
    627         uu((n<<1)|1,l,r,(sl+sr)/2+1,sr,v);
    628         pull(n);
    629     }
    630     int q(int l, int r) {return qq(1,l,r,1,sz);}
    631     void u(int l, int r, int v) {uu(1,l,r,1,sz,v);}
    632 };
    633 
    634 void solve() {
    635     int N, M; cin >> N >> M;
    636     vector<int> A;
    637     for (int i = 0; i < N; i++) {
    638         A.push_back(i+1);
    639     }
    640     vector<vector<int>> tt(N+1);
    641     vector<int> ndp1(M+1);
    642     for (int i = 1; i <= M; i++) {
    643         int a; cin >> a;
    644         tt[a].push_back(i);
    645     }
    646     for (int i = 1; i <= N; i++) {
    647         if (tt[i].empty()) {cout << -1 << endl; return;}
    648     }
    649     vector<int> ii(M+1); // one sentinel at end so no RE
    650     lst dp1(ii);
    651     bool f = true;
    652     for (auto x : A) {
    653         for (auto t : tt[x]) {
    654             int rr = dp1.q(t+1,M+1);
    655             ndp1[t]=(rr?rr+1:rr+(f));
    656         }
    657         for (auto t : tt[x]) {
    658             dp1.u(t,t,ndp1[t]);
    659         }
    660         dp1.u(tt[x].back()+1,M+1,0);
    661         if (f) {f=false;}
    662     }
    663     vector<int> ndp2(M+1);
    664     reverse(A.begin(),A.end());
    665     lst dp2(ii);
    666     f=true;
    667     for (auto x : A) {
    668         for (auto t : tt[x]) {
    669             int rr = dp2.q(t+1,M+1);
    670             ndp2[t]=(rr?rr+1:rr+(f));
    671         }
    672         for (auto t : tt[x]) {
    673             dp2.u(t,t,ndp2[t]);
    674         }
    675         dp2.u(tt[x].back()+1,M+1,0);
    676         if (f) {f=false;}
    677     }
    678     int aa = 0;
    679     for (int i = 1; i <= M; i++) {aa=max(aa,dp1.q(i,i)+dp2.q(i,i)-1);}
    680     cout << N-aa << endl;
    681 }
    682 
    683 int main() {
    684     int T; cin >> T;
    685     while (T--) {solve();}
    686 }
    687 ```
    688 
    689 **Implementation 2: Amortized Set Deletion**
    690 
    691 We can also use a normal segment tree together with a set of active positions. Whenever a state with position greater than $last_i$ becomes invalid, remove the largest such position from the set and set its segment tree value to $0$.
    692 
    693 Each position is inserted once and deleted at most once in one pass, so there are only $O(m)$ deletions in total. The total complexity is again $O(m\log m)$.
    694 
    695 **Code (Amortized Set Deletion)**
    696 
    697 ```
    698 #include <bits/stdc++.h>
    699 using namespace std;
    700 
    701 struct tri { //inp zero index vector, transformed to 1 index
    702     vector<int> s;
    703     int sz = 1;
    704     tri(vector<int> &A) {
    705         while (sz<A.size()) {sz<<=1;}
    706         s.assign(2*sz,0);
    707         for (int i = 0; i < A.size(); i++) {s[i+sz] = A[i];}
    708         for (int i = sz-1; i >= 1; i--) {s[i]=max(s[i<<1],s[(i<<1)|1]);}
    709     }
    710     void u(int i, int x) {
    711         int p = sz+i-1; s[p] = x;
    712         for (p>>=1; p; p>>=1) {s[p]=max(s[p<<1],s[(p<<1)|1]);}
    713     }
    714     int aa(int n, int l, int r, int sl, int sr) {
    715         if (l<=sl&&sr<=r) {return s[n];}
    716         else if (sr<l||sl>r) {return 0;}
    717         else {return max(aa(n<<1,l,r,sl,(sl+sr)>>1),aa((n<<1)|1,l,r,((sl+sr)>>1)+1,sr));}
    718     }
    719     int q(int l, int r) {return aa(1,l,r,1,sz);}
    720 };
    721 
    722 void solve() {
    723     int N, M; cin >> N >> M;
    724     vector<int> A;
    725     for (int i = 0; i < N; i++) {
    726         A.push_back(i+1);
    727     }
    728     vector<vector<int>> tt(N+1);
    729     vector<int> ndp1(M+1);
    730     for (int i = 1; i <= M; i++) {
    731         int a; cin >> a;
    732         tt[a].push_back(i);
    733     }
    734     for (int i = 1; i <= N; i++) {
    735         if (tt[i].empty()) {cout << -1 << endl; return;}
    736     }
    737     vector<int> ii(M+1); // one sentinel at end so no RE
    738     tri dp1(ii);
    739     set<int> act;
    740     bool f = true;
    741     for (auto x : A) {
    742         for (auto t : tt[x]) {
    743             int rr = dp1.q(t+1,M+1);
    744             ndp1[t]=(rr?rr+1:rr+(f));
    745         }
    746         for (auto t : tt[x]) {
    747             dp1.u(t,ndp1[t]);
    748             act.insert(t);
    749         }
    750         while (!act.empty()&&(*act.rbegin()>tt[x].back())) {dp1.u((*act.rbegin()),0); act.erase(*act.rbegin());}
    751         if (f) {f=false;}
    752     }
    753     vector<int> ndp2(M+1);
    754     act.clear();
    755     reverse(A.begin(),A.end());
    756     tri dp2(ii);
    757     f=true;
    758     for (auto x : A) {
    759         for (auto t : tt[x]) {
    760             int rr = dp2.q(t+1,M+1);
    761             ndp2[t]=(rr?rr+1:rr+(f));
    762         }
    763         for (auto t : tt[x]) {
    764             dp2.u(t,ndp2[t]);
    765             act.insert(t);
    766         }
    767         while (!act.empty()&&(*act.rbegin()>tt[x].back())) {dp2.u((*act.rbegin()),0); act.erase(*act.rbegin());}
    768         if (f) {f=false;}
    769     }
    770     int aa = 0;
    771     for (int i = 1; i <= M; i++) {aa=max(aa,dp1.q(i,i)+dp2.q(i,i)-1);}
    772     cout << N-aa << endl;
    773 }
    774 
    775 int main() {
    776     int T; cin >> T;
    777     while (T--) {solve();}
    778 }
    779 ```
    780 
    781 **Rate the problem!**
    782 
    783 **Difficulty**
    784 
    785 * Trivial problem
    786 * Easy problem
    787 * Average problem
    788 * Hard problem
    789 * Impossible problem
    790 
    791 **Quality**
    792 
    793 * Excellent problem
    794 * Good problem
    795 * Average problem
    796 * Bad problem
    797 * Horrible problem