题目概述

有 $n$ 堆石子，每堆 $a_i$ 个，现在要取 $m$ 次，第 $i$ 次在 $[L_i,R_i]$ 中取 $K_i$ 个（不够 $K_i$ 就取完）。问在前 $i-1$ 次取到的最多的前提下，第 $i$ 次最多能取多少。

解题报告

我太菜了，把每堆石子看做 $a_i$ 个点，取 $K_i$ 个看做 $K_i$ 个点向 $[L_i,R_i]$ 连边，那么就是二分图最大匹配。

最多取的数量就是最大的 $x$ 使得 $x$ 个点向 $[L_i,R_i]$ 连边之后能够有完美匹配，考虑霍尔定理。

先离线得到所有线段的位置关系，那么由于不包含所以线段就分成了一块块的，只需要考虑所有块里的情况就好了，也就是说对于所有 $i\le j$ ，都满足：

$$ Sum_a(R_j)-Sum_a(L_i-1)\ge Sum_K(j)-Sum_K(i-1)\\ \Rightarrow Sum_a(R_j)-Sum_K(j)\ge Sum_a(L_i-1)-Sum_K(i-1) $$

当新加入一个线段 $pos$ 的时候，假设取了 $k$ 个，那么：

$$ k\le K_{pos}\land \forall i\le pos\le j,k\le(Sum_a(R_j)-Sum_K(j))-(Sum_a(L_i-1)-Sum_K(i-1)) $$

因为加入 $k$ 后从 $pos$ 开始 $Sum_K(i)$ 都增加了 $k$ ，由于还要满足霍尔定理所以 $k$ 需要满足上面的式子。

所以每次用线段树求出 $min\{Sum_a(R_j)-Sum_K(j)\}-max\{Sum_a(L_i-1)-Sum_K(i-1)\}$ 就好了。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=40000;

int n,m,a[maxn+5],K[maxn+5],SA[maxn+5],L[maxn+5],R[maxn+5],ID[maxn+5],who[maxn+5];
int A[(maxn<<2)+5],B[(maxn<<2)+5],TA[(maxn<<2)+5],TB[(maxn<<2)+5];

#define sqr(x) ((x)*(x))
#define Pushup(p) (A[p]=max(A[(p)<<1],A[(p)<<1|1]),B[p]=min(B[(p)<<1],B[(p)<<1|1]))
void Build(int l,int r,int p=1){
    if (l==r) {A[p]=SA[L[ID[l]]-1];B[p]=SA[R[ID[l]]];return;}
    int mid=l+(r-l>>1);Build(l,mid,p<<1);Build(mid+1,r,p<<1|1);Pushup(p);
}
inline void Pushdown(int p){int tag;
    tag=TA[p];TA[p]=0;A[p<<1]+=tag;TA[p<<1]+=tag;A[p<<1|1]+=tag;TA[p<<1|1]+=tag;
    tag=TB[p];TB[p]=0;B[p<<1]+=tag;TB[p<<1]+=tag;B[p<<1|1]+=tag;TB[p<<1|1]+=tag;
}
void UpdateA(int L,int R,int k,int l=1,int r=m,int p=1){
    if (L==l&&r==R) {A[p]+=k;TA[p]+=k;return;}int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) UpdateA(L,R,k,l,mid,p<<1); else if (L>mid) UpdateA(L,R,k,mid+1,r,p<<1|1);
    else UpdateA(L,mid,k,l,mid,p<<1),UpdateA(mid+1,R,k,mid+1,r,p<<1|1);Pushup(p);
}
void UpdateB(int L,int R,int k,int l=1,int r=m,int p=1){
    if (L==l&&r==R) {B[p]+=k;TB[p]+=k;return;}int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) UpdateB(L,R,k,l,mid,p<<1); else if (L>mid) UpdateB(L,R,k,mid+1,r,p<<1|1);
    else UpdateB(L,mid,k,l,mid,p<<1),UpdateB(mid+1,R,k,mid+1,r,p<<1|1);Pushup(p);
}
int Min(int L,int R,int l=1,int r=m,int p=1){
    if (L==l&&r==R) return B[p];int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) return Min(L,R,l,mid,p<<1); else if (L>mid) return Min(L,R,mid+1,r,p<<1|1);
    else return min(Min(L,mid,l,mid,p<<1),Min(mid+1,R,mid+1,r,p<<1|1));
}
int Max(int L,int R,int l=1,int r=m,int p=1){
    if (L==l&&r==R) return A[p];int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) return Max(L,R,l,mid,p<<1); else if (L>mid) return Max(L,R,mid+1,r,p<<1|1);
    else return max(Max(L,mid,l,mid,p<<1),Max(mid+1,R,mid+1,r,p<<1|1));
}
inline bool cmp(const int &a,const int &b) {return L[a]<L[b];}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    int X,Y,Z,P;scanf("%d%d%d%d%d",&n,&X,&Y,&Z,&P);
    for (int i=1;i<=n;i++) SA[i]=SA[i-1]+(a[i]=(sqr(i-X)%P+sqr(i-Y)%P+sqr(i-Z)%P)%P);
    scanf("%d%d%d%d%d%d%d",&m,&K[1],&K[2],&X,&Y,&Z,&P);if (!m) return 0;
    for (int i=3;i<=m;i++) K[i]=(X*K[i-1]%P+Y*K[i-2]%P+Z)%P;
    for (int i=1;i<=m;i++) scanf("%d%d",&L[i],&R[i]),ID[i]=i;sort(ID+1,ID+1+m,cmp);
    for (int i=1;i<=m;i++) who[ID[i]]=i;Build(1,m);
    for (int i=1;i<=m;i++){
        int x=Min(who[i],m)-Max(1,who[i]);x=min(x,K[i]);UpdateB(who[i],m,-x);
        if (who[i]<m) UpdateA(who[i]+1,m,-x);printf("%d\n",x);
    }return 0;
}