线段树动态维护最大子段和
观察分析题面发现，如果要使他匹配成功，则对于$1≤i≤n$左面任意$i$个点，至少右面也有$i$个点和他匹配
设$a[i]$为选择型号$i$的人数，$sum[i]$为前缀和
所以对于任意$sum[l,r]≤(r-l+1+d)*k$
设$s[l,r]$为$l≤i≤r,a[i]-k$的和
则对于任意的$l,r$总有$s[l,r]≤d*k$
就转化为维护最大子段和
code
1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define ll long long 5 #define int long long 6 const int inf=1e9+7; 7 const int maxn=2e5+10; 8 inline int read(){ 9 int x=0,f=1; 10 char c=getchar(); 11 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 12 while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();} 13 return x*f; 14 } 15 struct tree{ 16 int lmx,rmx,sum,ans; 17 #define lmx(x) t[x].lmx 18 #define rmx(x) t[x].rmx 19 #define sum(x) t[x].sum 20 #define ans(x) t[x].ans 21 }t[maxn*4]; 22 int n,m,k,d; 23 inline void pushup(int p){ 24 sum(p)=sum(p<<1)+sum(p<<1|1); 25 lmx(p)=max(lmx(p<<1),sum(p<<1)+lmx(p<<1|1)); 26 rmx(p)=max(rmx(p<<1|1),sum(p<<1|1)+rmx(p<<1)); 27 ans(p)=max(ans(p<<1),max(ans(p<<1|1),rmx(p<<1)+lmx(p<<1|1))); 28 } 29 void build(int p,int l,int r){ 30 if(l==r){ 31 sum(p)=ans(p)=-k;rmx(p)=lmx(p)=0; 32 return ; 33 } 34 int mid=(l+r)>>1; 35 build(p<<1,l,mid);build(p<<1|1,mid+1,r); 36 pushup(p); 37 } 38 void update(int p,int l,int r,int x,int y){ 39 if(l==r){ 40 ans(p)+=y;sum(p)+=y; 41 lmx(p)=rmx(p)=max(sum(p),0ll); 42 return ; 43 } 44 int mid=(l+r)>>1; 45 if(mid>=x)update(p<<1,l,mid,x,y); 46 else update(p<<1|1,mid+1,r,x,y); 47 pushup(p); 48 } 49 int main(){ 50 n=read();m=read();k=read();d=read(); 51 build(1,1,n); 52 for(int i=1;i<=m;i++){ 53 int x,y;x=read();y=read(); 54 update(1,1,n,x,y); 55 if(ans(1)<=k*d)puts("TAK"); 56 else puts("NIE"); 57 } 58 return 0; 59 } 60 } 61 signed main(){ 62 gengyf::main(); 63 return 0; 64 }