哟 HallHall 定理

· · 算法·理论

看得我头大，写点东西记录一下。

Hall 定理及其相关推论

我们有一个二分图 G=(V_1 \cup V_2,E)，其中 V_1,V_2 分别是 G 的左部点集和右部点集。

记 N(x) 为与点 x 直接相连的点集，N(S) 为点集 S 在 G 上的邻域，即 \bigcup\limits _{x \in S}N(x)。

  • Hall 定理：二分图 G 存在大小为 |V_1| 的匹配的充要条件是 \forall S \subseteq V_1 有 |S|\le |N(S)|。其中我们称这个条件为 Hall 条件。

证明：

  1. 假如存在一个点集 S \subsetneq V_1 使得 |S|=|N(S)|，那么归纳假设中 S \cup N(S) 的导出子图存在完备匹配。对 S 与 N(S) 匹配后，视为将它们删去，图变为 G'=(V_1'\cup V_2',E')。在 G' 中的邻域记为 N'（注意区分）。

    此时对于所有左部点集 T 都满足 |T|\le|N'(T)|。因为 |S \cup T|\le |N(S \cup T)|，而 |S \cup T|=|S|+|T|,|N(S \cup T)|=|N(S)|+|N'(T)|，重新带入 |S|=|N(S)| 即可得到 |T|\le|N'(T)|。此时的图 G' 依然满足 Hall 定理。

  2. 假如对于任意左部点集 S \subseteq V_1 使得 |S|<|N(S)|，随便将一条边作为匹配，依然视为这对应的两个点删去成为图 G''，显然对于 G'' 中的左部点集都有 |S|\le |N''(S)|，那么此时的图 G'' 依然满足 Hall 定理。

  • 推论 1：正则（即每个点度数相同）二分图 G 满足 |V_1|=|V_2|，那么 G 存在完美匹配。

证明：

记每个点度数为 k \ge 1，对于任意 S \subseteq V_1，考虑其及其邻域 N(S) 度数和分别为 k|S|,k|N(S)|，N(S) 的邻边包含了 S 的邻边，所以 k|S|\le k|N(S)|，即 |S|\le |N(S)|。故 G 满足 Hall 条件，此时大小为 |V_1| 的匹配就是完美匹配。

如此，命题得证。

若我们将匹配的边删去，这个图依然是一个正则二分图，每个点度数为 k-1。那么我们可以一直找到完美匹配直到 k=0。故每个点度数为 k 的正则二分图可以拆分为 k 组完美匹配。

  • 推论 2：二分图 G 的最大匹配大小为 |V_1|-\max\limits_{S\subseteq V_1 }\{0,|S|-|N(S)|\}。

证明：

待补。

  • 广义 Hall 定理：形如下图的网络最大流中，源部可以流满当且仅当对于任意 S 均有 \sum\limits_{i\in S}a_i \le \sum \limits _{i \in N(S)}b_i。

这图是贺的。

证明：

构造一个二分图，对于每个 i 我们在左部拆 a_i 个点，对于每个 j 我们在右部拆 b_j 个点。原先 i,j 间的连边改为他们所拆的点间的两两连边。显然这个二分图的最大匹配与原图的最大流等价。而这个条件不弱于 Hall 条件，所以该命题成立。

相关题目

题 1

网络流模型：对 x 号脚的人建源部点，从源点连容量为人数 a_x 的边。对 y 号的鞋建立汇部点，与汇点连容量为 k 的边。对于源部点 x，朝 x \le y \le x+d 的汇部点 y 连容量为 +\infty 的边。

合法即源部满流，由广义 Hall 定理，对于任意一个源部点集 S，都要有 \sum _{i \in S}a_i\le k|N(S)|。

显然只有 S 在其中元素相邻时，限制才是紧的，那么我们只考虑选区间，即对于任意区间 [l,r] 要有 \sum _{i =l}^{r}a_i\le (r-l+1+d)k。

令 a_i \gets a_i-k，则条件变为 \sum _{i =l}^{r}a_i\le dk。直接找 a 的最大子段和判断即可。每次加人删人都是 a 上单点修。

线段树大家都会，时间复杂度 \mathcal{O}\big(m \log n\big)。

::::info[代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=800005;
int n,m,k,d,S[N],L[N],R[N],res[N];
inline void U(int id,int l,int r,int x,int v){
    if(l==r)return L[id]=R[id]=res[id]=(S[id]+=v),void();int mid=l+r>>1;
    x<=mid?U(id<<1,l,mid,x,v):U(id<<1|1,mid+1,r,x,v);
    S[id]=S[id<<1]+S[id<<1|1],
    L[id]=max(L[id<<1],S[id<<1]+L[id<<1|1]),
    R[id]=max(R[id<<1|1],S[id<<1|1]+R[id<<1]),
    res[id]=max({res[id<<1],res[id<<1|1],R[id<<1]+L[id<<1|1]});
}
signed main(){
    cin>>n>>m>>k>>d;
    for(int i=1;i<=n;++i)U(1,1,n,i,-k);
    for(int i=1,r,x;i<=m;++i)
        cin>>r>>x,U(1,1,n,r,x),
        cout<<(res[1]<=d*k?"TAK\n":"NIE\n");
    return 0;
}

::::

题 2

考虑记某个配锁的局面下钥匙 x 可以打开的锁为集合 N(x)，那么对于合法情况的判定是：

\max\limits_{S\subseteq [m]}\left\{\sum_{i \in S}a_i-\sum _{i \in N(S)}b_i\right\}\le 0

长得好像 Hall 定理！

这个条件等价于建立一个二分图，对于所有 i 拆 a_i 个左部点，对于所有的 j 拆 b_j 个右部点。一个箱子 i 上有锁 j 就将所有 i 拆的点与 j 拆的点相连（可能有多出的点空着）。合法条件就是存在大小为 \sum_{i=1}^{n} a_i 的匹配。

可以发现这个建图的方式和广义 Hall 定理中证明很像，所以这个题可以对其考虑网络流建模来做。无形之中还验证了最大流最小割定理（直接考虑网络流是最小割，而最大匹配等价于最大流）。

发现数据范围很小，思考状压 DP。先枚举左部点及其和谁匹配，直接对右部中每个点是否匹配状压，但这样不是太好写，拿每种右部点还剩下几个做 V 进制状压是好的。

时间复杂度 \mathcal{O}\big(nV^{2m}\big)。实现似乎不管精细程度如何都可以快速通过。

::::info[代码]

#include<bits/stdc++.h>
#define vc basic_string<int>
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read(){
    register int x=0,s=gc;while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=7,M=50000,inf=1e9;
int n,m,V,nw,ans=inf,a[N],b[N],c[N][N],dp[M],tmp[M];vc t;
inline void chkmin(int &x,int y){
    x=x<y?x:y;
}
inline vc gt(int x){
    vc r;
    for(int i=0;i<m;++i)r+=x%5,x/=5;
    return r;
}
inline int GT(vc x){
    int r=0;
    for(int i=m-1;~i;--i)r=r*5+x[i];
    return r;
}
inline void dfs(int x,int cs,int s){
    if(x==m){
        if(s)return;
        return chkmin(tmp[GT(t)],cs);
    }
    for(int i=1;i<=min(s,t[x]);++i)
        t[x]-=i,dfs(x+1,cs+c[nw][x],s-i),t[x]+=i;
    dfs(x+1,cs,s);
}
signed main(){
    n=rd,m=rd,V=pow(5,m);
    for(int i=0;i<n;++i)a[i]=rd;for(int i=0;i<m;++i)t+=b[i]=rd;
    for(int i=0;i<n;++i)for(int j=0;j<m;++j)c[i][j]=rd;
    memset(dp,0x3f,sizeof(dp)),memset(tmp,0x3f,sizeof(tmp)),dp[GT(t)]=0;
    for(int i=0;i<n;++i){
        for(int j=0;j<V;++j)if(dp[j]<inf)nw=i,t=gt(j),dfs(0,dp[j],a[i]);
        for(int j=0;j<V;++j)dp[j]=tmp[j],tmp[j]=inf;
    }
    for(int i=0;i<V;++i)chkmin(ans,dp[i]);
    cout<<(ans>=inf?-1:ans)<<'\n';return 0;
}

::::

题 3

考虑构造一个二分图：左部点是每个集合，右部点是每个节点，若点 i 在集合 j 中，则连一条点 i 和集合 j 之间的边。

对于一个左部点集 S，一定要有 |N(S)|\ge |S|+1，否则无论我们怎样选择这 |S| 条边，它都不会是个树。

这和 Hall 定理很像。对这个图求最大匹配，若最大匹配大小小于 n-1，此时显然是无解的。对于其余大小等于 n-1 的情况继续考虑构造。

考虑对这种情况的构造：右部中有且仅有一个点 x 未被匹配，在左侧选择位于 N(x) 且未被选择过的集合 p，递归进入 p 的匹配点 x'，此时集合 p 选择的边是 (x,x')。

如果最后经过了所有点，那么我们构造出了一棵树，否则无解。那么就出现一个问题：会不会有解而我们没有找到？

考虑构造没有经过所有点的情况，此时经过右部点的次数是经过左部点的次数加一，那么显然剩余的点中左部点和右部点的个数相同，对于此时的图有 |V_1|\ge |N(V_1)|，其中 V_1 是左部点集。这种情况我们在上面已经说明其无解。

那么用 Dinic 跑二分图匹配，时间复杂度 \mathcal{O}\big(n+m\sqrt{n}\big)。

::::info[代码]

#include<bits/stdc++.h>
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read(){
    register int x=0,s=gc;while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=800005,inf=1e9;
struct edge{
    int to,nx,w;
}e[N];int n,m=1,L,s,t,rt,cur[N],hd[N],a[N],b[N],dep[N];bool vis[N];
inline void up(int x,int y,int w){
    e[++m]={y,hd[x],w},hd[x]=m;
}
inline void U(int x,int y,int w){
    up(x,y,w),up(y,x,0);
}
inline bool bfs(){
    for(int i=1;i<=t;++i)dep[i]=inf,cur[i]=hd[i];
    queue<int> q;q.push(s),dep[s]=0;
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=hd[u],to;i;i=e[i].nx){
            to=e[i].to;
            if(e[i].w&&dep[to]>dep[u]+1)
                dep[to]=dep[u]+1,q.push(to);
        }
    }
    return dep[t]<inf;
}
inline int dfs(int x,int mn){
    if(x==t||!mn)return mn;
    int FL=0;
    for(int i=cur[x],to,fl;i;i=e[i].nx){
        cur[x]=i,to=e[i].to;
        if(dep[to]==dep[x]+1&&
            (fl=dfs(to,min(mn,e[i].w)))){
            e[i].w-=fl,e[i^1].w+=fl,mn-=fl,FL+=fl;
            if(!mn)break;   
        }
    }
    return FL;
}
inline int Dinic(){
    int res=0;
    while(bfs())res+=dfs(s,inf);
    return res;
}
inline void dfs(int x){
    for(int i=hd[x],to;i;i=e[i].nx){
        to=e[i].to;if(vis[to])continue;vis[to]=1;
        for(int j=hd[to];j;j=e[j].nx)if(!e[j].w)
            dfs(e[j].to),++m,a[to]=x-L,b[to]=e[j].to-L;
    }
}
signed main(){
    n=rd,L=n-1;
    for(int i=1,sz;i<n;++i){
        sz=rd;
        for(int j=1,x;j<=sz;++j)x=rd,U(i,L+x,1);
    }
    s=n+L+1,t=s+1;
    for(int i=1;i<=L;++i)U(s,i,1);
    for(int i=L+1;i<=L+n;++i)U(i,t,1);
    if(Dinic()<n-1)return cout<<-1<<'\n',0;
    for(int i=hd[t];i;i=e[i].nx)if(!e[i].w){rt=e[i].to;break;}
    m=0,vis[s]=vis[t]=1,dfs(rt);
    if(m<n-1)return cout<<-1<<'\n',0;
    for(int i=1;i<n;++i)cout<<a[i]<<' '<<b[i]<<'\n';return 0;
}

::::

题 4

将每个人 i 有的卡片 a_{i,1},a_{i,2},\cdots ,a_{i,m} 看作一个矩阵。那么我们可以随意重排行内。

考虑将矩阵构造为每列上是一个 1 \sim n 的排列的形式，那么最后交换 a_{i,j},a_{j,i} 即可。

建立一个二分图：左部点为每一行，右部点为每种数，某一行 i 对 a_{i,1},a_{i,2},\cdots,a_{i,m} 连边。

那么在某一列排出一个排列相当于在图上找一个完美匹配。我们需要对每一列都这么干，所以就是要将图拆成 n 组完美匹配，由于这是一个 n-正则二分图，由推论 1 这一定有解。

用 Dinic 跑二分图匹配，时间复杂度 \mathcal{O}\big(n^{3.5}\big)。

::::info[代码]

#include<bits/stdc++.h>
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read(){
    register int x=0,s=gc;while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=500005,M=405,inf=1e9;
struct edge{
    int to,nx,w;
}e[N];int n,m,s,t,a[M][M],c[M][M],cur[N],hd[N],ht[N],dep[N];
inline void up(int x,int y,int w){
    e[++m]={y,hd[x],w},hd[x]=m;
}
inline void U(int x,int y,int w){
    up(x,y,w),up(y,x,0);
}
inline bool bfs(){
    for(int i=1;i<=t;++i)dep[i]=inf,cur[i]=hd[i];
    queue<int> q;q.push(s),dep[s]=0;
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=hd[u],to;i;i=e[i].nx){
            to=e[i].to;
            if(e[i].w&&dep[to]>dep[u]+1)
                dep[to]=dep[u]+1,q.push(to);
        }
    }
    return dep[t]<inf;
}
inline int dfs(int x,int mn){
    if(x==t||!mn)return mn;
    int FL=0;
    for(int i=cur[x],to,fl;i;i=e[i].nx){
        cur[x]=i,to=e[i].to;
        if(dep[to]==dep[x]+1&&
            (fl=dfs(to,min(mn,e[i].w)))){
            e[i].w-=fl,e[i^1].w+=fl,mn-=fl,FL+=fl;
            if(!mn)break;   
        }
    }
    return FL;
}
inline int Dinic(){
    int res=0;
    while(bfs())res+=dfs(s,inf);
    return res;
}
inline void clr(){
    memset(hd,0,sizeof(hd)),m=1;
}
inline void sol(){
    n=rd;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)a[i][j]=rd;
    s=n+n+1,t=s+1;
    for(int i=1;i<=n;++i)ht[i]=hd[i];
    for(int k=1;k<=n;++k){
        clr();
        for(int i=1;i<=n;++i)U(s,i,1);
        for(int i=1;i<=n;++i)U(i+n,t,1);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)if(a[i][j])U(i,a[i][j]+n,1);
        Dinic();
        for(int i=1;i<=n;++i){
            for(int j=hd[i];j;j=e[j].nx){
                if(!e[j].w){
                    for(int o=1;o<=n;++o)if(a[i][o]==e[j].to-n){
                        c[i][k]=o,a[i][o]=0;break;}
                }
            }
        }
    }
    cout<<n*(n-1)/2<<'\n';
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            cout<<i<<' '<<c[i][j]<<' '<<j<<' '<<c[j][i]<<'\n';
}
signed main(){
    int T=rd;
    while(T--)sol();
    return 0;
}

::::

题 5

我们认为 \mathcal{O}(n)=\mathcal{O}(\sum a)。

建立流模型，每种饼干为源部，从源点连容量 a_i 的边，每个盒子为汇部，向汇点连容量 v_i 的边，每种饼干和每个盒子有一条容量 1 的边。其中 v_i 是在 b 中选的一个盒子大小。设我们选了 m 个盒子。

那么一种局面的合法判定为：

  2. 网络的两侧均满流，不妨将源汇互换，套用广义 Hall 定理得到 v_i 的限制，即对于任意一个盒子集合 S，有 \sum _{i \in S}v_i \le \sum_{i=1}^{n}\min\{|S|,a_i\}。假如不互换两边，式子会和 m 相关，这是我们不好处理的。

发现一个事情，条件 2. 右式的变量是 |S| 而与 S 内部无关，那么条件在左式为 v 的前 |S| 大值时最紧。

考虑从大到小选择盒子，设 f_{i,j,k} 表示在前 i 个考虑的盒子中，是否右选 j 个盒子，和为 k 的方案。因为 j \le \dfrac{\sum a}{b_i}，而 b_i 互不相同，所以只有 \mathcal{O}(n^2 \log n) 个有用状态。

用 bitset 优化，时间复杂度为 \mathcal{O}\left(\dfrac{n^2 \log n}{w}\right)。构造方案在 f 上贪心即可。

::::info[代码]

#include<bits/stdc++.h>
#define pr pair<int,int>
#define rd read()
#define gc getchar()
using namespace std;
inline int read(){
    register int x=0,ss=1,s=gc;
    while(!isdigit(s)&&s!='-')s=gc;
    if(s=='-')ss=-1,s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return ss*x;
}
const int N=15005;
int n,m,sum,ans=-1,a[N],b[N],s[N],c[N];vector<bitset<N>> f[N];bitset<N> pre[N];
priority_queue<pair<int,int> > q;vector<pr> rv;
signed main(){
    n=rd;for(int i=1;i<=n;++i)a[i]=rd,sum+=a[i],--s[a[i]+1];
    m=rd;for(int i=1;i<=m;++i)b[i]=rd;s[1]+=n;
    for(int i=2;i<=sum;++i)s[i]+=s[i-1];for(int i=2;i<=sum;++i)s[i]+=s[i-1];
    for(int i=0;i<=sum;++i)
        for(int j=0;j<=s[i];++j)pre[i][j]=1;
    reverse(b+1,b+m+1),f[0].resize(1),f[0][0][0]=1;
    for(int i=1,lim;i<=m;++i){
        lim=sum/b[i],f[i].resize(lim+1),f[i][0][0]=1;
        for(int j=1;j<=lim;++j){
            if(j<f[i-1].size())f[i][j]|=f[i-1][j];
            f[i][j]|=(f[i][j-1]<<b[i]),f[i][j]&=pre[j];
        }
    }
    for(int i=1;i<f[m].size();++i)if(f[m][i][sum]){ans=i;break;}
    cout<<ans<<'\n';if(ans==-1)return 0;
    for(int i=ans,j=m;i;sum-=b[j],c[i]=b[j],--i)
        for(;!f[j][i][sum]||!f[j][i-1][sum-b[j]];--j);
    for(int i=1;i<=n;++i)q.push({a[i],i});
    for(int i=1;i<=ans;++i){
        cout<<c[i]<<' ';rv={};
        for(int j=1;j<=c[i];++j){
            pr t=q.top();q.pop(),--t.first;
            cout<<t.second<<' ';if(t.first)rv.push_back(t);
        }
        for(pr i:rv)q.push(i);cout<<'\n';
    }
    return 0;
}

::::

题 6

对于单次询问，首先发现可以枚举 x 最终加到了 t，这个数必须覆盖了 a[l,r] 中所存在的最高位，设这是第 k 位。显然 \le t 的数可以只用一次操作做掉，而 >t 的数分别需要一次操作去消除最高位和其他位，也就是两次。

那么答案可以写成：

2(r-l+1)+\min_{t \ge 2^k}\left\{t-\sum _{i=l}^{r}[a_i\le t]\right\}

发现对 t 的限制与 a_i \le t 可以化简，令 b 序列为每个 a 中 \ge 2^k 的数减去 2^k 拼接形成的序列，记其长度为 m。运用合理手段改写成：

2^k+(r-l+1)+\sum _{i=l}^{r}[a_i \ge 2^k]-\max_{t \ge 0}\left\{\sum _{i=l'}^{r'}[b_i\le t]-t\right\}

其中 b[l',r'] 即 a[l,r] 在 b 中所对应的区间。前面几个部分都简单，考虑最后这个

\max_{t \ge 0}\left\{\sum _{i=l'}^{r'}[b_i\le t]-t\right\}

怎么求。一个直观的感受是很像 Hall 定理，考虑构造一个二分图：左部点分别对应 b_1,b_2,\cdots b_{m}，右部点分别对应每个自然数。若 b_i \ge j，那么就连边。显然这个式子就是该二分图的左部失配点数。

发现对于这样的二分图匹配，我们可以以任意顺序枚举 b 匹配（但是显然其匹配点 j 来说，j 应该尽可能大），且不需要反悔。因为在每个点匹配点 j 尽可能大的情况下，无法匹配只会是整个前缀被匹配，换掉前面的其他点不会更优。

那么不妨对于一次询问按 r',r'-1,\cdots,l' 的顺序依次匹配。

扫描线，扫到 r 的时候尝试加入 r，若不可以直接加入，就删掉可以使它能加入的最靠前的位置后加入。那么这个删掉的点即失配点，单次询问求在前缀 [1,r'] 中有几个 [l',r'] 中的失配点。

考虑如何维护新的失配点的位置，设当前左部点集为 S，我们在每个位置 x 维护 d_x=\sum _{p\in S}[p \le x]-x 的值，现在加入 b_r，利用 Hall 定理判定 S 是否可以全部匹配，写作 \max\{d_i\}\le 0。若这个条件不符合，意味着要删点，因为 d_i \le 1，所以就是找到第一个位置 x 满足 d_x=1，删除的位置就是 b_i\le x 的最靠前的位置。

那么对于每个 k 做一次，序列上的每个 a_i 和每次询问对应一个唯一 k，那么它们都只被考虑一次。利用主席树维护二维数点即可。

时间复杂度 \mathcal{O}\big((n+q)\log V\big)，空间复杂度为 \mathcal{O}\big(n\log V\big)。

::::info[代码]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=200005,inf=1e9;
int n,sz,b[N],p[N],rk[N],po[N],c[61][N],rt[61][N];ll v[N];
vector<int> s[61],S;
struct seg{
    int G[N<<2],M[N<<2];
    inline void push(int id,int k){
        M[id]+=k,G[id]+=k;
    }
    inline void pushdown(int id){
        if(G[id])push(id<<1,G[id]),push(id<<1|1,G[id]),G[id]=0;
    }
    inline void B(int id,int l,int r){
        G[id]=0;if(l==r)return M[id]=-l,void();int mid=l+r>>1;
        B(id<<1,l,mid),B(id<<1|1,mid+1,r),M[id]=max(M[id<<1],M[id<<1|1]);
    }
    inline int fd(int id,int l,int r){
        if(l==r)return l;int mid=l+r>>1;pushdown(id);
        return M[id<<1]>0?fd(id<<1,l,mid):fd(id<<1|1,mid+1,r);
    }
    inline void U(int id,int l,int r,int x,int y,int k){
        if(x<=l&&y>=r)return push(id,k);int mid=l+r>>1;pushdown(id);
        if(x<=mid)U(id<<1,l,mid,x,y,k);if(y>mid)U(id<<1|1,mid+1,r,x,y,k);
        M[id]=max(M[id<<1],M[id<<1|1]);
    }
}T;
struct finder{
    set<int> s[N<<2];int M[N<<2];
    inline void push(int id){
        s[id].erase(s[id].begin()),
        M[id]=s[id].size()?*s[id].begin():inf;
    }
    inline void U(int id,int l,int r,int x,int k){
        if(l==r)return s[id].insert(k),M[id]=*s[id].begin(),void();
        int mid=l+r>>1;x<=mid?U(id<<1,l,mid,x,k):U(id<<1|1,mid+1,r,x,k);
        M[id]=min(M[id<<1],M[id<<1|1]);
    }
    inline int D(int id,int l,int r,int x){
        if(M[id]>x||(l==r&&M[id]!=x))return 0;
        if(l==r)return l=*s[id].begin(),push(id),l;int mid=l+r>>1,res=0;
        if(M[id<<1]<=x)res=D(id<<1,l,mid,x);
        if(M[id<<1|1]<=x&&!res)res=D(id<<1|1,mid+1,r,x);
        M[id]=min(M[id<<1],M[id<<1|1]);return res;
    }
    inline int fd(int id,int l,int r,int y){
        if(r<=y)return M[id];int mid=l+r>>1,res=fd(id<<1,l,mid,y);
        if(mid<y)res=min(res,fd(id<<1|1,mid+1,r,y));
        return res;
    }
    inline void B(int id,int l,int r){
        M[id]=inf;if(l==r)return s[id].clear();
        int mid=l+r>>1;B(id<<1,l,mid),B(id<<1|1,mid+1,r);
    }
}W;
struct solver{
    int cnt=0;
    struct node{
        int ls,rs,sm;
    }t[N<<6];
    inline void U(int &id,int l,int r,int x){
        t[++cnt]=t[id],id=cnt,++t[id].sm;
        if(l==r)return;int mid=l+r>>1;
        x<=mid?U(t[id].ls,l,mid,x):U(t[id].rs,mid+1,r,x);
    }
    inline int Q(int id,int l,int r,int x,int y){
        if(!id)return 0;if(x<=l&&y>=r)return t[id].sm;
        int mid=l+r>>1,res=0;if(x<=mid)res=Q(t[id].ls,l,mid,x,y);
        if(y>mid)res+=Q(t[id].rs,mid+1,r,x,y);return res;
    }
}E;
inline bool cmp(int x,int y){
    return v[x]<v[y];
}
void init(int n,const vector<ll> &a){
    ::n=n;
    for(int i=1;i<=n;++i)s[b[i]=__lg(v[i]=a[i-1])].push_back(i),v[i]-=1ll<<b[i],c[b[i]][i]=1;
    for(int k=0;k<60;++k){
        if(!s[k].size())continue;
        for(int i=1;i<=n;++i)c[k][i]+=c[k][i-1];
        S=s[k];sort(S.begin(),S.end(),cmp),sz=S.size();
        rk[S[0]]=1;for(int i=1;i<sz;++i)rk[S[i]]=rk[S[i-1]]+(v[S[i]]!=v[S[i-1]]);
        for(int i:S)if(v[i]<=n)po[v[i]]=i;
        sz=rk[S[sz-1]],T.B(1,1,n),W.B(1,1,sz);
        for(int i=1;i<=n;++i){
            rt[k][i]=rt[k][i-1];
            if(b[i]==k&&v[i]<=n){   
                if(!v[i]){E.U(rt[k][i],1,n,i);continue;}
                W.U(1,1,sz,rk[i],i),T.U(1,1,n,v[i],n,1);
                if(T.M[1]>0){
                    int h=T.fd(1,1,n),ps=W.fd(1,1,sz,rk[po[h]]);
                    ps=W.D(1,1,sz,ps),T.U(1,1,n,v[ps],n,-1),E.U(rt[k][i],1,n,ps);
                }
            }
        }
    }
}
ll ask(int l,int r){
    int k;for(int i=60;~i;--i)if(c[i][r]-c[i][l-1]){k=i;break;}
    return (1ll<<k)+(r-l+1)+c[k][r]-c[k][l-1]-E.Q(rt[k][r],1,n,l,r);
}
vector<ll> askAll(int q,const vector<int> &l,const vector<int> &r){
    vector<ll> ans;
    for(int i=0;i<q;++i)ans.push_back(ask(l[i],r[i]));
    return ans;
}

::::

题 7

显然一只蚂蚁与一块方糖匹配，是类似图匹配的结构。那么考虑考虑朝距离 \le L 的所有方糖连一条边，这个二分图的最大匹配就是答案。

分别记 a_i,b_i 为位置 i 的蚂蚁数和方糖数。

运用 Hall 定理，我们知道二分图最大匹配是 \sum a_i-\max\limits_{S}\{0,\sum_{i \in S}a_i-\sum_{i \in N(S)}b_i\}。

考虑将 S 表示为 k 个不交区间的并 [l_1,r_1]\cup [l_2,r_2]\cup\cdots\cup[l_k,r_k]。

则 N(S)=\big[l_1-L,r_1+L\big]\cup \big[l_2-L,r_2+L\big]\cup\cdots\cup\big[l_k-L,r_k+L\big]。

这些区间也最好不交，这要求了 l_{i+1}-r_i >2L。

如果出现了 l_{i+1}-r_i \le 2L，我们可以将区间 [l_i,r_i],[l_{i+1},r_{i+1}] 合并为区间 [l_i,r_{i+1}]，这样 N(S) 不变，但 S 不减。一定是不劣的。

考虑用一个简单的形式刻画 \sum_{i \in N(S)}b_i，可以写成所有区间减去相邻区间交。两个部分的表示都不难，修改后的变化容易表示。

可以直接上线段树转移，维护 f_{0/1,0/1} 表示目前区间左端点选/不选，右端点选/不选的最大值。转移时枚举一下中点怎么选就好了。

需要对坐标离散化一下。时间复杂度 \mathcal{O}\big(q\log q\big)，空间复杂度 \mathcal{O}(q)。

::::info[代码]

#include<bits/stdc++.h>
#define vector basic_string
#define int long long
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read(){
    register int x=0,s=gc;while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=500005,inf=1e16;
int n,q,L;
struct query{
    int op,x,v;
}t[N];
vector<int> v;
struct seg{
    int f[N<<2][2][2],w[N<<2],t[N<<2];
    inline void chkmax(int &x,int y){
        x=x<y?y:x;
    }
    inline void pushup(int id){
        for(int i:{0,1})for(int j:{0,1})f[id][i][j]=-inf;
        for(int l1:{0,1})for(int r1:{0,1})
            for(int l2:{0,1})for(int r2:{0,1})
                chkmax(f[id][l1][r2],
                    f[id<<1][l1][r1]+f[id<<1|1][l2][r2]+(r1&&l2)*w[id]);}
    inline void push(int id,int k){
        t[id]+=k,w[id]+=k;
        for(int i:{0,1})for(int j:{0,1})f[id][i][j]-=k;
        chkmax(f[id][0][0],0);
    }
    inline void pushdown(int id){
        if(t[id])push(id<<1,t[id]),push(id<<1|1,t[id]),t[id]=0;
    }
    inline void U(int id,int l,int r,int x,int k){
        if(l==r)return f[id][1][1]+=k,void();
        int mid=l+r>>1;pushdown(id);
        x<=mid?U(id<<1,l,mid,x,k):U(id<<1|1,mid+1,r,x,k),pushup(id);
    }
    inline void U(int id,int l,int r,int x,int y,int k){
        if(x>y)return;if(x<=l&&y>=r)return push(id,k);
        int mid=l+r>>1;pushdown(id);
        if(x<=mid)U(id<<1,l,mid,x,y,k);
        if(y>mid)U(id<<1|1,mid+1,r,x,y,k);
        if(x<=mid&&y>mid)w[id]+=k;pushup(id);
    }
    inline int res(){
        return max({f[1][0][0],f[1][0][1],f[1][1][0],f[1][1][1]});
    }
}T;
signed main(){
    q=rd,L=rd;for(int i=1;i<=q;++i)t[i]={rd,rd,rd},v+=t[i].x;
    sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end()),n=v.size();
    for(int i=1,l,r,ans=0;i<=q;++i){
        if(t[i].op==1)
            l=lower_bound(v.begin(),v.end(),t[i].x)-v.begin()+1,
            T.U(1,1,n,l,t[i].v),ans+=t[i].v;
        else
            l=lower_bound(v.begin(),v.end(),t[i].x-L)-v.begin()+1,
            r=upper_bound(v.begin(),v.end(),t[i].x+L)-v.begin(),
            T.U(1,1,n,l,r,t[i].v);
        cout<<ans-T.res()<<'\n';
    }
    return 0;
}

::::