2064.md (24236B)
1 Source: https://codeforces.com/blog/entry/138912 2 3 Thank you everyone for participating! 4 5 [2064A - Brogramming Contest](/contest/2064/problem/A "Codeforces Round 1005 (Div. 2)"): 6 7 **Solution** 8 9 Notice that if $s$ starts with a $1$ we must move the entire string $s$ to $t$ at some point. Also Notice that if we perform the operation, the total number of occurrences of $01$ and $10$ across both strings can only decrease by one. This gives us an upper bound on the answer being the number of occurrences of $01$ and $10$ in $s$ adding one to this if it starts with the character $1$. 10 11 Now the following construction uses the same number of moves as the upper bound (thus showing it is the minimum number of moves): If $s$ begins with $1$ then select the entire string $s$ and move it to $t$. Then repeatedly find the first character in $s$ or $t$ which is not equal to the character before it (note under this construction such an index can only exist in one string at a time) and selected the suffix starting from this character and move it to the other string. During this construction some prefix of $s$ will contain $0$s and some prefix of $t$ will contain $1$s, so after each move the total number of $01$ and $10$ will decrease. 12 13 So the answer to this problem will be the number of $01$ and $10$ in $s$ adding one to the answer if it starts with $1$. 14 15 **Code(c++)** 16 17 ``` 18 #include<bits/stdc++.h> 19 using namespace std; 20 typedef long long ll; 21 #define debug(x) cout << #x << " = " << x << "\n"; 22 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 23 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 24 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 25 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 26 27 void solve(){ 28 int n; 29 cin >> n; 30 31 string s; 32 cin >> s; 33 34 int ans = 0; 35 for (int i = 0; i < n - 1; i++) { 36 if (s[i] != s[i + 1]) ans++; 37 } 38 39 if (s[0] == '1') ans++; 40 cout << ans << "\n"; 41 } 42 43 int main(){ 44 ios::sync_with_stdio(false); 45 cin.tie(0); 46 cout.tie(0); 47 48 int t; 49 cin >> t; 50 while (t--) solve(); 51 } 52 ``` 53 54 [2064B - Variety is Discouraged](/contest/2064/problem/B "Codeforces Round 1005 (Div. 2)"): 55 56 **Solution** 57 58 The first thing to notice is that if we remove an element from $a$ then our score will never increase. Because removing one element will cause $|a|$ to decrease by $1$ and $\mathrm{distinct}(a)$ will decrease by at most $1$ and so the $|a|$ — $\mathrm{distinct}(a)$ will never increase. This means that we should be trying to removing the longest subarray which does not decrease our score. 59 60 We can see that removing any element which only occurs once in $a$ will never decrease our score, and that removing any element which occurs more than once will always decrease our score. Thus we should try to find the longest subarray of elements which only have $1$ occurrence in $a$ and this will be the answer. This can be calculated with a single loop in $O(n)$. 61 62 **Code(c++)** 63 64 ``` 65 #include<bits/stdc++.h> 66 using namespace std; 67 typedef long long ll; 68 #define debug(x) cout << #x << " = " << x << "\n"; 69 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 70 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 71 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 72 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 73 74 void solve(){ 75 int n; 76 cin >> n; 77 78 vector<int> a(n); 79 for (int &x : a) cin >> x; 80 81 vector<int> freq(n + 1); 82 for (int x : a) freq[x]++; 83 84 vector<int> len(n + 1); 85 len[0] = freq[a[0]] == 1; 86 for (int i = 1; i < n; i++) 87 if (freq[a[i]] == 1) 88 len[i] = len[i - 1] + 1; 89 90 int mx = *max_element(len.begin(), len.end()); 91 if (mx == 0){ 92 cout << "0\n"; 93 return; 94 } 95 96 for (int i = 0; i < n; i++){ 97 if (len[i] == mx){ 98 cout << i - len[i] + 2 << " " << i + 1 << "\n"; 99 return; 100 } 101 } 102 } 103 104 int main(){ 105 ios::sync_with_stdio(false); 106 cin.tie(0); 107 cout.tie(0); 108 109 int t; 110 cin >> t; 111 while (t--) solve(); 112 } 113 ``` 114 115 [2064C - Remove the Ends](/contest/2064/problem/C "Codeforces Round 1005 (Div. 2)") 116 117 **Solution** 118 119 First see that at any point we should either remove the leftmost positive element or the rightmost negative element, as if we were to take a positive element that is not the leftmost one we could have just taken the leftmost one first and had a higher score, a similar argument can be made for taking the rightmost negative element. Now if you do either of these moves some number of times you will always take some prefix of positive numbers and then the remaining suffix of negative numbers, and so to calculate the answer we only need to check all $n + 1$ ways to split the array into a prefix and suffix and take the maximum across them all which is easy to do in $O(n)$. 120 121 **Code(c++)** 122 123 ``` 124 #include<bits/stdc++.h> 125 using namespace std; 126 typedef long long ll; 127 #define debug(x) cout << #x << " = " << x << "\n"; 128 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 129 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 130 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 131 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 132 133 void solve(){ 134 int n; 135 cin >> n; 136 137 vector<int> a(n); 138 for (int &x : a) 139 cin >> x; 140 141 vector<ll> pre(n), suf(n); 142 if (a[0] > 0) 143 pre[0] = a[0]; 144 145 for (int i = 1; i < n; i++){ 146 pre[i] = pre[i - 1]; 147 if (a[i] > 0) 148 pre[i] += a[i]; 149 } 150 151 if (a[n - 1] < 0) 152 suf[n - 1] = -a[n - 1]; 153 154 for (int i = n - 2; i >= 0; i--){ 155 suf[i] = suf[i + 1]; 156 if (a[i] < 0) 157 suf[i] -= a[i]; 158 } 159 160 ll ans = 0; 161 for (int i = 0; i < n; i++) 162 ans = max(ans, pre[i] + suf[i]); 163 164 cout << ans << "\n"; 165 } 166 167 int main(){ 168 ios::sync_with_stdio(false); 169 cin.tie(0); 170 cout.tie(0); 171 172 int t; 173 cin >> t; 174 while (t--) solve(); 175 } 176 ``` 177 178 [2064D - Eating](/contest/2064/problem/D "Codeforces Round 1005 (Div. 2)") 179 180 **Solution** 181 182 First notice that if we are unable to eat the next slime then this slime must have had a $\mathrm{msb}$ (most significant bit) at least as large as the current value of $x$. Subsequently this means that if a slime has a $\mathrm{msb}$ strictly less than $x$ we can always eat it. 183 184 Now see that if we eat a slime with lower $\mathrm{msb}$ than $x$ then the $\mathrm{msb}$ of $x$ will never decrease and that if we eat a slime with equal $\mathrm{msb}$ then $\mathrm{msb}$ of $x$ will decrease, this inspires us to do the following: 185 186 at any point we should eat as many slimes as we can to the left that have smaller $\mathrm{msb}$ (to calculate the new value of $x$ after doing this we can just do any range xor query such as prefix sums), after this the next slime will always have $\mathrm{msb}$ greater than or equal to $x$ and so we will either not be able to eat it or we will eat it $\mathrm{msb}$ of $x$ will decrease. Because the $\mathrm{msb}$ will always decrease after every operation we will only need to do this operation at most $log(x)$ times! 187 188 And so we should try find some way to calculate fast the first slime to our left with $\mathrm{msb}$ greater than or equal to the current $\mathrm{msb}$ of $x$. There are many ways to do this but I would say the cleanest way is to use prefix sums, store for each $i, j$ where $1 \le i \le n, 1 \le j \le log(W)$ (where $W$ is the max value of $w_i$ and $x$), the greatest index before it which has $\mathrm{msb}$ greater than or equal to $j$ call this $\mathrm{pre}_{i, j}$ 189 190 Now we can update it as follows: 191 192 * if $\mathrm{msb}(w_i) \lt j$ then $\mathrm{pre}_{i, j} = \mathrm{pre}_{i - 1, j}$ 193 * else $\mathrm{pre}_{i, j} = i$ 194 195 And so the final complexity is $O((n + q)log(W))$ 196 197 **Code(c++)** 198 199 ``` 200 #include<bits/stdc++.h> 201 using namespace std; 202 typedef long long ll; 203 #define debug(x) cout << #x << " = " << x << "\n"; 204 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 205 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 206 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 207 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 208 209 const int W = 30; 210 211 void solve(){ 212 int n, q; 213 cin >> n >> q; 214 215 vector<int> a(n); 216 for (int &x : a) cin >> x; 217 218 vector<int> pre(n + 1); 219 pre[0] = a[0]; 220 for (int i = 1; i < n; i++){ 221 pre[i] = pre[i - 1] ^a[i]; 222 } 223 224 vector<array<int, W>> last(n); 225 for (int i = 0; i < n; i++){ 226 fill(last[i].begin(), last[i].end(), 0); 227 if (i > 0) last[i] = last[i - 1]; 228 last[i][__lg(a[i])] = i; 229 230 for (int j = W - 2; j >= 0; j--){ 231 last[i][j] = max(last[i][j], last[i][j + 1]); 232 } 233 } 234 235 while (q--) { 236 int x; 237 cin >> x; 238 239 int idx = n - 1; 240 while (idx >= 0 && x > 0){ 241 int msb = __lg(x); 242 243 int nxt = last[idx][msb]; 244 x ^= pre[idx] ^ pre[nxt]; 245 idx = nxt; 246 if (nxt == -1 || a[nxt] > x) break; 247 248 x ^= a[nxt]; 249 idx--; 250 } 251 252 cout << n - idx - 1 << "\n"; 253 } 254 } 255 256 int main(){ 257 ios::sync_with_stdio(false); 258 cin.tie(0); 259 cout.tie(0); 260 261 int t; 262 cin >> t; 263 while (t--) solve(); 264 } 265 ``` 266 267 [2064E - Mycraft Sand Sort](/contest/2064/problem/E "Codeforces Round 1005 (Div. 2)"): 268 269 **Solution** 270 271 The first thing to notice is that the first column of sand will be identical to $c$ after sorting. This means that it must be true that $c' = c$. 272 273 Now that we know $c' = c$ we need to find how many ways we can re-arrange $p$ such that the sand layout is the same. Something we can notice is that $p'$ must be able to obtainable from $p$ by only swapping values of the same colour. This is true because if we remove all sand blocks that are not of any specific colour (i.e. keeping only one colour), then by examining the new sand layout we can find what the values of the colour we didn't remove are. 274 275 Now lets isolate a single colour and try to find the number of ways we can arrange it. One thing we can notice is that we can swap an arbitrary $p_i$ and $p_j$ without changing the final sand layout if and only if every number of different colour between $i$ and $j$ is strictly less than both $p_i$ and $p_j$. After staring at this operation enough you will see that each number in $p_i$ has a certain range of positions it can take. I think the easiest way to calculate this range is to use DSU, iterate in order of $p_i$ and merge with everything it can reach in one move, storing leftmost and rightmost element currently in the component to be fast enough. 276 277 It is important to note that these ranges we are calculating have some form of tree structure, because of how we calculated them every pair of ranges will either not intersect or one will contain the other. This means that if we iterate in order of size and "fix" a position in each range we will calculate the answer. 278 279 There is actually no need to build the tree, and instead we can multiply by the size of each DSU component as we are merging, after each merge decreasing the size of the component by $1$. 280 281 **Code(c++)** 282 283 ``` 284 #include<bits/stdc++.h> 285 using namespace std; 286 typedef long long ll; 287 #define debug(x) cout << #x << " = " << x << "\n"; 288 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 289 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 290 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 291 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 292 293 const int MOD = 998244353; 294 295 template<ll mod> // template was not stolen from https://codeforces.com/profile/SharpEdged 296 struct modnum { 297 static constexpr bool is_big_mod = mod > numeric_limits<int>::max(); 298 299 using S = conditional_t<is_big_mod, ll, int>; 300 using L = conditional_t<is_big_mod, __int128, ll>; 301 302 S x; 303 304 modnum() : x(0) {} 305 modnum(ll _x) { 306 _x %= static_cast<ll>(mod); 307 if (_x < 0) { _x += mod; } 308 x = _x; 309 } 310 311 modnum pow(ll n) const { 312 modnum res = 1; 313 modnum cur = *this; 314 while (n > 0) { 315 if (n & 1) res *= cur; 316 cur *= cur; 317 n /= 2; 318 } 319 return res; 320 } 321 modnum inv() const { return (*this).pow(mod-2); } 322 323 modnum& operator+=(const modnum& a){ 324 x += a.x; 325 if (x >= mod) x -= mod; 326 return *this; 327 } 328 modnum& operator-=(const modnum& a){ 329 if (x < a.x) x += mod; 330 x -= a.x; 331 return *this; 332 } 333 modnum& operator*=(const modnum& a){ 334 x = static_cast<L>(x) * a.x % mod; 335 return *this; 336 } 337 modnum& operator/=(const modnum& a){ return *this *= a.inv(); } 338 339 friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; } 340 friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; } 341 friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; } 342 friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; } 343 344 friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; } 345 friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; } 346 friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; } 347 348 friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; } 349 friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; } 350 }; 351 352 using mint = modnum<MOD>; 353 354 template <class T> struct SegTree{ 355 vector<T> seg; 356 int n; 357 const T ID = 0; 358 359 T cmb(T a, T b){ 360 return max(a, b); 361 } 362 363 SegTree(int _n){ 364 n = 1; 365 while (n < _n) n *= 2; 366 seg.assign(2 * n + 1, ID); 367 } 368 369 void set(int pos, T val){ 370 seg[pos + n] = val; 371 } 372 373 void build(){ 374 for (int i = n - 1; i >= 1; i--) seg[i] = cmb(seg[2 * i], seg[2 * i + 1]); 375 } 376 377 void upd(int v, int tl, int tr, int pos, T val){ 378 if (tl == tr){ 379 seg[v] = val; 380 } else { 381 int tm = (tl + tr) / 2; 382 if (pos <= tm) upd(2 * v, tl, tm, pos, val); 383 else upd(2 * v + 1, tm + 1, tr, pos, val); 384 seg[v] = cmb(seg[2 * v], seg[2 * v + 1]); 385 } 386 } 387 388 void upd(int pos, T val){ 389 upd(1, 0, n - 1, pos, val); 390 } 391 392 T query(int v, int tl, int tr, int l, int r){ 393 if (l > r) return ID; 394 if (l == tl && r == tr) return seg[v]; 395 int tm = (tl + tr) / 2; 396 T res = query(2 * v, tl, tm, l, min(tm, r)); 397 res = cmb(res, query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r)); 398 return res; 399 } 400 401 T query(int l, int r){ 402 return query(1, 0, n - 1, l, r); 403 } 404 }; 405 406 struct DSU{ 407 vector<int> p, sz, used, mn, mx; 408 409 DSU(int n){ 410 p.assign(n, 0); 411 sz.assign(n, 1); 412 used.assign(n, 0); 413 mx.assign(n, 0); 414 mn.assign(n, 0); 415 416 for (int i = 0; i < n; i++) p[i] = i; 417 } 418 419 int find(int u){ 420 if (p[u] == u) return u; 421 p[u] = find(p[u]); 422 return p[u]; 423 } 424 425 void unite(int u, int v){ 426 u = find(u); 427 v = find(v); 428 if (u == v) return; 429 430 if (sz[u] < sz[v]) swap(u, v); 431 p[v] = u; 432 sz[u] += sz[v]; 433 used[u] += used[v]; 434 mn[u] = min(mn[u], mn[v]); 435 mx[u] = max(mx[u], mx[v]); 436 } 437 438 bool same(int u, int v){ 439 return find(u) == find(v); 440 } 441 442 int size(int u){ 443 u = find(u); 444 return sz[u]; 445 } 446 }; 447 448 void solve(){ 449 int n; 450 cin >> n; 451 452 vector<int> a(n), b(n); 453 for (int &x : a) cin >> x; 454 for (int &x : b) cin >> x; 455 456 vector<vector<int>> col(n + 1); 457 for (int i = 0; i < n; i++){ 458 col[b[i]].push_back(i); 459 } 460 461 vector<vector<int>> ord(n + 1); 462 463 for (int i = 0; i <= n; i++){ 464 ord[i] = col[i]; 465 sort(ord[i].begin(), ord[i].end(), [&](int x, int y) -> bool{ 466 return a[x] < a[y]; 467 }); 468 } 469 470 SegTree<int> seg(n); 471 for (int i = 0; i < n; i++){ 472 seg.set(i, a[i]); 473 } seg.build(); 474 475 mint ans = 1; 476 DSU dsu(n); 477 for (int i = 0; i <= n; i++){ 478 for (int j = 0; j < col[i].size(); j++){ 479 dsu.mn[col[i][j]] = j; 480 dsu.mx[col[i][j]] = j; 481 } 482 } 483 484 for (int i = 0; i <= n; i++){ 485 for (int x : ord[i]) seg.upd(x, 0); 486 487 for (int x : ord[i]){ 488 int idx = lower_bound(col[i].begin(), col[i].end(), x) - col[i].begin(); 489 for (int j = idx + 1; j < col[i].size(); j++){ 490 if (seg.query(x, col[i][j]) >= a[x]) break; 491 492 dsu.unite(x, col[i][j]); 493 j = dsu.mx[dsu.find(x)]; 494 } 495 496 for (int j = idx - 1; j >= 0; j--){ 497 if (seg.query(col[i][j], x) >= a[x]) break; 498 499 dsu.unite(x, col[i][j]); 500 j = dsu.mn[dsu.find(x)]; 501 } 502 503 int u = dsu.find(x); 504 ans *= dsu.size(u) - dsu.used[u]; 505 dsu.used[u]++; 506 } 507 508 for (int x : ord[i]) seg.upd(x, a[x]); 509 } 510 511 cout << ans << "\n"; 512 } 513 514 int main(){ 515 ios::sync_with_stdio(false); 516 cin.tie(0); 517 cout.tie(0); 518 519 int t; 520 cin >> t; 521 while (t--) solve(); 522 } 523 ``` 524 525 [2064F - We Be Summing](/contest/2064/problem/F "Codeforces Round 1005 (Div. 2)") 526 527 **Solution** 528 529 For an arbitrary array $b$ first notice that $\min(b_1,\ldots,b_i)$ and $\max(b_{i + 1},\ldots,n)$ is both non-increasing as we increase $i$. This means that if an array $b$ is epic then there exists a unique pair of integers $x, y$ such that $x + y = k$ and there exists $i, (1 \le i \lt |b|)$ such that $\min(b_1,\ldots,b_i) = x$ and $\max(b_{i + 1},\ldots,n) = y$. 530 531 Lets call an array $b$ $x$-epic if it is epic due to the pair $x, k - x$. Because the pair $x, y$ is unique, the answer will be equivalent to the sum of all $x$-epic subarrays of $a$. So lets try to find this sum. 532 533 Lets say we are trying to find the sum of all $x$ epic subarrays for a given $x$ and let $y = k - x$. Firstly the subarray must obviously contain both $x$ and $y$, so lets try to find for each $i$ the number of subarrays that are epic where $a_i$ is the first instance of $x$ in the subarray. Notice that it must be true that the first element smaller than $x$ must come after the last element bigger than $y$. Notice also that there cannot be an element bigger than $y$ after the last instance of $y$. 534 535 So we should store for each index $j$ such that $p_j = y$ the length of the longest consecutive sequence of elements strictly less than $y$, which contains $j$ as its leftmost element. Then for each $i$ where $p_i = x$ we should binary search for the last time where first element smaller than $x$ after the last element bigger than $y$. Once we can use prefix sums to find the number of possible right positions of the subarray. To find the number of possible left positions of the subarray it is just the length of the longest consecutive interval which only contains element strictly larger than $x$ and contain $i$ as its right most element. Now we know the number of possible left endpoints of the subarray and right endpoints, so we can just add their product to the answer. 536 537 After doing this across all $i$ we will have the answer. 538 539 **Code(c++)** 540 541 ``` 542 #include<bits/stdc++.h> 543 using namespace std; 544 typedef long long ll; 545 #define debug(x) cout << #x << " = " << x << "\n"; 546 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 547 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 548 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 549 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 550 551 template <class T> struct SegTree{ 552 vector<T> seg; 553 int n; 554 const T ID = {INT_MAX, -INT_MAX}; 555 556 T cmb(T a, T b){ 557 array<int, 2> res; 558 res[0] = min(a[0], b[0]); 559 res[1] = max(a[1], b[1]); 560 return res; 561 } 562 563 SegTree(int _n){ 564 n = 1; 565 while (n < _n) n *= 2; 566 seg.assign(2 * n + 1, ID); 567 } 568 569 void set(int pos, T val){ 570 seg[pos + n] = val; 571 } 572 573 void build(){ 574 for (int i = n - 1; i >= 1; i--) seg[i] = cmb(seg[2 * i], seg[2 * i + 1]); 575 } 576 577 void upd(int v, int tl, int tr, int pos, T val){ 578 if (tl == tr){ 579 seg[v] = val; 580 } else { 581 int tm = (tl + tr) / 2; 582 if (pos <= tm) upd(2 * v, tl, tm, pos, val); 583 else upd(2 * v + 1, tm + 1, tr, pos, val); 584 seg[v] = cmb(seg[2 * v], seg[2 * v + 1]); 585 } 586 } 587 588 void upd(int pos, T val){ 589 upd(1, 0, n - 1, pos, val); 590 } 591 592 T query(int v, int tl, int tr, int l, int r){ 593 if (l > r) return ID; 594 if (l == tl && r == tr) return seg[v]; 595 int tm = (tl + tr) / 2; 596 T res = query(2 * v, tl, tm, l, min(tm, r)); 597 res = cmb(res, query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r)); 598 return res; 599 } 600 601 T query(int l, int r){ 602 return query(1, 0, n - 1, l, r); 603 } 604 }; 605 606 void solve(){ 607 int n, k; 608 cin >> n >> k; 609 610 vector<int> a(n); 611 for (int &x : a) cin >> x; 612 613 vector<vector<int>> p(n + 1); 614 for (int i = 0; i < n; i++) 615 p[a[i]].push_back(i); 616 617 vector<array<int, 2>> stk; 618 vector<int> small_l(n, -1), small_r(n, n), big_l(n, -1), big_r(n, n); 619 620 for (int i = 0; i < n; i++){ 621 while (stk.size() && a[i] <= stk.back()[0]) 622 stk.pop_back(); 623 624 if (stk.size()) 625 small_l[i] = stk.back()[1]; 626 stk.push_back({a[i], i}); 627 } 628 629 stk.clear(); 630 for (int i = n - 1; i >= 0; i--){ 631 while (stk.size() && a[i] >= stk.back()[0]) 632 stk.pop_back(); 633 634 if (stk.size()) 635 big_r[i] = stk.back()[1]; 636 stk.push_back({a[i], i}); 637 } 638 639 ll ans = 0; 640 SegTree<array<int, 2>> seg_small(n), seg_big(n); 641 642 for (int x = 1; x <= n; x++){ 643 int y = k - x; 644 if (y > n){ 645 for (int pos : p[x]) 646 seg_small.upd(pos, {pos, pos}); 647 continue; 648 } 649 650 vector<int> pre(p[y].size()); 651 for (int i = 0; i < p[y].size(); i++){ 652 if (i > 0) 653 pre[i] += pre[i - 1]; 654 655 int r = big_r[p[y][i]] - 1; 656 if (i < p[y].size() - 1) 657 r = min(r, p[y][i + 1] - 1); 658 pre[i] += r - p[y][i] + 1; 659 } 660 661 vector<int> first(p[x].size()), last(p[y].size()); 662 for (int i = 0; i < p[x].size(); i++) 663 first[i] = seg_small.query(p[x][i], n - 1)[0]; 664 665 for (int i = 0; i < p[y].size(); i++) 666 last[i] = seg_big.query(0, p[y][i])[1]; 667 668 int prev = -1; 669 for (int i = 0; i < p[x].size(); i++){ 670 int l = p[x][i]; 671 int l_min = small_l[l] + 1; 672 l_min = max(l_min, prev + 1); 673 prev = l; 674 675 int nxt = upper_bound(p[y].begin(), p[y].end(), l) - p[y].begin(); 676 if (nxt == p[y].size()) 677 continue; 678 679 int lo = nxt, hi = p[y].size(); 680 while (lo < hi){ 681 int mid = (lo + hi) / 2; 682 683 int pos = p[y][mid]; 684 if (first[i] <= last[mid]) 685 hi = mid; 686 else 687 lo = mid + 1; 688 } 689 690 lo--; 691 if (lo < nxt) 692 continue; 693 694 int res = pre[lo]; 695 if (nxt > 0) 696 res -= pre[nxt - 1]; 697 698 ans += 1LL * (l - l_min + 1) * res; 699 } 700 701 for (int pos : p[x]) 702 seg_small.upd(pos, {pos, pos}); 703 for (int pos : p[y]) 704 seg_big.upd(pos, {pos, pos}); 705 } 706 707 cout << ans << "\n"; 708 } 709 710 int main(){ 711 ios::sync_with_stdio(false); 712 cin.tie(0); 713 cout.tie(0); 714 715 int t; 716 cin >> t; 717 while (t--) solve(); 718 } 719 ```