Description
初始時滑冰俱樂部有1到n号的溜冰鞋各k雙。已知x号腳的人可以穿x到x+d的溜冰鞋。 有m次操作,每次包含兩個數ri,xi代表來了xi個ri号腳的人。xi為負,則代表走了這麼多人。 對于每次操作,輸出溜冰鞋是否足夠。
Input
n m k d ( 1≤n≤200,000 , 1≤m≤500,000 , 1≤k≤10^9 , 0≤d≤n ) ri xi ( 1≤i≤m, 1≤ri≤n-d , |xi|≤10^9 )
Output
對于每個操作,輸出一行,TAK表示夠 NIE表示不夠。
Sample Input
4 4 2 1
1 3
2 3
3 3
2 -1
Sample Output
TAK
TAK
NIE
TAK
解題方法: 神題。 OTZ
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = e5+;
namespace segmenttree{
LL lmax[maxn<<], rmax[maxn<<], smax[maxn<<], sum[maxn<<];
void init(){
memset(lmax, , sizeof(lmax));
memset(rmax, , sizeof(rmax));
memset(smax, , sizeof(smax));
memset(sum, , sizeof(sum));
}
void pushup(int o){
lmax[o] = max(lmax[o*2], sum[o*2] + lmax[o*2+]);
rmax[o] = max(rmax[o*2+], sum[o*2+] + rmax[o*2]);
smax[o] = max(smax[o*2], smax[o*2+]);
smax[o] = max(smax[o], lmax[o*2+] + rmax[o*2]);
sum[o] = sum[o*2] + sum[o*2+];
}
void update(int pos, LL v, int l, int r, int o){
if(l == r){
lmax[o] += v;
rmax[o] += v;
smax[o] += v;
sum[o] += v;
return ;
}
int mid = (l + r) / ;
if(pos <= mid) update(pos, v, l, mid, o*2);
else update(pos, v, mid+, r, o*2+);
pushup(o);
}
}
int n, m, k, d;
int main(){
using namespace segmenttree;
init();
scanf("%d%d%d%d", &n, &m, &k, &d);
for(int i = ; i <= n; i++) update(i, -k, , n, );
while(m--){
int x, r;
scanf("%d%d", &r, &x);
update(r, x, , n, );
puts(smax[] <= (LL)d*k ? "TAK" : "NIE");
}
return ;
}