BZOJ1135: [POI2009]Lyz

1135: [POI2009]Lyz

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 264  Solved: 106
[Submit][Status]

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

HINT

Source

题解：

暴力的话是每次构图跑个最大匹配，显然会T。

然后因为只需要判断能否把人全部匹配完了，所以我们有二分图匹配中的hall定理：

Hall定理：

此定理使用于组合问题中，二部图G中的两部分顶点组成的集合分别为X, Y, X={X1, X2, X3,X4,.........,Xm}, Y={y1, y2, y3, y4 ,.........,yn},G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：

X中的任意k个点至少与Y中的k个点相邻。（1≤k≤m)

那么有解的条件就是任意一个人的集合的人数<=所连接的鞋子数量

可以看出，当人是连续的时候鞋子所连接数量最少，所以我们只需要判断连续的子序列是否满足题意即可。否则既然连续的都满足题意，那么分开之后一定会有更多的鞋子被连进来。

用  表示鞋号为i的人的个数

那么

令

则

维护t'i的最长连续子序列  ---zky

代码：

 #include<cstdio>
 #include<cstdlib>
 #include<cmath>
 #include<cstring>
 #include<algorithm>
 #include<iostream>
 #include<vector>
 #include<map>
 #include<set>
 #include<queue>
 #include<string>
 #define inf 1000000000
 #define maxn 250000
 #define maxm 500+100
 #define eps 1e-10
 #define ll long long
 #define pa pair<int,int>
 #define for0(i,n) for(int i=0;i<=(n);i++)
 #define for1(i,n) for(int i=1;i<=(n);i++)
 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 #define mod 1000000007
 using namespace std;
 inline int read()
 {
     int x=,f=;char ch=getchar();
     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
     return x*f;
 }
 struct seg{ll l,r,lx,rx,mx,sum;}t[*maxn];
 ll n,m,kk,d;
 inline void build(int k,int l,int r)
 {
     t[k].l=l;t[k].r=r;int mid=(l+r)>>;
     t[k].lx=t[k].rx=t[k].mx=-kk;t[k].sum=-(r-l+)*kk;
     if(l==r)return;
     build(k<<,l,mid);build(k<<|,mid+,r);
 }
 inline void pushup(int k)
 {
     int l=k<<,r=k<<|;
     t[k].lx=max(t[l].lx,t[l].sum+t[r].lx);
     t[k].rx=max(t[r].rx,t[r].sum+t[l].rx);
     t[k].mx=max(t[l].rx+t[r].lx,max(t[l].mx,t[r].mx));
     t[k].sum=t[l].sum+t[r].sum;
 }
 inline void add(int k,int x,ll y)
 {
     int l=t[k].l,r=t[k].r,mid=(l+r)>>;
     if(l==r){t[k].sum+=y;t[k].mx=t[k].lx=t[k].rx=t[k].sum;return;}
     if(x<=mid)add(k<<,x,y);else add(k<<|,x,y);
     pushup(k);
 }
 int main()
 {
     freopen("input.txt","r",stdin);
     freopen("output.txt","w",stdout);
     n=read();m=read();kk=read();d=read();
     build(,,n);
     while(m--)
     {
         int x=read();ll y=read();
         add(,x,y);
         printf("%s\n",t[].mx<=d*kk?"TAK":"NIE");
     }
     return ;
 }