codeforces-scrape

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

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 ```