bzoj2138 stone线段树+ hall定理

bzoj2138 stone线段树+ hall定理

​​ Description

话说Nan在海边等人，预计还要等上M分钟。为了打发时间，他玩起了石子。Nan搬来了N堆石子，编号为1到N，每堆 包含Ai颗石子。每1分钟，Nan会在编号在[Li,Ri]之间的石堆中挑出任意Ki颗扔向大海（好疼的玩法），如果[Li,R i]剩下石子不够Ki颗，则取尽量地多。为了保留扔石子的新鲜感，Nan保证任意两个区间[Li,Ri]和[Lj,Rj]，不会 存在Li<=Lj&Rj<=Ri的情况，即任意两段区间不存在包含关系。可是，如果选择不当，可能无法扔出最多的石子， 这时NN就会不高兴了。所以他希望制定一个计划，他告诉你他m分钟打算扔的区间[Li,Ri]以及Ki。现在他想你告诉 他，在满足前i-1分钟都取到你回答的颗数的情况下，第i分钟最多能取多少个石子。 Input

第一行正整数N，表示石子的堆数； 第二行正整数x,y,z,P，(1<=x,y,z<=N;P<=500) 有等式A[i]=[(i-x)^2+(i-y)^2+(i-z)^2] mod P； 第三行正整数M，表示有M分钟； 第四行正整数K[1],K[2],x,y,z,P，(x,y,z<=1000;P<=10000) 有等式K[i]=(x*K[i-1]+y*K[i-2]+z)mod P。 接下来M行，每行两个正整数L[i],R[i]。 N<=40000 M<=N 1<=L[i]<=R[i]<=N A[i]<=500 Output

有M行，第i行表示第i分钟最多能取多少石子。

Sample Input

5 3 2 4 7 3 2 5 2 6 4 9 2 4 1 2 3 5 Sample Output

2 5 5 【样例说明】 石子每堆个数分别为0,5,2,5,0。 第1分钟，从第2到第4堆中选2个； 第2分钟，从第1到第2堆中选5个； 第3分钟，从第3到第5堆中选8个，但最多只能选5个。 线段树+ hall定理 思考了很久也不太会做的题..很菜qwq ​​ 考虑定理的内容是： 我们来假设X集合点少一点好了。X集合就当做有n个点。 那么二分图G存在完美匹配，则取任意正整数1<=k<=n，均满足我从X集合选出k个不同的点，那么它们连向的y集合的点个数不小于k。 那么本来这题一个简单点的想法是把每堆石子和每个询问全部都拆开来看 每次最大流即可 注意到这题有个性质 那就是一个区间不会包含另一个区间 这样的话就有些性质 具体可以参考原blog的题解 然后开始推导公式 设bi按照右端点排序之后第i次扔掉的石子ai即题目中的定义 设s表示b的前缀和，ss表示a前缀和。 同时为了方便，令v[i]=ss[R[i]],vv[i]=ss[L[i+1]-1] 那么上面式子可写为 Sr−Sl−1<=Vr−VVl−1 Sr−Vr<=Sl−1−VVl−1 继续为了方便，令c[i]=s[i]-v[i],cc[i]=s[i-1]-vv[i-1] 那么上面式子可写为 Cr<=CCl 那么观察到 只需要在当前询问的时候在1~j中找一下cc的最小值 在j~m中找一下c的最大值 只要这个满足 那么上界也就确定了 tgotp昨天和我说要同时和当前询问的这个k取下min才可以 注意细节：存在m=0 ，存在线段树询问时 l>r的情况

#include#include#define N 44000#define inf 0x3f3f3f3fusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x*f;}inline int sq(int x){return x*x;}struct node{ int min,max,left,right,lazyc,lazycc;}tree[N<<1];struct node1{ int l,r,id,k;}qr[N];int cov[N],num,s[N],c[N],cc[N],n,m,pos[N],bl[N],root,tot,a[N];inline void update(int x){ int l=tree[x].left,r=tree[x].right; tree[x].max=max(tree[l].max,tree[r].max); tree[x].min=min(tree[l].min,tree[r].min);}inline void pushdown(int x){ int l=tree[x].left,r=tree[x].right; if (tree[x].lazyc){ if (l)tree[l].lazyc+=tree[x].lazyc,tree[l].max+=tree[x].lazyc; if (r)tree[r].lazyc+=tree[x].lazyc,tree[r].max+=tree[x].lazyc;tree[x].lazyc=0; } if (tree[x].lazycc){ if (l)tree[l].lazycc+=tree[x].lazycc,tree[l].min+=tree[x].lazycc; if (r)tree[r].lazycc+=tree[x].lazycc,tree[r].min+=tree[x].lazycc;tree[x].lazycc=0; }}inline int qx(int x,int l,int r,int l1,int r1){ if (l1<=l&&r1>=r) return tree[x].max; int mid=l+r>>1,tmp=-inf;pushdown(x); if (l1<=mid) tmp=max(tmp,qx(tree[x].left,l,mid,l1,r1)); if (r1>mid) tmp=max(tmp,qx(tree[x].right,mid+1,r,l1,r1));return tmp;} inline int qn(int x,int l,int r,int l1,int r1){ if (l1<=l&&r1>=r) return tree[x].min; int mid=l+r>>1,tmp=inf;pushdown(x); if(l1<=mid) tmp=min(tmp,qn(tree[x].left,l,mid,l1,r1)); if (r1>mid) tmp=min(tmp,qn(tree[x].right,mid+1,r,l1,r1));return tmp;}inline void insertc(int x,int l,int r,int l1,int r1,int v){ if (l1<=l&&r1>=r){tree[x].max+=v;tree[x].lazyc+=v;return;} int mid=l+r>>1;pushdown(x); if (l1<=mid) insertc(tree[x].left,l,mid,l1,r1,v); if (r1>mid) insertc(tree[x].right,mid+1,r,l1,r1,v);update(x);}inline void insertcc(int x,int l,int r,int l1,int r1,int v){ if (l1>r1) return; if (l1<=l&&r1>=r){tree[x].min+=v;tree[x].lazycc+=v;return;} int mid=l+r>>1;pushdown(x); if (l1<=mid) insertcc(tree[x].left,l,mid,l1,r1,v); if (r1>mid) insertcc(tree[x].right,mid+1,r,l1,r1,v);update(x);}inline bool cmp(const node1 &a,const node1 &b){return a.r>1; if (l==r){tree[x].min=cc[l],tree[x].max=c[l];return;} build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);update(x);}int main(){ freopen("bzoj2138.in","r",stdin); n=read();tree[0].min=inf;tree[0].max=-inf; int x=read(),y=read(),z=read(),mod=read(); for (int i=1;i<=n;++i) a[i]=(sq(i-x)+sq(i-y)+sq(i-z))%mod;m=read(); qr[1].k=read();qr[2].k=read();x=read();y=read();z=read();mod=read();if (!m) return 0; for (int i=3;i<=m;++i) qr[i].k=(qr[i-1].k*x+qr[i-2].k*y+z)%mod; for (int i=1;i<=m;++i) qr[i].l=read(),qr[i].r=read(),qr[i].id=i,++cov[qr[i].l],--cov[qr[i].r+1]; for (int i=1;i<=n;++i){ cov[i]+=cov[i-1];if (cov[i]) a[++tot]=a[i],bl[i]=tot; }n=tot;for (int i=1;i<=n;++i) s[i]=s[i-1]+a[i]; for (int i=1;i<=m;++i) qr[i].l=bl[qr[i].l],qr[i].r=bl[qr[i].r];sort(qr+1,qr+m+1,cmp); //for (int i=1;i<=m;++i) printf("%d %d\n",qr[i].l,qr[i].r); for (int i=1;i<=m;++i) c[i]-=s[qr[i].r],cc[i]-=s[qr[i].l-1],pos[qr[i].id]=i;build(root,1,m); //for (int i=1;i<=m;++i) printf("%d %d\n",qr[i].l,qr[i].r); //for (int i=1;i<=m;++i) printf("%d %d\n",c[i],cc[i]); for (int i=1;i<=m;++i){ int j=pos[i],cc=qn(root,1,m,1,j),c=qx(root,1,m,j,m),ans=min(qr[j].k,cc-c); //printf("%d %d\n",cc,c); printf("%d\n",ans);insertc(root,1,m,j,m,ans);insertcc(root,1,m,j+1,m,ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。