解题：POI 2009 Lyz

题面

板板讲的霍尔定理

霍尔定理：一张二分图有完全匹配的充要条件是对于任$i$个左部点都有至少$i$个右部点与它们相邻。放在这个题里就是说显然最容易使得鞋不够的情况是一段连续的人，那就维护一下最大子段和就好了=。=

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 long long ll[*N],rr[*N],len[*N],val[*N];

 long long n,m,k,d,t1,t2;

 void pushup(int nde)

 {

     int ls=*nde,rs=*nde+;

     ll[nde]=max(val[ls]+ll[rs],ll[ls]);

     rr[nde]=max(val[rs]+rr[ls],rr[rs]);

     len[nde]=max(max(len[ls],len[rs]),rr[ls]+ll[rs]);

     val[nde]=val[ls]+val[rs];

 }

 void create(int nde,int l,int r)

 {

     if(l==r)

         ll[nde]=rr[nde]=len[nde]=val[nde]=-k;

     else

     {

         int mid=(l+r)/,ls=*nde,rs=*nde+;

         create(ls,l,mid),create(rs,mid+,r);

         pushup(nde);

     }

 }

 void change(int nde,int l,int r,int pos,int task)

 {

     if(l==r)

     {

         ll[nde]+=task,rr[nde]+=task;

         len[nde]+=task,val[nde]+=task;

     }

     else

     {

         int mid=(l+r)/,ls=*nde,rs=*nde+;

         if(pos<=mid) change(ls,l,mid,pos,task);

         else change(rs,mid+,r,pos,task);

         pushup(nde);

     }

 }

 int main ()

 {

     scanf("%lld%lld%lld%lld",&n,&m,&k,&d),create(,,n);

     for(int i=;i<=m;i++)

     {

         scanf("%lld%lld",&t1,&t2),change(,,n,t1,t2);

         (len[]<=k*d)?printf("TAK\n"):printf("NIE\n");

     }

     return ;

 }