BZOJ 1135:[POI2009]Lyz 线段树 + HALL定理

1135: [POI2009]Lyz

Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 448  Solved: 205 [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定理

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) 由此可知，对于任意的连续区间和都小于k*d 所以 ∑i=lra[i]<=(r−l+1+d)∗k   化简得 ∑i=lr(a[i]−k)<=d∗k   用线段树维护最大连续区间和，最后得解啦~~~

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<iomanip> using namespace std; #define ll long long const int N=1e6; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return f*x; } ll n,m,k,d; struct data{ll sum,ml,mr,w;}t[N]; void update(ll x) { t[x].sum=t[x<<1].sum+t[x<<1|1].sum; t[x].ml=max(t[x<<1].ml,t[x<<1].sum+t[x<<1|1].ml); t[x].mr=max(t[x<<1|1].mr,t[x<<1|1].sum+t[x<<1].mr); t[x].w=max(max(t[x<<1].w,t[x<<1|1].w),t[x<<1|1].ml+t[x<<1].mr); } void build(int p,int l,int r) { if(l==r) {t[p]=(data){-k,-k,-k,-k};return ;} int mid=r+l>>1; build(p<<1,l,mid);build(p<<1|1,mid+1,r); update(p); } inline void modify(int p,int l,int r,int v,ll val) { if(l==r) {t[p]=(data){t[p].sum+val,t[p].sum+val,t[p].sum+val,t[p].sum+val};return ;} int mid=r+l>>1; if(v<=mid) modify(p<<1,l,mid,v,val); else modify(p<<1|1,mid+1,r,v,val); update(p); } int main() { n=read();m=read();k=read();d=read(); build(1,1,n);ll x,y; for(int i=1;i<=m;i++) { x=read();y=read(); modify(1,1,n,x,y); puts(t[1].w<=(k*d)?"TAK":"NIE"); } }