https://www.luogu.org/problem/P3488
根据Hall定理 左边任意一个区间L-R a[i]的和sum[l~r] 都要<= (R-L+1+d)*K
把(R-L+1)*K 挪到左边 即为 对任意L-R区间 有 $\sum_{i=L}^R{(a[i]-k)} \le K*D$
然后用线段树最大字段和去维护它即可
#include<bits/stdc++.h> #define RG register using namespace std; typedef long long ll; const int MAXN = 500005; struct segment_tree { ll lmax, rmax, ans, sum; } sgt[MAXN << 2]; int n, m; ll k, d; inline void pushup(int x) { sgt[x].sum = sgt[x << 1].sum + sgt[x << 1 | 1].sum; sgt[x].lmax = max(sgt[x << 1].lmax, sgt[x << 1].sum + sgt[x << 1 | 1].lmax); sgt[x].rmax = max(sgt[x << 1 | 1].rmax, sgt[x << 1].rmax + sgt[x << 1 | 1].sum); sgt[x].ans = max(sgt[x << 1].ans, max(sgt[x << 1 | 1].ans, sgt[x << 1].rmax + sgt[x << 1 | 1].lmax)); } void build(int x, int l, int r) { if (l == r) { sgt[x].lmax = sgt[x].rmax = 0; sgt[x].sum = sgt[x].ans = -k; return ; } int mid = (l + r) >> 1; build(x << 1, l, mid); build(x << 1 | 1, mid + 1, r); pushup(x); } void update(int x, int l, int r, int aim, ll add) { if (l == r) { sgt[x].sum += add, sgt[x].ans += add; sgt[x].lmax = sgt[x].rmax = max(sgt[x].sum, 0LL); return ; } int mid = (l + r) >> 1; if (aim <= mid) { update(x << 1, l, mid, aim, add); } else { update(x << 1 | 1, mid + 1, r, aim, add); } pushup(x); } int main() { ll x, y; scanf("%d %d %lld %lld", &n, &m, &k, &d); build(1, 1, n); for (int i = 1; i <= m; i++) { scanf("%lld %lld", &x, &y); update(1, 1, n, x, y); if (sgt[1].ans <= 1LL * k * d) { printf("TAK\n"); } else { printf("NIE\n"); } } return 0; }