自动搬运

查看原文

来自洛谷，原作者为

	李至擎 **

搬运于2025-08-24 22:51:12，当前版本为作者最后更新于2023-11-22 21:51:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

“这不是简单题吗，为什么是黑啊？”——marblue

记位置 $i$ 会对答案产生贡献当且仅当 $a_{i-1}\neq a_i$，问题可以转化成在 $2n$ 个点中选最多的贡献给答案，现在考虑限制。对于两个区间 $[l_1,r_1),[l_2,r_2)$，我们分情况讨论一下：

• $[l_1,r_1)\in[l_2,r_2)$。显然我们先执行 $[l_2,r_2)$ 再执行 $[l_1,r_1)$ 不劣。

• $[l_1,r_1)\cap[l_2,r_2)=\varnothing$。显然互不影响。

• $[l_1,r_1)\cap[l_2,r_2)\neq\varnothing$。令 $l_1<l_2,r_1<r_2$，如果 $[l_1,r_1)$ 在后面则 $r_1$ 会产生贡献，否则 $l_2$ 会产生贡献。所以 $r_1$ 与 $l_2$ 不能同时选择，这就是一个建图后的独立集。

发现题目保证 $l_i,r_i$ 互不相等，故这是一个二分图，跑 bitset 优化 dinic/匈牙利即可，复杂度 $\mathcal{O}(\dfrac{n^3}{w})/\mathcal{O}(\dfrac{n^2\sqrt{n}}{w})$。似乎还可以用可持久化线段树优化建图的 dinic，好像是 $\mathcal{O}(n^2\log n)$，但我不太会（

是 luogu 上的倒数第二劣解，不知道为什么 dinic 这么慢啊，可能复杂度假了？

证明一下为什么找到独立集后一定有对应解。无解当且仅当对于区间执行顺序的先后限制构成环。考虑找到这个环上随便一个区间 $[l_1,r_1)$，假设它取的是右端点 $r_1$ 产生贡献，找到它下一个区间 $[l_2,r_2)$，$l_1<l_2,r_1<r_2$，此时只能是 $r_2$ 产生贡献。于是递归下去，因为 $r_i$ 互不相同，所以环上的区间的 $r$ 单调递增，故不会形成环。

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int n,S,T,dep[10005];bitset<10005>g[10005];
int bfs(){
	for(int i=1;i<=T;i++)dep[i]=0;
	dep[S]=1;queue<int>q;q.push(S);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int v=g[u]._Find_first();v<=T;v=max(v+1,(int)g[u]._Find_next(v))){
			if(g[u][v]==0)continue;
			if(!dep[v])dep[v]=dep[u]+1,q.push(v);
		}
	}
	return dep[T];
}
int dinic(int u,int flow){
	if(u==T)return flow;
	int rest=0;
	for(int v=g[u]._Find_first();v<=T&&flow;v=max(v+1,(int)g[u]._Find_next(v))){
		if(g[u][v]==0)break;
		if(dep[v]!=dep[u]+1)continue;
		int k=dinic(v,min(flow,1));if(!k)dep[v]=0;
		rest+=k,flow-=k;if(k)g[u][v]=0,g[v][u]=1;
	}
	return rest;
}
int l[5005],r[5005],pos[10005];
signed main(){
	n=read(),S=2*n+1,T=2*n+2;
	for(int i=1;i<=n;i++){
		l[i]=read(),r[i]=read();
		pos[l[i]]=0,pos[r[i]]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(l[i]<l[j]&&l[j]<r[i]&&r[i]<r[j]){
				g[l[j]][r[i]]=1;
			}
		}
	}
	for(int i=1;i<=2*n;i++)if(pos[i]==0)g[S][i]=1;
	for(int i=1;i<=2*n;i++)if(pos[i]==1)g[i][T]=1;
	int ans=2*n;
	while(bfs())ans-=dinic(S,inf);
	printf("%d\n",ans);	
	return 0;
}