正题

题目链接:https://www.luogu.com.cn/problem/P5180

---

题目大意

给出 n n n个点的一张有向图，求每个点支配的点数量。

1 ≤ n ≤ 2 × 1 0 5 , 1 ≤ m ≤ 3 × 1 0 5 1\leq n\leq 2\times 10^5,1\leq m\leq 3\times 10^5 1≤n≤2×105,1≤m≤3×105

---

解题思路

首先定义半支配点 s e m i x semi_x semix​表示对于点 x x x寻找一个 d f n dfn dfn序最小的点 y y y满足存在一条 y y y到 x x x的路径去掉头尾之后所有点的 d f n dfn dfn序都大于 x x x的。

考虑怎么求每个点的半支配点，考虑两种情况对于一个能够直接到达 x x x的点 y y y

1. d f n y < d f n x dfn_y<dfn_x dfny​<dfnx​：那么 y y y可能是 x x x的半支配点
2. d f n y > d f n x dfn_y>dfn_x dfny​>dfnx​：那么设 v v v表示 y y y到 d f s dfs dfs根节点的路径上的某个点 u u u的 d f n dfn dfn序最小的半支配点，那么 v v v可能是 u u u的半支配点

主要是第二种情况我们相当于要找一个在某个点到根节点路径上的点使得它的半支配点 d f n dfn dfn序最小。

那么可以考虑倒序枚举，然后用带权并查集维护那个半支配点编号最小的。

之后就是半支配点有什么用，大概就是半支配点向点连边那么新的图支配关系不变。

所以一种暴力的做法就是直接跑 D A G DAG DAG的支配树求法，但是有更快的。

考虑对于一个点 x x x和它的半支配点 y y y，如果 y y y到 x x x的路径上我们找到一个半支配点 d f n dfn dfn序最小的节点 u u u且它的半支配点为 v v v。
那么如果

1. v = y v=y v=y，那么证明整条路径上没有 d f n dfn dfn序更小的半支配点， y y y就是 x x x的支配点。
2. d u > d y d_u>d_y du​>dy​，那么显然 u u u有更小的支配点支配这套路径，所以 u u u的支配点就是 y y y的支配点

这个过程中 u u u和 v v v的维护和上面一样，所以可以一起求解。

但是我们可以暂时不知道 u u u的支配点，所以可以先记录，最后在正序的记回去。

时间复杂度 O ( n α ( n ) ) O(n\alpha(n)) O(nα(n))

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2100;
struct node{
	int l,r;
}q[110000];
int n,m,k,t,ans,p[N],st[N][26],ss[N][26],nxt[N],f[N][N],pre[N][N];
char T[N],S[N];
bool cmp(node x,node y)
{return x.l<y.l;}
int main()
{
	freopen("lcs.in","r",stdin);
	freopen("lcs.out","w",stdout);
	scanf("%s",T+1);m=strlen(T+1);
	scanf("%s",S+1);n=strlen(S+1);
	for(int i=1;i<=m;i++){
		for(int j=0;j<26;j++)
			st[i][j]=st[i-1][j]+(T[i]=='a'+j);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<26;j++)
			ss[i][j]=ss[i-1][j]+(S[i]=='a'+j);
	}
	scanf("%d",&k);
	for(int i=1;i<=k;i++)
		scanf("%d%d",&q[i].l,&q[i].r),q[i].l++,q[i].r++;
	sort(q+1,q+1+k,cmp);
	int nowr=0,pr=0;
	for(int i=1;i<=k;i++){
		if(q[i].l>nowr){
			nxt[pr]=nowr;
			for(int j=nowr+1;j<q[i].l;j++)nxt[j]=j;
			pr=q[i].l;nowr=q[i].r;
		}
		else nowr=max(q[i].r,nowr);
	}
	nxt[pr]=nowr;
	for(int i=nowr+1;i<=n;i++)nxt[i]=i;
	for(int i=1;i<=n;i++)
		if(nxt[i])p[++t]=i;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=t;j++){
			int l=p[j],r=nxt[l],L=i;
			for(int z=min(r-l,m-L);z>=0;z--){
				bool flag=1;
				for(int k=0;k<26;k++)
					if(ss[r][k]-ss[l-1][k]<st[L+z][k]-st[L-1][k])
						{flag=0;break;}
				if(flag){pre[i][j]=z+1;break;}
			}
		}
	for(int i=1;i<=m;i++)
		for(int j=1;j<=t;j++){
			int l=p[j],r=nxt[l],R=i;
			if(pre[i][j]==r-l+1)continue;
			for(int z=min(r-l,R-1)-1;z>=0;z--){
				bool flag=1;
				for(int k=0;k<26;k++)
					if(ss[r][k]-ss[l-1][k]<st[R][k]-st[R-z-1][k])
						{flag=0;break;}
				if(flag){f[i+1][j+1]=z+1;ans=max(ans,z+1);break;}
			}
		}
	for(int i=1;i<=m;i++)
		for(int j=1;j<=t;j++){
			int l=p[j],r=nxt[l];
			if(pre[i][j]==r-l+1){
				f[i+r-l+1][j+1]=max(f[i+r-l][j+1],f[i][j]+r-l+1);
				ans=max(ans,f[i][j]+r-l+1);
			}
			ans=max(ans,f[i][j]+pre[i][j]);
		}
	printf("%d\n",ans);
	return 0;
}