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