题解：P15133 [ROIR 2026] 最后的滑动窗口问题

ケロシ · 2026-02-03 12:15:41 · 题解

画一个平面，横轴是 l，纵轴是 k。

考虑一个点 u 的贡献，找出其左边第一个比它小的 pre_u 和右边第一个比它小的 nxt_u，那么贡献形如：

是斜距加，然后是求行区间和。

经典的，先把斜距差分成四个三角加：

然后三角加能拆成两个后缀加：

其中黄色的那个后缀加坐标系是斜的，所以点需要映射到 (u+i,i)。

对 k 扫描线后需要支持区间加区间和，使用树状数组即可，时间复杂度 O(n \log n)。

const int N = 2e5 + 5;
int n, q, a[N];
int stk[N], tp;
int pre[N], nxt[N];
struct Query { int l, r, i; };
VC<Query> e[N];
VC<PII> f[N];
ll ans[N];
struct fenwick {
    ll c[N], d[N];
    inline int lowbit(int x) {
        return - x & x;
    }
    void add(int u, ll x) {
        for(int i = u; i <= n * 2; i += lowbit(i)) {
            c[i] += x;
            d[i] += x * (u - 1);
        }
    }
    ll query(int u) {
        ll res = 0;
        for(int i = u; i; i -= lowbit(i)) {
            res += c[i] * u;
            res -= d[i];
        }
        return res;
    }
    ll query(int l, int r) {
        return query(r) - query(l - 1);
    }
} t1, t2;
void solve() {
    read(n, q);
    FOR(i, 1, n) read(a[i]);
    tp = 0; stk[tp] = 0;
    FOR(i, 1, n) {
        while(tp && a[stk[tp]] >= a[i]) tp --;
        pre[i] = stk[tp];
        stk[++ tp] = i;
    }
    tp = 0; stk[tp] = n + 1;
    ROF(i, n, 1) {
        while(tp && a[stk[tp]] > a[i]) tp --;
        nxt[i] = stk[tp];
        stk[++ tp] = i;
    }
    FOR(i, 1, n) {
        f[1].eb(i, a[i]);
        f[i - pre[i] + 1].eb(pre[i], - a[i]);
        f[nxt[i] - i + 1].eb(i, - a[i]);
        f[nxt[i] - pre[i] + 1].eb(pre[i], a[i]);
    }
    FOR(i, 1, q) {
        INT(l, r, k);
        e[k].pb({l, r - k + 1, i});
    }
    FOR(i, 1, n) {
        for(auto [u, x] : f[i]) {
            if(u < 1) continue;
            t1.add(u + 1, - x);
            t2.add(u + i, x);
        }
        for(auto h : e[i]) {
            int l = h.l, r = h.r;
            ans[h.i] += t1.query(l, r);
            ans[h.i] += t2.query(l + i, r + i);
        }
    }
    FOR(i, 1, q) print(ans[i]);
}