bzoj 1135 [POI2009]Lyz 线段树+hall定理

1135: [POI2009]Lyz

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 573 Solved: 280
[Submit][Status][Discuss]

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

题解：

　　　可以转换一下模型，每个人都有鞋穿不就等价于二分图存在完美匹配。

　　　根据hall定理，对于一个二分图，设左边有n个点，右边有m个点，则左边n个点

　　　能完全匹配的充要条件是：对于1<=i<=n,左面任意i个点，都至少有i个右面的点与它相连

　　　hall定理很容易理解，然后后面我就直接贴别人的了。

 #include<cstring>

 #include<cmath>

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #define ll long long

 #define N 200007

 #define Wb putchar(' ')

 #define We putchar('\n')

 #define rg register int

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 inline void write(int x)

 {

     if(x<) putchar('-'),x=-x;

     if (x==) putchar();

     int num=;char c[];

     while(x) c[++num]=(x%)+,x/=;

     while(num) putchar(c[num--]);

 }

 int n,m,k,d;

 struct seg

 {

     struct node

     {

         ll ls,rs,ss,sum;

         node(){ls=rs=ss=sum=;}

     }t[N<<];

     #define lson i<<1,l,mid

     #define rson i<<1|1,mid+1,r

     #define L i<<1

     #define R i<<1|1

     void update(int i)

     {

         t[i].ls=max(t[L].ls,t[L].sum+t[R].ls);

         t[i].rs=max(t[R].rs,t[R].sum+t[L].rs);

         t[i].ss=max(t[L].ss,t[R].ss);

         t[i].ss=max(t[i].ss,t[L].rs+t[R].ls);

         t[i].sum=t[L].sum+t[R].sum;

     }

     void Add(int i,int l,int r,int ps,ll d)

     {

         if(l==r){t[i].ls+=d;t[i].rs+=d;t[i].ss+=d;t[i].sum+=d;return;}

         int mid=(l+r)>>;

         if(ps<=mid)Add(lson,ps,d);

         else Add(rson,ps,d);

         update(i);

     }

     #undef lson

     #undef rson

     #undef L

     #undef R

 }T;  

 int main()

 {

       n=read(),m=read(),k=read(),d=read();

     for(int i=;i<=n;i++)T.Add(,,n,i,-k);

     while(m--)

     {

         int r=read(),x=read();

         T.Add(,,n,r,x);

         puts(T.t[].ss<=(ll)d*k?"TAK":"NIE");

     }

 }

巴特西