Luogu题面爆炸是什么鬼
只有当\(\sum_{i=l}^r a_i -k\times (r-l+1+d)>0\)才会无解
化简可得\(\sum_{i=l}^r (a_i -k)> k\times d\)时无解
所以此题转化为维护动态最大子段和，用线段树即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define ls p << 1
#define rs p << 1 | 1
#define mid ((l + r) >> 1)
using namespace std;
LL read() {
LL k = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
k = k * 10 + c - 48, c = getchar();
}
return k * f;
}
LL n, m, k, d;
struct zzz {
LL lm, rm, sum, ans;
}tree[500010 << 2];
void up(int p) {
tree[p].sum = tree[ls].sum + tree[rs].sum;
tree[p].lm = max(tree[ls].lm, tree[ls].sum + tree[rs].lm);
tree[p].rm = max(tree[rs].rm, tree[rs].sum + tree[ls].rm);
tree[p].ans = max(tree[ls].ans, max(tree[rs].ans, tree[ls].rm + tree[rs].lm));
}
void build(int l, int r, int p) {
if(l == r) {
tree[p] = (zzz){0, 0, -k, -k};
return ;
}
build(l, mid, ls); build(mid+1, r, rs);
up(p);
}
void update(int l, int r, int p, int pos, int val) {
if(l == r) {
tree[p].ans += val, tree[p].sum += val;
tree[p].lm = tree[p].rm = max(tree[p].sum, (LL)0);
return ;
}
if(mid >= pos) update(l, mid, ls, pos, val);
else update(mid+1, r, rs, pos, val);
up(p);
}
int main() {
n = read(), m = read(), k = read(), d = read();
build(1, n, 1);
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
update(1, n, 1, x, y);
if(tree[1].ans > k * d) printf("NIE\n");
else printf("TAK\n");
}
return 0;
}