codeforces-scrape

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

2009.md (28833B)


      1 Source: https://codeforces.com/blog/entry/133296
      2 
      3 Thanks for participating! Despite the round being unrated, we hope you've enjoyed the problemset. We put a lot of effort into this round :prayge:
      4 
      5 I want to give huge thanks to [Dominater069](/profile/Dominater069 "Международный гроссмейстер Dominater069") and [satyam343](/profile/satyam343 "Кандидат в мастера satyam343") for their heavy contributions to the subtasks of G. If you're participating out of competition, we hope you enjoyed attempting these bonus subtasks. Otherwise, we hope you will enjoy upsolving them!
      6 
      7 [2009A - Минимизировать!](/contest/2009/problem/A "Codeforces Round 971 (Div. 4)")
      8 
      9 Problem Credits: [cry](/profile/cry "Международный мастер cry")   
     10  Analysis: [cry](/profile/cry "Международный мастер cry")
     11 
     12 **Solution** 
     13 
     14 We choose $c$ between $a$ and $b$ $(a \leq c \leq b)$. The distance is $(c - a) + (b - c) = b - a$. Note that the distance does not depend on the the position $c$ at all.
     15 
     16 **Code (Python) (ntarsis30)** 
     17 
     18 ```
     19 for _ in range(int(input())):
     20     a,b = map(int,input().split())
     21     print(b-a)
     22 ```
     23 
     24 [2009B - osu!mania](/contest/2009/problem/B "Codeforces Round 971 (Div. 4)")
     25 
     26 Problem Credits: [cry](/profile/cry "Международный мастер cry")   
     27  Analysis: [cry](/profile/cry "Международный мастер cry")
     28 
     29 **Solution** 
     30 
     31 Implement the statement. Iterate from $n-1$ to $0$ and use the .find() method in std::string in C++ (or .index() in python) to find the '#' character.
     32 
     33 **Code (Python) (chromate00)**
     34 
     35 ```
     36 import sys
     37 input=lambda:sys.stdin.readline().rstrip()
     38 
     39 for i in range(int(input())):
     40     n=int(input())
     41     print(*reversed([input().index("#")+1 for i in range(n)]))
     42 ```
     43 
     44 [2009C - Легенда о лягушке Лее](/contest/2009/problem/C "Codeforces Round 971 (Div. 4)")
     45 
     46 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Кандидат в мастера Proof_by_QED")   
     47  Analysis: [cry](/profile/cry "Международный мастер cry")
     48 
     49 **Solution** 
     50 
     51 Consider the $x$ and $y$ directions separately and calculate the jumps we need in each direction. The number of jumps we need in the $x$ direction is $\lceil \frac{x}{k} \rceil$ and similarily $\lceil \frac{y}{k} \rceil$ in the $y$ direction. Now let's try to combine them to obtain the total number of jumps. Let's consider the following cases:
     52 
     53 * $\lceil \frac{y}{k} \rceil \geq \lceil \frac{x}{k} \rceil$. In this case, there will need to be $\lceil \frac{y}{k} \rceil - \lceil \frac{x}{k} \rceil$ extra jumps in the $y$ direction. While Freya performs these extra jumps, she will choose $d = 0$ for the $x$ direction. In total, there will need to be $2 \cdot \lceil \frac{y}{k} \rceil$ jumps.
     54 * $\lceil \frac{x}{k} \rceil \gt \lceil \frac{y}{k} \rceil$. We can use the same reasoning as the previous case, but there's a catch. Since Freya is initially facing the $x$ direction, for the last jump, she does not need to jump in the $y$ direction. In total, there will need to be $2 \cdot \lceil \frac{x}{k} \rceil - 1$ jumps.
     55 
     56 **Code (Python) (ntarsis30)**
     57 
     58 ```
     59 for _ in range(int(input())):
     60     x,y,k = map(int,input().split())
     61     print(max(2*((x+k-1)//k)-1,2*((y+k-1)//k)))
     62 ```
     63 
     64 [2009D - Сатьям и подсчет](/contest/2009/problem/D "Codeforces Round 971 (Div. 4)")
     65 
     66 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Кандидат в мастера Proof_by_QED")   
     67  Analysis: [cry](/profile/cry "Международный мастер cry")
     68 
     69 **Solution** 
     70 
     71 Initially, the obvious case one might first consider is an upright right triangle (specifically, the triangle with one of its sides parallel to the $y$-axis). This side can only be made with two points in the form $(x, 0)$ and $(x,1)$. We only need to search third point. Turns out, the third point can be any other unused vertex! If the third point has $y = 0$, then it will be an upright triangle, but if the third point has $y = 1$, it will simply be upside down.
     72 
     73 One of the other case is in the form of $(x,0), (x+1,1), (x+2, 0)$. Let's see why this is a right triangle. Recall that in right triangle, the sum of the squares of two of the sides must equal to the square of the third side. The length between the first and the second point is $\sqrt 2$ because it is the diagonal of $1$ by $1$ unit block. Similarily, the second and third point also has length $\sqrt 2$. Obviously, the length between the first and third point is $2$. Since we have $\sqrt 2^2 + \sqrt 2^2 = 2^2$, this is certainly a right triangle. Of course, we can flip the $y$ values of each point and it will still be a valid right triangle, just upside down.
     74 
     75 **Code (Python) (ntarsis30)**
     76 
     77 ```
     78 from collections import Counter
     79 for _ in range(int(input())):
     80     n = int(input())
     81     nums = []
     82     for i in range(n):
     83         x,y = map(int,input().split())
     84         nums.append((x,y))
     85     ans = 0
     86     b = Counter(x[0] for x in nums)
     87     check = set(nums)
     88     for i in b:
     89         if b[i]==2: ans += n-2
     90     for p in check:
     91         if (p[0]-1,p[1]^1) in check and (p[0]+1,p[1]^1) in check: 
     92             ans +=1
     93     print(ans)
     94 ```
     95 
     96 [2009E - СУПЕР ДУПЕР БОЛЬШОЙ Массив Кли!!!](/contest/2009/problem/E "Codeforces Round 971 (Div. 4)")
     97 
     98 Problem Credits: [cry](/profile/cry "Международный мастер cry")   
     99  Analysis: [cry](/profile/cry "Международный мастер cry")
    100 
    101 **Solution** 
    102 
    103 We can rewrite $x$ as $|a_1+\dots+a_i-(a_{i+1}+\dots+a_n)|$. Essentially, we want to minimize the absolute value difference between the sums of the prefix and the suffix. With absolute value problems. it's always good to consider the positive and negative cases separately. We will consider the prefix greater than the suffix separately with the less than case.
    104 
    105 We can use binary search to search for the greatest $i$ such that $a_1 + \dots + a_i \leq a_{i+1} + \dots + a_n$. Note that here, the positive difference is minimized. If we move to $i+1$, then the negative difference is minimized (since the sum of prefix will now be less than the sum of suffix). The answer is the minimum absolute value of both cases.
    106 
    107 To evaluate $a_1 + \dots + a_i$ fast, we can use the sum of arithmetic sequence formula.
    108 
    109 **Code (Python) (ntarsis30)**
    110 
    111 ```
    112 from collections import Counter
    113 def val(mid):
    114     val1 = (mid+k-1+k)*mid//2
    115     val2 = (k+n-1+k)*n//2 - val1
    116     return val1,val2
    117 for _ in range(int(input())):
    118     n,k = map(int,input().split())
    119     lo = 1
    120     hi = n
    121     curr = 1
    122     while lo <= hi:
    123         mid = (lo+hi)//2
    124         a,b = val(mid)
    125         if b>a:
    126             curr = mid
    127             lo = mid+1
    128         else:
    129             hi = mid-1
    130     a1,b1 = val(curr)
    131     a2,b2 = val(curr+1)
    132     print(min(b1-a1,a2-b2))
    133 ```
    134 
    135 Bonus: Solve in $\mathcal{O}(1)$.
    136 
    137 **Code (Python) (Non-origination)**
    138 
    139 ```
    140 import sys
    141 input=sys.stdin.readline
    142 
    143 from math import floor,sqrt
    144 
    145 f=lambda x: (2*x*x + x*(4*k-2) + (n-n*n-2*k*n))//2
    146 
    147 t=int(input())
    148 for _ in range(t):
    149     n,k=map(int,input().split())
    150     D=4*k*k + 4*k*(n-1) + (2*n*n-2*n+1)
    151     i=(floor(sqrt(D))-(2*k-1))//2
    152     ans=min(abs(f(i)),abs(f(i+1)))
    153     print(ans)
    154 ```
    155 
    156 [2009F - Запросы Светлячка](/contest/2009/problem/F "Codeforces Round 971 (Div. 4)")
    157 
    158 Problem Credits: [cry](/profile/cry "Международный мастер cry")   
    159  Analysis: [cry](/profile/cry "Международный мастер cry")
    160 
    161 **Solution** 
    162 
    163 Let's duplicate the array $a$ and concatenate it with itself. Now, $a$ should have length $2n$ and $a_i = a_{i-n}$ for all $n \lt i \leq 2n$. Now, the $j$'th element of the $i$'th rotation is $a_{i+j-1}$.
    164 
    165 It can be shown for any integer $x$, it belongs in rotation $\lfloor \frac{x-1}{n} \rfloor + 1$ and at position $(x-1) \mod n + 1$. Let $rl$ denote the rotation for $l$ and $rr$ denote the rotation for $r$. If $rr - rl \gt 1$, we are adding $rr-rl-1$ full arrays to our answer. The leftovers is just the suffix of rotation $rl$ starting at position $l$ and the prefix of rotation of $rr$ starting at position $r$. This can be done with prefix sums. You may need to handle $rl=rr$ separately.
    166 
    167 **Code (C++) (awesomeguy856)**
    168 
    169 ```
    170 #include <bits/stdc++.h>
    171 using namespace std;
    172 #define ll long long
    173 int main() {
    174     int t;
    175     cin >> t;
    176     while (t--) {
    177         ll n, q;
    178         cin >> n >> q;
    179         vector<ll> a(n), ps(1);
    180         for (ll &r : a) {
    181             cin >> r;
    182             ps.push_back(ps.back() + r);
    183         }
    184         for (ll &r : a) {
    185             ps.push_back(ps.back() + r);
    186         }
    187         while (q--) {
    188             ll l, r;
    189             cin >> l >> r;
    190             l--; r--;
    191             ll i = l / n, j = r / n;
    192             l %= n; r %= n;
    193             cout << ps[n] * (j - i + 1) - (ps[i + l] - ps[i]) - (ps[j + n] - ps[j + r + 1]) << "\n";
    194         }
    195     }
    196 }
    197 ```
    198 
    199 [2009G1 - Запросы подмассивов Юнли (простая версия)](/contest/2009/problem/G1 "Codeforces Round 971 (Div. 4)")
    200 
    201 Problem Credits: [cry](/profile/cry "Международный мастер cry"), [Proof_by_QED](/profile/Proof_by_QED "Кандидат в мастера Proof_by_QED")   
    202  Analysis: [Proof_by_QED](/profile/Proof_by_QED "Кандидат в мастера Proof_by_QED")
    203 
    204 **Solution** 
    205 
    206 We first make the sequence $b_i=a_i-i$ for all $i$. Now, if $b_i=b_j$, then $i$ and $j$ are in correct relative order.
    207 
    208 Now, to solve the problem, we precompute the answer for every window of $k$, and then each query is a lookup. We use a sliding window, maintaining a multiset of frequencies of values of $b$ in the current window. To move from the window $[i\ldots i+k-1]$ to $i+1 \ldots i+k$, we lower the frequency of $b_i$ by $1$, and increase the frequency of $b_{i+k}$ by $1$.
    209 
    210 **Code (C++) (yash_9a3b)**
    211 
    212 ```
    213 #include "bits/stdc++.h"
    214 #pragma GCC optimize("O3,unroll-loops")
    215 #pragma GCC target("avx,avx2,sse,sse2")
    216 #define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
    217 #define endl '\n'
    218 #define int long long
    219 #define f first
    220 #define mp make_pair
    221 #define s second
    222 using namespace std;
    223 
    224 void solve(){
    225     int n, k, q; cin >> n >> k >> q;
    226     int a[n + 1]; for(int i = 1; i <= n; i++) cin >> a[i];
    227     map <int,int> m;
    228     multiset <int> tot;
    229     for(int i = 1; i <= n; i++) tot.insert(0);
    230     for(int i = 1; i < k; i++){
    231         tot.erase(tot.find(m[a[i] - i]));
    232         m[a[i] - i]++;
    233         tot.insert(m[a[i] - i]);
    234     }
    235     int ret[n + 1];
    236     for(int i = k; i <= n; i++){
    237         tot.erase(tot.find(m[a[i] - i]));
    238         m[a[i] - i]++;
    239         tot.insert(m[a[i] - i]);
    240         int p = i - k + 1;
    241         ret[p] = k - *tot.rbegin();
    242         tot.erase(tot.find(m[a[p] - p]));
    243         m[a[p] - p]--;
    244         tot.insert(m[a[p] - p]);
    245     }
    246     while(q--){
    247         int l, r ; cin >> l >> r;
    248         cout << ret[l] << endl;
    249     }
    250     tot.clear();
    251     m.clear();
    252 }
    253 
    254 signed main()
    255 {
    256     fast;
    257     int t;
    258     cin >> t;
    259     while(t--){
    260         solve();
    261     }
    262 }
    263 ```
    264 
    265 [2009G2 - Запросы подмассивов Юнли (сложная версия)](/contest/2009/problem/G2 "Codeforces Round 971 (Div. 4)")
    266 
    267 Analysis: Solution 1: [Proof_by_QED](/profile/Proof_by_QED "Кандидат в мастера Proof_by_QED"), Solution 2: [awesomeguy856](/profile/awesomeguy856 "Мастер awesomeguy856")
    268 
    269 **Prologue**
    270 
    271 First, read the solution to the easy version of the problem to compute the answer for every window of $k$. Let $c_i=f([a_i, ..., a_{i+k-1}])$. Now, the problem simplifies to finding
    272 
    273 $\sum_{j=l}^{r-k+1} ( \min_{i=l}^{j} c_i)$
    274 
    275 **Solution 1 (Lazy Segment Tree, Offline)**
    276 
    277 We will answer the queries offline in decreasing order of $l$. We maintain a lazy segment tree. We have a variable $x$ sweeping from $n-k$ to $0$. As the variable sweeps leftwards, in node $i$ of the segment tree, we keep track of $\min_{j=x}^{i}c_i$.
    278 
    279 To decrease the value of $x$, we note that the range $[x-1, y]$ in the segment tree will be set to $c_{x-1}$, where $y$ is the largest value such that $c_y \gt c_{x-1}$ but $c_{y+1}\leq c_{x-1}$ (or $y=n-1$). To find the $y$ for each $x$, we may either walk/binary search in the segment tree, or use a monotonic stack.
    280 
    281 **Code (C++) (vgoofficial)**
    282 
    283 ```
    284 #include "bits/stdc++.h"
    285 #define int long long
    286 
    287 template <typename T>
    288 std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
    289     os << "[ ";
    290     for (const auto& elem : vec) {
    291         os << elem << " ";
    292     }
    293     os << "]";
    294     return os;
    295 }
    296 
    297 using namespace std;
    298 
    299 int getAns(int& k, multiset<int>& ms) { return k - (*ms.rbegin()); }
    300 struct SegTree {
    301     int n;
    302     vector<int> tree, setLazy, begin, end;
    303     void prop(int i) {
    304         if (setLazy[i] != -100) {
    305             setLazy[2 * i + 1] = setLazy[2 * i] = setLazy[i];
    306             tree[2 * i] = tree[2 * i + 1] =
    307                 setLazy[i] * (end[2 * i + 1] - begin[2 * i + 1] + 1);
    308             setLazy[i] = -100;
    309         }
    310     }
    311     SegTree(int nn) {
    312         n = 1;
    313         while (n < nn) n *= 2;
    314         tree.resize(2 * n);
    315         setLazy.resize(2 * n, -100);
    316         begin.resize(2 * n);
    317         end.resize(2 * n);
    318         for (int i = n; i < 2 * n; i++) {
    319             begin[i] = end[i] = i - n;
    320         }
    321         for (int i = n - 1; i > 0; i--) {
    322             begin[i] = begin[2 * i];
    323             end[i] = end[2 * i + 1];
    324         }
    325     }
    326     void rangeSet(int i, int amt, int lo, int hi) {
    327         if (i < n) prop(i);
    328         if (begin[i] == lo && end[i] == hi) {
    329             tree[i] = amt * (hi - lo + 1);
    330             setLazy[i] = amt;
    331             return;
    332         }
    333         if (begin[2 * i] <= hi && end[2 * i] >= lo) {
    334             rangeSet(2 * i, amt, lo, min(hi, end[2 * i]));
    335         }
    336         if (begin[2 * i + 1] <= hi && end[2 * i + 1] >= lo) {
    337             rangeSet(2 * i + 1, amt, max(lo, begin[2 * i + 1]), hi);
    338         }
    339         tree[i] = tree[2 * i] + tree[2 * i + 1];
    340     }
    341     int query(int i, int lo, int hi) {
    342         if (i < n) prop(i);
    343         if (begin[i] == lo && end[i] == hi) return tree[i];
    344         int ans = 0;
    345         if (begin[2 * i] <= hi && end[2 * i] >= lo) {
    346             ans += query(2 * i, lo, min(end[2 * i], hi));
    347         }
    348         if (begin[2 * i + 1] <= hi && end[2 * i + 1] >= lo) {
    349             ans += query(2 * i + 1, max(lo, begin[2 * i + 1]), hi);
    350         }
    351         return ans;
    352     }
    353 };
    354 signed main() {
    355     int t;
    356     cin >> t;
    357     while (t--) {
    358         int n, k, q;
    359         cin >> n >> k >> q;
    360         vector<int> v(n);
    361         for (int i = 0; i < n; i++) {
    362             cin >> v[i];
    363             v[i] = v[i] - i;
    364         }
    365         vector<int> ans(n);  // ans[i] is answer from i to i+k-1
    366         map<int, int> mp;
    367         multiset<int> active;
    368         for (int i = 0; i < k; i++) {
    369             if (mp[v[i]] == 0) {
    370                 mp[v[i]] = 1;
    371                 active.insert(1);
    372             } else {
    373                 active.erase(active.find(mp[v[i]]));
    374                 mp[v[i]]++;
    375                 active.insert(mp[v[i]]);
    376             }
    377         }
    378         ans[0] = getAns(k, active);
    379         for (int i = k; i < n; i++) {
    380             // erase v[i-k]
    381             active.erase(active.find(mp[v[i - k]]));
    382             mp[v[i - k]]--;
    383             if (mp[v[i - k]] != 0) active.insert(mp[v[i - k]]);
    384 
    385             if (mp[v[i]] == 0) {
    386                 mp[v[i]] = 1;
    387                 active.insert(1);
    388             } else {
    389                 active.erase(active.find(mp[v[i]]));
    390                 mp[v[i]]++;
    391                 active.insert(mp[v[i]]);
    392             }
    393             ans[i - k + 1] = getAns(k, active);
    394         }
    395         vector<array<int, 3>> queries(q);
    396         vector<int> an(q);
    397         for (int i = 0; i < q; i++) {
    398             queries[i][2] = i;
    399             cin >> queries[i][0] >> queries[i][1];
    400             queries[i][0]--;
    401             queries[i][1]--;
    402             queries[i][0] *= -1;
    403         }
    404         sort(begin(queries), end(queries));
    405         for (int i = 0; i < q; i++) queries[i][0] *= -1;
    406         SegTree st(n);
    407         st.rangeSet(1, ans[n - k], n - k, n - k);
    408         int cur = n - k;
    409         stack<pair<int, int>> s;
    410         s.push({ans[n - k], n - k});
    411         for (int i = 0; i < q; i++) {
    412             while (cur != queries[i][0]) {
    413                 cur--;
    414                 int here = cur;
    415                 while (s.size() && s.top().first > ans[cur]) {
    416                     here = s.top().second;
    417                     s.pop();
    418                 }
    419                 s.push({ans[cur], here});
    420                 st.rangeSet(1, ans[cur], cur, here);
    421             }
    422             an[queries[i][2]] =
    423                 st.query(1, queries[i][0], queries[i][1] - k + 1);
    424         }
    425         for (auto x : an) cout << x << endl;
    426     }
    427 }
    428 ```
    429 
    430 **Solution 2 (Binary Lifting, Online)**
    431 
    432 Let $p_i$ be the smallest value $j \gt i$ such that $c_j \lt c_i.$ We can calculate these values using a monotonic stack and iterating through $c$ backwards. If such $j$ does not exist, then we let $p_i=n.$ Then $f(h,i)=c_i$ for all $i\le h-k+1 \lt p_i.$ Further, $f(h,i)=c_{p_i}$ for $p_i\le h-k+1 \lt p_{p_i},$ and so on.
    433 
    434 Now, let $w(0,i)=i,$ and $w(h,i)=p_{w(h-1,i)}$ for $h \gt 0.$ To calculate the answer for a query $(l,r),$ consider the largest value of $j$ such that $w(j,l)\le r.$ Then we can take the sum $c_{w(j,l)}\cdot(r-w(j,l)+1)+\sum_{i=1}^jc_{w(i-1,l)}\cdot(w(i,l)-w(i-1,l)).$
    435 
    436 Now it remains to quickly calculate this sum. We can use binary lifting to solve this. Specifically, we create an $n\times20$ data table where $d[i][j]=\sum_{h=1}^{2^j}c_{w(h-1,i)}\cdot(w(h,i)-w(h-1,i)),$ if $w(2^j,i)$ exists, and $-1$ otherwise. We can precompute this table recursively, as $d[i][0]=c_i\cdot(w(1,i)-i)$ and $d[i][j]=d[i][j-1]+d[w(2^{j-1},i)][j-1].$
    437 
    438 Then, to answer queries, we iterate $j$ from $19$ to $0,$ and if $w(2^j,l)\le r,$ we add $d[l][j]$ to our answer, and set $l=w(2^j,l).$ At the end, we add $c_l\cdot(r-l+1)$ to our answer.
    439 
    440 **Code (C++) (awesomeguy856)**
    441 
    442 ```
    443 #include <bits/stdc++.h>
    444 #define int long long
    445 #define pii pair<int, int>
    446 #define fi first
    447 #define se second
    448 using namespace std;
    449 void solve() {
    450     int n, k, q;
    451     cin >> n >> k >> q;
    452     vector<int> a(n);
    453     for (int &r : a) cin >> r;
    454     vector<int> c(3 * n), v(n);
    455     multiset<int> s;
    456     for (int i = 0; i < k; i++) c[a[i] - i + n - 1]++;
    457     for (int r : c) s.insert(r);
    458     v[k - 1] = k - *s.rbegin();
    459     for (int i = k; i < n; i++) {
    460         int x = a[i] - i + n - 1, y = a[i - k] - i + k + n - 1;
    461         c[x]++;
    462         s.erase(s.find(c[x] - 1));
    463         s.insert(c[x]);
    464         c[y]--;
    465         s.erase(s.find(c[y] + 1));
    466         s.insert(c[y]);
    467         v[i] = k - *s.rbegin();
    468     }
    469     vector<int> l(n, -1);
    470     stack<pii> t;
    471     for (int i = k - 1; i < n; i++) {
    472         while (!t.empty()) {
    473             if (t.top().se <= v[i]) break;
    474             l[t.top().fi] = i;
    475             t.pop();
    476         }
    477         t.push({i, v[i]});
    478     }
    479     vector<vector<pii>> w(n, vector<pii>(20, {-1, -1}));
    480     for (int i = n - 1; i >= k - 1; i--) {
    481         w[i][0].se = l[i];
    482         if (l[i] < 0) {
    483             w[i][0].fi = (n - i) * v[i];
    484             continue;
    485         }
    486         w[i][0].fi = (l[i] - i) * v[i];
    487         for (int j = 1; j < 20; j++) {
    488             if (w[w[i][j - 1].se][j - 1].se < 0) break;
    489             w[i][j].se = w[w[i][j - 1].se][j - 1].se;
    490             w[i][j].fi = w[i][j - 1].fi + w[w[i][j - 1].se][j - 1].fi;
    491         }
    492     }
    493     while (q--) {
    494         int l, r, ans = 0;
    495         cin >> l >> r;
    496         l--;
    497         r--;
    498         l += k - 1;
    499         for (int j = 19; ~j; j--) {
    500             if (w[l][j].se < 0) continue;
    501             if (w[l][j].se > r) continue;
    502             ans += w[l][j].fi;
    503             l = w[l][j].se;
    504         }
    505         cout << ans + v[l] * (r - l + 1) << "\n";
    506     }
    507 }
    508 int32_t main() {
    509     ios::sync_with_stdio(0);
    510     cin.tie(0);
    511     int t;
    512     cin >> t;
    513     while (t--) solve();
    514 }
    515 ```
    516 
    517 [2009G3 - Запросы подмассивов Юнли (экстремальная версия)](/contest/2009/problem/G3 "Codeforces Round 971 (Div. 4)")
    518 
    519 Analysis: [Dominater069](/profile/Dominater069 "Международный гроссмейстер Dominater069")
    520 
    521 **Solution** 
    522 
    523 I decided to write the Editorial for this problem in a step-by-step manner. Some of the steps are really short and meant to be used as hints but i decided to have a uniform naming for everything.
    524 
    525 **Step 1**
    526 
    527 Continuing from the easier versions of the problem, we know we need to compute sum of min of subarrays, and answer subarray queries on this. Consider the standard approach of finding sum of min over all subarrays.
    528 
    529 **Step 2**
    530 
    531 Sum of min of all subarrays for a fixed array is a well known problem. Here is how you can solve it, given an array $a$ of length $n$.
    532 
    533 Let $nx_i$ denote the smallest integer $j (j \gt i)$ such that $a_j \lt a_i$ holds, or $n + 1$ if no such integer exists. Similarly, define $pv_i$ denote the largest integer $j (j \lt i)$ such that $a_j \le a_i$ holds, or $0$ if no such integer exists.
    534 
    535 The answer is simply $\sum_{i = 1}^{n} a_i \cdot (nx_i - i) \cdot (i - pv_i)$. Calculating $nx_i$ and $pv_i$ can be done with Monotonic Stack.
    536 
    537 **Step 3**
    538 
    539 Given a query $(L, R)$, divide all indices $i$ ($L \le i \le R$) into $4$ groups depending on the existence of $nx_i$ and $pv_i$ within the interval $[L, R]$, i.e. :
    540 
    541 * Case $1$ : $L \le pv_i, nx_i \le R$
    542 * Case $2$ : $pv_i \lt L, nx_i \le R$
    543 * Case $3$ : $L \le pv_i, nx_i \gt R$
    544 * Case $4$ : $pv_i \lt L, nx_i \gt R$
    545 
    546 Try to calculate the contributions of each of these categories separately.
    547 
    548 **Step 4**
    549 
    550 Case $1$ can be reduced to rectangle queries. Case $4$ is simple to handle as there is atmost $1$ element which satisfies that condition, which (if exists) is the minimum element in the range $(L, R)$ which can be found using any RMQ data structure like Sparse Table or Segment Tree.
    551 
    552 **What is Rectangle Queries?**
    553 
    554 Given a list of $n$ tuples $(l, r, v)$ and $q$ queries $(L, R)$ you have to add $v$ to answer of the $i$-th query if $L \lt = l \lt = r \lt = R$.
    555 
    556 This can be solved in $O((n + q) log(n))$ using Fenwick Tree and Sweepline.
    557 
    558 Iterate from $i = n$ to $i = 1$. For every tuple with left end at $i$ say $(i, j, v)$, add $v$ to a range query sum data structure at position $j$. Then, for every query with left end at $i$, we can simply query the range sum from $i = l$ to $i = r$ to get the required answer.
    559 
    560 **How to reduce Case 1 to Rectangle Queries?**
    561 
    562 For every index $i$ from $1$ to $n$, generate a tuple as $(pv_i, nx_i, a_i \cdot (i - pv_i) \cdot (nx_i - i)$. Then, solve the Rectangle Queries problem with this list of tuples. The answer will be the required contribution of all indices belonging to Case $1$.
    563 
    564 **Step 5**
    565 
    566 This leaves us with Case $2$ and $3$, which are symmetric, so we discuss only case $2$.
    567 
    568 Let us sweepline from $i = n$ to $i = 1$, maintaining a Monotonic Stack of elements, popping elements when we find a smaller element, similar to how we find $pv_i$.
    569 
    570 The indices belonging to Case $2$ are **precisely** the elements present in the Monotonic Stack (obviously ignore any element $ \gt R$) when we have swept till $i = L$, with the possible exception of the minimum in the range $[L, R]$ (that might belong to Case $4$).
    571 
    572 **Step 6**
    573 
    574 Let's analyze the contribution of the indices in Case $2$.
    575 
    576 It is $a_i \cdot (L - i + 1) \cdot (nx_i - i)$.
    577 
    578 Take a look at what happens when we go from $L$ to $L - 1$, how do all the contributions of elements belonging to Case $2$ change.
    579 
    580 **Step 7**
    581 
    582 Some elements get popped from the Monotonic Stack because $a_{L - 1}$. We need to reset the contribution of all these elements to $0$.
    583 
    584 The elements that do not get popped have their contribution increased by exactly $(nx_i - i)$.
    585 
    586 $1$ element gets added to the Monotonic Stack, which is $a_{L - 1}$, so we need to initiliatize its contribution to $(nx_{L - 1} - (L - 1)).$
    587 
    588 **Step 8**
    589 
    590 Resetting and Initiliazing Contribution is simple enough with most data structures, so let us focus on adding $(nx_i - i)$ to the elements present in the Monotonic Stack.
    591 
    592 We can keep a Lazy Segment Tree with $2$ parameters, $sumcon=$ sum of all contributions in this segment tree node, and $addcon = $ sum of $(nx_i - i)$ of all "non-popped" elements in this node. The lazy tag will denote how many contribution increases I have to do. We can simply do $sumcon += lazy * addcon$ for the lazy updates.
    593 
    594 Then, we can query the range sum from $L$ to $R$ to get the sum of contributions of all elements belonging to Case $2$. Case $3$ can be solved in a symmetric way. Adding up the answers over Case $1$, $2$, $3$ and $4$ will give us the required answer.
    595 
    596 **Minor Detail**
    597 
    598 We need to be quite careful with the Case $4$ element, as we might double count its contribution in Case $2$ and $3$. I handle this in the model solution by querying the sum of contribution in $[L, X - 1]$ where $X$ is the largest element present in the monostack which is $\le R$, and handling $X$ separately. You can easily note that $X$ is the only element belonging to Case $4$ (if any at all).
    599 
    600 **Code (C++) (awesomeguy856)**
    601 
    602 ```
    603 #include <bits/stdc++.h>
    604 #define int long long
    605 #define ll long long 
    606 #define pii pair<int,int> 
    607 #define piii pair<pii,pii>
    608 #define fi first
    609 #define se second
    610 #pragma GCC optimize("O3,unroll-loops")
    611 #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
    612 using namespace std;
    613 struct segtree {
    614     const static int INF = 1e18, INF2 = 0;
    615     int l, r;
    616     segtree* lc, * rc;
    617     int v = INF, v2=0, v3=0, v4=0;
    618     segtree* getmem();
    619     segtree() : segtree(-1, -1) {};
    620     segtree(int l, int r) : l(l), r(r) {
    621         if (l == r) return;
    622         int m = (l + r) / 2;
    623         lc = getmem(); *lc = segtree(l, m);
    624         rc = getmem(); *rc = segtree(m + 1, r);
    625     }
    626     int op(int a, int b) {
    627         return min(a,b); 
    628     }
    629     int op2(int a, int b) {
    630         return a+b; 
    631     }
    632     void add(int qi, int qv, int h, int h4=0) {
    633         if (r < qi || l > qi) return;
    634         if (l == r) { if (v==INF) v=qv; v2+=qv, v3+=qv*h; v4+=qv*h4; return;}
    635         lc->add(qi, qv, h, h4); rc->add(qi, qv, h, h4);
    636         v = op(lc->v, rc->v);
    637         v2 = op2(lc->v2, rc->v2); 
    638         v3 = op2(lc->v3, rc->v3); 
    639         v4 = op2(lc->v4, rc->v4); 
    640     }
    641     int qrr(int ql, int qx) {
    642         if (v>=qx||r<ql) return 1e9; 
    643         if (l==r) return l; 
    644         int k=lc->qrr(ql,qx); 
    645         if (k<1e9) return k; 
    646         return rc->qrr(ql,qx); 
    647     }
    648     int q2(int ql, int qr) {
    649         if (l > qr || r < ql) return INF2;
    650         if (ql <= l && r <= qr) return v2;
    651         return op2(lc->q2(ql, qr), rc->q2(ql, qr));
    652     }
    653     int q3(int ql, int qr) {
    654         if (l > qr || r < ql) return INF2;
    655         if (ql <= l && r <= qr) return v3;
    656         return op2(lc->q3(ql, qr), rc->q3(ql, qr));
    657     }
    658     int q4(int ql, int qr) {
    659         if (l > qr || r < ql) return INF2; 
    660         if (ql <= l && r <= qr) return v4; 
    661         return op2(lc->q4(ql, qr), rc->q4(ql, qr)); 
    662     }
    663 };
    664 segtree mem[2000005];int memsz = 0;
    665 segtree* segtree::getmem() { return &mem[memsz++]; }
    666 void solve() {
    667     int n, k, q;
    668     cin >> n >> k >> q;
    669     vector<int> a(n);
    670     for (int &r : a) cin >> r;
    671     vector<int> c(2 * n), v(n);
    672     multiset<int> s;
    673     for (int i = 0; i < k; i++) c[a[i] - i + n - 1]++;
    674     for (int r : c) s.insert(r);
    675     v[k - 1] = k - *s.rbegin();
    676     for (int i = k; i < n; i++) {
    677         int x = a[i] - i + n - 1, y = a[i - k] - i + k + n - 1;
    678         c[x]++;
    679         s.erase(s.find(c[x] - 1));
    680         s.insert(c[x]);
    681         c[y]--;
    682         s.erase(s.find(c[y] + 1));
    683         s.insert(c[y]);
    684         v[i] = k - *s.rbegin();
    685     }
    686     vector<int> ans(q);
    687     vector<vector<pii>> w(n); 
    688     segtree co(0, n+2), lb(0, n+2), e(0,n+2),e2(0,n+2); 
    689     vector<int> rb(n); 
    690     stack<int> t; 
    691     for (int i = 0; i < q; i++) {
    692         int l,r; cin >> l >> r; 
    693         w[l+k-2].push_back({i,r-1}); 
    694     }
    695     for (int i = n-1; ~i; i--) {
    696         e.add(i,v[i],i,i*i); 
    697         int j=min(n,e.qrr(i,v[i])); 
    698         rb[i]=j; 
    699         e.add(j-1,-v[i],i,i*i);
    700         e2.add(j,v[i]*(j-i),i);
    701         while (!t.empty()) {
    702             int x=t.top(); 
    703             if (v[x]<v[i]) break;
    704             t.pop(); 
    705             co.add(rb[x],v[x]*(rb[x]-x)*(x-i),0); 
    706             lb.add(x,v[x]*(x-i),x);
    707             lb.add(rb[x]-1,-v[x]*(x-i),x); 
    708             e.add(x,-v[x],x,x*x);
    709             e.add(rb[x]-1,v[x],x,x*x);
    710             e2.add(rb[x],-v[x]*(rb[x]-x),x); 
    711         }
    712         t.push(i); 
    713         int l=i;
    714         for (auto [p,r]:w[i]) {
    715             int x=e.q2(l,r), y=e.q3(l,r), z=e.q4(l,r);
    716             int f=y*(r+1)-z, g=x*(r+1)-y; 
    717             int lx=lb.q2(l,r), ly=lb.q3(l,r); 
    718             ans[p]=co.q2(l,r+1)+lx*(r+1)-ly+e2.q3(l,r+1)-e2.q2(l,r+1)*(i-1)+f-g*(i-1);
    719         }
    720     }
    721     for (int r:ans) cout << r << "\n";
    722 }
    723 
    724 int32_t main() {
    725 	ios::sync_with_stdio(0); cin.tie(0);
    726 	int t = 1; cin >> t;
    727 	while (t--) solve();
    728 }
    729 ```