P15133 [ROIR 2026] 最后的滑动窗口问题
给定长为 \(n\) 的序列 \(a_i\)。进行 \(q\) 次询问，给定 \(l,r,k\)，查询
\[\sum_{[l',r'] \subseteq [l,r] \land r'-l'+1=k} \min_{i \in [l',r']} a_i \]\(n,q \le 10^5\)，2 秒，512 MB。
用单调栈求出 \(a_i\) 成为区间 \(\min\) 的极长区间 \([x_i,y_i]\)，则 \(a_i\) 对询问有贡献，只要 \(l' \in [x_i,i] \land r' \in [i,y_i]\)。
代入 \([l',r'] \subseteq [l,r]\) 和 \(r'=l'+k-1\) 列得关于 \(l'\) 的约束：
- \(l' \in[x_i,i]\)。
- \(l' \in [i-k+1,y_i-k+1]\)。
- \(l' \in [l,r-k+1]\)。
将 \((l',k)\) 映射到二维平面，只考虑前两个条件，画出 \(a_i\) 有贡献的范围：
问题可以描述为，每个 \(i\) 对 \([x_i,i] \times [i+1,y_i+1]\) 的斜 \(45\degree\) 平行四边形 \(+a_i\)。询问给定 \(k\)，对 \(l' \in [l,r-k+1]\) 的线段整点求和。
坐标变换 \((l',k) \to (l',l'+k)\) 将平四拉成 4-side 矩形，查询对 \(y=x+k \land x \in [l,r-k+1]\) 斜 \(45\degree\) 线段求和。
将 4-side 差分到开口向左下的 2-side 矩形。考察斜线询问与矩形界点 \((x_0,y_0)\) 的位置关系：
- 若 \(c，斜线在下方穿过矩形竖边，对 \(x\) 轴上 \([1,x_0]\) 有贡献。
- 若 \(c \ge k\)，斜线在上方穿过矩形横边，对 \(y\) 轴上 \([1,y_0]\) 有贡献。
我们将矩形分成两类处理。用两棵线段树维护 \(x\) 轴和 \(y\) 轴，查询时将斜线投影到坐标轴上，将两类贡献求和就是答案。
使用斜率为 \(1\) 的扫描线 \(y-x=c\) 扫描平面，将矩形 \((x_0,y_0)\) 挂在 \(y_0-x_0\) 上，扫到时切换贡献类型，将 \(x\) 上的贡献撤销并加入 \(y\) 上的贡献即可。
视 \(n,q\) 同阶复杂度 \(O(n \log n)\)。
const int N = 1e5 + 5;
int n, q, a[N], x[N], y[N]; i64 ans[N];void prework() {vector st;for (int i = 1; i <= n; i++) {while (!st.empty() && a[st.back()] > a[i]) st.pop_back();x[i] = st.empty() ? 1 : st.back() + 1, st.pb(i);}st.clear();for (int i = n; i >= 1; i--) {while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();y[i] = st.empty() ? n : st.back() - 1, st.pb(i);}
}struct segtree {#define ls (rt << 1)#define rs (rt << 1 | 1)i64 sum[8*N], tag[8*N];void pushup(int rt) {sum[rt] = sum[ls] + sum[rs];}void apply(int rt, i64 c, int len) {sum[rt] += c * len, tag[rt] += c;}void pushdown(int rt, int ln, int rn) {if (!tag[rt]) return;apply(ls, tag[rt], ln), apply(rs, tag[rt], rn), tag[rt] = 0;}void add(int tl, int tr, int c, int l = 1, int r = 2*n, int rt = 1) {if (tl <= l && r <= tr) return apply(rt, c, r-l+1), void();int mid = (l + r) >> 1; pushdown(rt, mid-l+1, r-mid);if (tl <= mid) add(tl, tr, c, l, mid, ls);if (tr > mid) add(tl, tr, c, mid+1, r, rs);pushup(rt);}i64 ask(int tl, int tr, int l = 1, int r = 2*n, int rt = 1) {if (tl > tr) return 0;if (tl <= l && r <= tr) return sum[rt];int mid = (l + r) >> 1; pushdown(rt, mid-l+1, r-mid);if (tl <= mid && mid < tr) return ask(tl, tr, l, mid, ls) + ask(tl, tr, mid+1, r, rs);return tl <= mid ? ask(tl, tr, l, mid, ls) : ask(tl, tr, mid+1, r, rs);}
} X, Y;vector> P[N]; // (x, y, w)
vector> Q[N]; // (l, r, id)
void add(int x1, int x2, int y1, int y2, int w) {auto push = [](int x, int y, int w) -> void {if (x <= 0 || y <= 0) return;int d = y - x;if (d <= 1) Y.add(1, y, w);else X.add(1, x, w), P[d].pb(x, y, w);};push(x2, y2, +w), push(x1-1, y1-1, +w);push(x2, y1-1, -w), push(x1-1, y2, -w);
}void _main() {cin >> n >> q;for (int i = 1; i <= n; i++) cin >> a[i];prework();for (int i = 1, l, r, k; i <= q; i++) {cin >> l >> r >> k;Q[k].pb(l, r-k+1, i);}for (int i = 1; i <= n; i++) add(x[i], i, i+1, y[i]+1, a[i]);for (int c = 1; c <= n; c++) {for (auto [x, y, w] : P[c]) X.add(1, x, -w), Y.add(1, y, w);for (auto [l, r, id] : Q[c]) ans[id] = X.ask(l, r) + Y.ask(l+c, r+c);}for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}