模拟赛 怨灵退治 题解（Hall定理+线段树）
题意：
有 n 群怨灵排成一排，燐每秒钟会选择一段区间，消灭至多 k 只怨灵。
如果怨灵数量不足 k，则会消灭尽量多的怨灵。
燐作为一只有特点的猫，它选择的区间是不会相互包含的。它想要知道它每秒最多能消灭多少怨灵。
要求：在之前每次都消灭尽量多的怨灵的情况下，求第 i 秒最多能消灭的怨灵的数量。
首先，这题可以用网络流做部分分。
考虑如何判断是否可行：
有一种显然的二分图匹配：把每个询问放在X部，怨灵放在Y部。
然后，把询问，怨灵分别拆点，进行区间连边，做匹配，如果有完美匹配，则可行。
但是，如果直接而匹配，会超时。我们考虑使用Hall定理进行判断。
Hall定理，就是说，在X部上取任意子集，与其相连的Y部结点都不小于集合大小。
如果我们要取子集，会变得更慢。
首先，把区间排序。
通过分析，我们知道：只要判断连续区间即可。
在X不连续时：
1、X部中一个点拆出来的点选子集，不如都选，因为都选不会使Y部大小增加。、
2、类似的，若X部中选的点在Y部中连续，那么X一定要连续，因为中间增加不会使Y部大小增加（区间是不会相互包含的）。
3、若X部中选的点在Y部中不连续，那可以拆成多个，拆的前后是等价的。
所以，我们只要快速判断连续区间就行。
记怨灵数量的前缀和为 sum[i]，区间消灭的怨灵数量的前缀和为 sumval[i]，区间左右端点为 l[i]，r[i]。
那么我们要求对于任意 \(1\leq L\leq R\leq m\),满足：
\(sumval[R]-sumval[L-1]\leq sum[r[R]]-sum[l[L]-1]\)
即\(sumval[R]-sum[r[R]]\leq sumval[L-1]-sum[l[L]-1]\)。
由于sum不变，只有sumval会边，所以当区间 i 被加入时：
若L-1>=i，R>=i，那么大小关系不变。
若L-1 只有对L-1 所以区间 i 被加入时设结果为val[i]，那么对于任意 \(1\leq L\leq i\leq R\leq m\)，要求 val[i]满足： \(sumval[R]+val[i]-sum[r[R]]\leq sumval[L-1]-sum[l[L]-1]\) 即\(val[i]\leq sumval[L-1]-sum[l[L]-1]]-(sumval[R]-sum[r[R]])\)。 那么，找到最小的 \(sumval[L-1]-sum[l[L]-1]\)，最大的 \(sumval[R]-sum[r[R]]\)，相减就是 val[i]的值。(当然,如果 k 小于这个值的话,val[i]就是 k) 使用线段树，支持区间加，区间最值，即可实现上述操作。 时间复杂度：\(O(mlog_2 m)\)。 感觉这个思路非常巧妙。 代码： #include #include #define inf 2000000000 int sz[100010],px[100010],wz[100010]; int xl[100010],xr[100010],xk[100010]; int cmp(const void*a,const void*b) { return xl[*(int*)a]-xl[*(int*)b]; } int z1[400010],z2[400010],su[100010]; int l1[400010],l2[400010]; void pushup(int i) { z1[i]=z1[(i<<1)|1]; z2[i]=z2[(i<<1)|1]; if(z1[i<<1] z1[i]=z1[i<<1]; if(z2[i<<1]>z2[i]) z2[i]=z2[i<<1]; } void pushdown(int i) { l1[i<<1]+=l1[i]; l1[(i<<1)|1]+=l1[i]; z1[i<<1]+=l1[i]; z1[(i<<1)|1]+=l1[i]; l1[i]=0; l2[i<<1]+=l2[i]; l2[(i<<1)|1]+=l2[i]; z2[i<<1]+=l2[i]; z2[(i<<1)|1]+=l2[i]; l2[i]=0; } void jianshu(int i,int l,int r) { if(l+1==r) { z1[i]=-su[xl[px[l]]-1]; z2[i]=-su[xr[px[l]]]; return; } int m=(l+r)>>1; jianshu(i<<1,l,m); jianshu((i<<1)|1,m,r); pushup(i); } void xiugai1(int i,int l,int r,int L,int R,int x) { if(R<=l||r<=L) return; if(L<=l&&r<=R) { z1[i]+=x; l1[i]+=x; return; } int m=(l+r)>>1; pushdown(i); xiugai1(i<<1,l,m,L,R,x); xiugai1((i<<1)|1,m,r,L,R,x); pushup(i); } void xiugai2(int i,int l,int r,int L,int R,int x) { if(R<=l||r<=L) return; if(L<=l&&r<=R) { z2[i]+=x; l2[i]+=x; return; } int m=(l+r)>>1; pushdown(i); xiugai2(i<<1,l,m,L,R,x); xiugai2((i<<1)|1,m,r,L,R,x); pushup(i); } void xiugai(int n,int j,int x) { xiugai1(1,1,n+1,j+1,n+1,x); xiugai2(1,1,n+1,j,n+1,x); } int getz1(int i,int l,int r,int L,int R) { if(R<=l||r<=L) return inf; if(L<=l&&r<=R) return z1[i]; int m=(l+r)>>1; pushdown(i); int rt1=getz1(i<<1,l,m,L,R),rt2=getz1((i<<1)|1,m,r,L,R); if(rt1 else return rt2; } int getz2(int i,int l,int r,int L,int R) { if(R<=l||r<=L) return -inf; if(L<=l&&r<=R) return z2[i]; int m=(l+r)>>1; pushdown(i); int rt1=getz2(i<<1,l,m,L,R),rt2=getz2((i<<1)|1,m,r,L,R); if(rt1>rt2)return rt1; else return rt2; } int getans(int n,int x) { int x1=getz1(1,1,n+1,1,x+1); int x2=getz2(1,1,n+1,x,n+1); return x1-x2; } int main() { freopen("rin.in","r",stdin); freopen("rin.out","w",stdout); int n,m; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&sz[i]); su[i]=su[i-1]+sz[i]; } scanf("%d",&m); if(m==0)return 0; for(int i=1;i<=m;i++) scanf("%d%d%d",&xl[i],&xr[i],&xk[i]); for(int i=1;i<=m;i++) px[i]=i; qsort(px+1,m,sizeof(int),cmp); for(int i=1;i<=m;i++) wz[px[i]]=i; jianshu(1,1,m+1); for(int i=1;i<=m;i++) { int jg=getans(m,wz[i]); if(xk[i] jg=xk[i]; xiugai(m,wz[i],jg); printf("%d\n",jg); } return 0; }