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.

for _ in range(int(input())):
    a,b = map(int,input().split())
    print(b-a)

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.

import sys
input=lambda:sys.stdin.readline().rstrip()

for i in range(int(input())):
    n=int(input())
    print(*reversed([input().index("#")+1 for i in range(n)]))

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:

• $$$\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.

• $$$\lceil \frac{x}{k} \rceil > \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.

for _ in range(int(input())):
    x,y,k = map(int,input().split())
    print(max(2*((x+k-1)//k)-1,2*((y+k-1)//k)))

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.

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.

from collections import Counter
for _ in range(int(input())):
    n = int(input())
    nums = []
    for i in range(n):
        x,y = map(int,input().split())
        nums.append((x,y))
    ans = 0
    b = Counter(x[0] for x in nums)
    check = set(nums)
    for i in b:
        if b[i]==2: ans += n-2
    for p in check:
        if (p[0]-1,p[1]^1) in check and (p[0]+1,p[1]^1) in check: 
            ans +=1
    print(ans)
    

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.

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.

To evaluate $$$a_1 + \dots + a_i$$$ fast, we can use the sum of arithmetic sequence formula.

from collections import Counter
def val(mid):
    val1 = (mid+k-1+k)*mid//2
    val2 = (k+n-1+k)*n//2 - val1
    return val1,val2
for _ in range(int(input())):
    n,k = map(int,input().split())
    lo = 1
    hi = n
    curr = 1
    while lo <= hi:
        mid = (lo+hi)//2
        a,b = val(mid)
        if b>a:
            curr = mid
            lo = mid+1
        else:
            hi = mid-1
    a1,b1 = val(curr)
    a2,b2 = val(curr+1)
    print(min(b1-a1,a2-b2))

import sys
input=sys.stdin.readline

from math import floor,sqrt

f=lambda x: (2*x*x + x*(4*k-2) + (n-n*n-2*k*n))//2

t=int(input())
for _ in range(t):
    n,k=map(int,input().split())
    D=4*k*k + 4*k*(n-1) + (2*n*n-2*n+1)
    i=(floor(sqrt(D))-(2*k-1))//2
    ans=min(abs(f(i)),abs(f(i+1)))
    print(ans) 

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 < i \leq 2n$$$. Now, the $$$j$$$'th element of the $$$i$$$'th rotation is $$$a_{i+j-1}$$$.

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

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n, q;
        cin >> n >> q;
        vector<ll> a(n), ps(1);
        for (ll &r : a) {
            cin >> r;
            ps.push_back(ps.back() + r);
        }
        for (ll &r : a) {
            ps.push_back(ps.back() + r);
        }
        while (q--) {
            ll l, r;
            cin >> l >> r;
            l--; r--;
            ll i = l / n, j = r / n;
            l %= n; r %= n;
            cout << ps[n] * (j - i + 1) - (ps[i + l] - ps[i]) - (ps[j + n] - ps[j + r + 1]) << "\n";
        }
    }
}

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.

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$$$.

#include "bits/stdc++.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define endl '\n'
#define int long long
#define f first
#define mp make_pair
#define s second
using namespace std;

void solve(){
    int n, k, q; cin >> n >> k >> q;
    int a[n + 1]; for(int i = 1; i <= n; i++) cin >> a[i];
    map <int,int> m;
    multiset <int> tot;
    for(int i = 1; i <= n; i++) tot.insert(0);
    for(int i = 1; i < k; i++){
        tot.erase(tot.find(m[a[i] - i]));
        m[a[i] - i]++;
        tot.insert(m[a[i] - i]);
    }
    int ret[n + 1];
    for(int i = k; i <= n; i++){
        tot.erase(tot.find(m[a[i] - i]));
        m[a[i] - i]++;
        tot.insert(m[a[i] - i]);
        int p = i - k + 1;
        ret[p] = k - *tot.rbegin();
        tot.erase(tot.find(m[a[p] - p]));
        m[a[p] - p]--;
        tot.insert(m[a[p] - p]);
    }
    while(q--){
        int l, r ; cin >> l >> r;
        cout << ret[l] << endl;
    }
    tot.clear();
    m.clear();
}

signed main()
{
    fast;
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

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

$$$\sum_{j=l}^{r-k+1} ( \min_{i=l}^{j} c_i)$$$

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$$$.

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

#include "bits/stdc++.h"
#define int long long

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
    os << "[ ";
    for (const auto& elem : vec) {
        os << elem << " ";
    }
    os << "]";
    return os;
}

using namespace std;

int getAns(int& k, multiset<int>& ms) { return k - (*ms.rbegin()); }
struct SegTree {
    int n;
    vector<int> tree, setLazy, begin, end;
    void prop(int i) {
        if (setLazy[i] != -100) {
            setLazy[2 * i + 1] = setLazy[2 * i] = setLazy[i];
            tree[2 * i] = tree[2 * i + 1] =
                setLazy[i] * (end[2 * i + 1] - begin[2 * i + 1] + 1);
            setLazy[i] = -100;
        }
    }
    SegTree(int nn) {
        n = 1;
        while (n < nn) n *= 2;
        tree.resize(2 * n);
        setLazy.resize(2 * n, -100);
        begin.resize(2 * n);
        end.resize(2 * n);
        for (int i = n; i < 2 * n; i++) {
            begin[i] = end[i] = i - n;
        }
        for (int i = n - 1; i > 0; i--) {
            begin[i] = begin[2 * i];
            end[i] = end[2 * i + 1];
        }
    }
    void rangeSet(int i, int amt, int lo, int hi) {
        if (i < n) prop(i);
        if (begin[i] == lo && end[i] == hi) {
            tree[i] = amt * (hi - lo + 1);
            setLazy[i] = amt;
            return;
        }
        if (begin[2 * i] <= hi && end[2 * i] >= lo) {
            rangeSet(2 * i, amt, lo, min(hi, end[2 * i]));
        }
        if (begin[2 * i + 1] <= hi && end[2 * i + 1] >= lo) {
            rangeSet(2 * i + 1, amt, max(lo, begin[2 * i + 1]), hi);
        }
        tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
    int query(int i, int lo, int hi) {
        if (i < n) prop(i);
        if (begin[i] == lo && end[i] == hi) return tree[i];
        int ans = 0;
        if (begin[2 * i] <= hi && end[2 * i] >= lo) {
            ans += query(2 * i, lo, min(end[2 * i], hi));
        }
        if (begin[2 * i + 1] <= hi && end[2 * i + 1] >= lo) {
            ans += query(2 * i + 1, max(lo, begin[2 * i + 1]), hi);
        }
        return ans;
    }
};
signed main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k, q;
        cin >> n >> k >> q;
        vector<int> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i];
            v[i] = v[i] - i;
        }
        vector<int> ans(n);  // ans[i] is answer from i to i+k-1
        map<int, int> mp;
        multiset<int> active;
        for (int i = 0; i < k; i++) {
            if (mp[v[i]] == 0) {
                mp[v[i]] = 1;
                active.insert(1);
            } else {
                active.erase(active.find(mp[v[i]]));
                mp[v[i]]++;
                active.insert(mp[v[i]]);
            }
        }
        ans[0] = getAns(k, active);
        for (int i = k; i < n; i++) {
            // erase v[i-k]
            active.erase(active.find(mp[v[i - k]]));
            mp[v[i - k]]--;
            if (mp[v[i - k]] != 0) active.insert(mp[v[i - k]]);

            if (mp[v[i]] == 0) {
                mp[v[i]] = 1;
                active.insert(1);
            } else {
                active.erase(active.find(mp[v[i]]));
                mp[v[i]]++;
                active.insert(mp[v[i]]);
            }
            ans[i - k + 1] = getAns(k, active);
        }
        vector<array<int, 3>> queries(q);
        vector<int> an(q);
        for (int i = 0; i < q; i++) {
            queries[i][2] = i;
            cin >> queries[i][0] >> queries[i][1];
            queries[i][0]--;
            queries[i][1]--;
            queries[i][0] *= -1;
        }
        sort(begin(queries), end(queries));
        for (int i = 0; i < q; i++) queries[i][0] *= -1;
        SegTree st(n);
        st.rangeSet(1, ans[n - k], n - k, n - k);
        int cur = n - k;
        stack<pair<int, int>> s;
        s.push({ans[n - k], n - k});
        for (int i = 0; i < q; i++) {
            while (cur != queries[i][0]) {
                cur--;
                int here = cur;
                while (s.size() && s.top().first > ans[cur]) {
                    here = s.top().second;
                    s.pop();
                }
                s.push({ans[cur], here});
                st.rangeSet(1, ans[cur], cur, here);
            }
            an[queries[i][2]] =
                st.query(1, queries[i][0], queries[i][1] - k + 1);
        }
        for (auto x : an) cout << x << endl;
    }
}

Let $$$p_i$$$ be the smallest value $$$j>i$$$ such that $$$c_j<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<p_i.$$$ Further, $$$f(h,i)=c_{p_i}$$$ for $$$p_i\le h-k+1<p_{p_i},$$$ and so on.

Now, let $$$w(0,i)=i,$$$ and $$$w(h,i)=p_{w(h-1,i)}$$$ for $$$h>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)).$$$

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].$$$

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.

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
void solve() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(n);
    for (int &r : a) cin >> r;
    vector<int> c(3 * n), v(n);
    multiset<int> s;
    for (int i = 0; i < k; i++) c[a[i] - i + n - 1]++;
    for (int r : c) s.insert(r);
    v[k - 1] = k - *s.rbegin();
    for (int i = k; i < n; i++) {
        int x = a[i] - i + n - 1, y = a[i - k] - i + k + n - 1;
        c[x]++;
        s.erase(s.find(c[x] - 1));
        s.insert(c[x]);
        c[y]--;
        s.erase(s.find(c[y] + 1));
        s.insert(c[y]);
        v[i] = k - *s.rbegin();
    }
    vector<int> l(n, -1);
    stack<pii> t;
    for (int i = k - 1; i < n; i++) {
        while (!t.empty()) {
            if (t.top().se <= v[i]) break;
            l[t.top().fi] = i;
            t.pop();
        }
        t.push({i, v[i]});
    }
    vector<vector<pii>> w(n, vector<pii>(20, {-1, -1}));
    for (int i = n - 1; i >= k - 1; i--) {
        w[i][0].se = l[i];
        if (l[i] < 0) {
            w[i][0].fi = (n - i) * v[i];
            continue;
        }
        w[i][0].fi = (l[i] - i) * v[i];
        for (int j = 1; j < 20; j++) {
            if (w[w[i][j - 1].se][j - 1].se < 0) break;
            w[i][j].se = w[w[i][j - 1].se][j - 1].se;
            w[i][j].fi = w[i][j - 1].fi + w[w[i][j - 1].se][j - 1].fi;
        }
    }
    while (q--) {
        int l, r, ans = 0;
        cin >> l >> r;
        l--;
        r--;
        l += k - 1;
        for (int j = 19; ~j; j--) {
            if (w[l][j].se < 0) continue;
            if (w[l][j].se > r) continue;
            ans += w[l][j].fi;
            l = w[l][j].se;
        }
        cout << ans + v[l] * (r - l + 1) << "\n";
    }
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

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.

#include <bits/stdc++.h>
#define int long long
#define ll long long 
#define pii pair<int,int> 
#define piii pair<pii,pii>
#define fi first
#define se second
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
struct segtree {
    const static int INF = 1e18, INF2 = 0;
    int l, r;
    segtree* lc, * rc;
    int v = INF, v2=0, v3=0, v4=0;
    segtree* getmem();
    segtree() : segtree(-1, -1) {};
    segtree(int l, int r) : l(l), r(r) {
        if (l == r) return;
        int m = (l + r) / 2;
        lc = getmem(); *lc = segtree(l, m);
        rc = getmem(); *rc = segtree(m + 1, r);
    }
    int op(int a, int b) {
        return min(a,b); 
    }
    int op2(int a, int b) {
        return a+b; 
    }
    void add(int qi, int qv, int h, int h4=0) {
        if (r < qi || l > qi) return;
        if (l == r) { if (v==INF) v=qv; v2+=qv, v3+=qv*h; v4+=qv*h4; return;}
        lc->add(qi, qv, h, h4); rc->add(qi, qv, h, h4);
        v = op(lc->v, rc->v);
        v2 = op2(lc->v2, rc->v2); 
        v3 = op2(lc->v3, rc->v3); 
        v4 = op2(lc->v4, rc->v4); 
    }
    int qrr(int ql, int qx) {
        if (v>=qx||r<ql) return 1e9; 
        if (l==r) return l; 
        int k=lc->qrr(ql,qx); 
        if (k<1e9) return k; 
        return rc->qrr(ql,qx); 
    }
    int q2(int ql, int qr) {
        if (l > qr || r < ql) return INF2;
        if (ql <= l && r <= qr) return v2;
        return op2(lc->q2(ql, qr), rc->q2(ql, qr));
    }
    int q3(int ql, int qr) {
        if (l > qr || r < ql) return INF2;
        if (ql <= l && r <= qr) return v3;
        return op2(lc->q3(ql, qr), rc->q3(ql, qr));
    }
    int q4(int ql, int qr) {
        if (l > qr || r < ql) return INF2; 
        if (ql <= l && r <= qr) return v4; 
        return op2(lc->q4(ql, qr), rc->q4(ql, qr)); 
    }
};
segtree mem[2000005];int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }
void solve() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(n);
    for (int &r : a) cin >> r;
    vector<int> c(2 * n), v(n);
    multiset<int> s;
    for (int i = 0; i < k; i++) c[a[i] - i + n - 1]++;
    for (int r : c) s.insert(r);
    v[k - 1] = k - *s.rbegin();
    for (int i = k; i < n; i++) {
        int x = a[i] - i + n - 1, y = a[i - k] - i + k + n - 1;
        c[x]++;
        s.erase(s.find(c[x] - 1));
        s.insert(c[x]);
        c[y]--;
        s.erase(s.find(c[y] + 1));
        s.insert(c[y]);
        v[i] = k - *s.rbegin();
    }
    vector<int> ans(q);
    vector<vector<pii>> w(n); 
    segtree co(0, n+2), lb(0, n+2), e(0,n+2),e2(0,n+2); 
    vector<int> rb(n); 
    stack<int> t; 
    for (int i = 0; i < q; i++) {
        int l,r; cin >> l >> r; 
        w[l+k-2].push_back({i,r-1}); 
    }
    for (int i = n-1; ~i; i--) {
        e.add(i,v[i],i,i*i); 
        int j=min(n,e.qrr(i,v[i])); 
        rb[i]=j; 
        e.add(j-1,-v[i],i,i*i);
        e2.add(j,v[i]*(j-i),i);
        while (!t.empty()) {
            int x=t.top(); 
            if (v[x]<v[i]) break;
            t.pop(); 
            co.add(rb[x],v[x]*(rb[x]-x)*(x-i),0); 
            lb.add(x,v[x]*(x-i),x);
            lb.add(rb[x]-1,-v[x]*(x-i),x); 
            e.add(x,-v[x],x,x*x);
            e.add(rb[x]-1,v[x],x,x*x);
            e2.add(rb[x],-v[x]*(rb[x]-x),x); 
        }
        t.push(i); 
        int l=i;
        for (auto [p,r]:w[i]) {
            int x=e.q2(l,r), y=e.q3(l,r), z=e.q4(l,r);
            int f=y*(r+1)-z, g=x*(r+1)-y; 
            int lx=lb.q2(l,r), ly=lb.q3(l,r); 
            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);
        }
    }
    for (int r:ans) cout << r << "\n";
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t = 1; cin >> t;
	while (t--) solve();
}