WA #9#10

很诡异，MAXN改成5e5 #10就能过，但是assert了tot<MAXN20,siz<MAXN100都没事

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=200010;
char s[MAXN];
int n;
int sa[MAXN],rk[MAXN],ct[MAXN],id[MAXN],trk[MAXN*2];
int st[MAXN][20],lg[MAXN];
void build(){
	int m=150;
	for(int i=1;i<=m;i++)ct[i]=0;
	for(int i=1;i<=n;i++)ct[rk[i]=s[i]]++;
	for(int i=1;i<=m;i++)ct[i]+=ct[i-1];
	for(int i=n;i>=1;i--)sa[ct[rk[i]]--]=i;
	for(int i=1;i<=2*n;i++)trk[i]=0;
	for(int k=1;k<=n;k<<=1){
		int p=0;
		for(int i=n;i>n-k;i--)id[++p]=i;
		for(int i=1;i<=n;i++)if(sa[i]>k)id[++p]=sa[i]-k;
		for(int i=1;i<=m;i++)ct[i]=0;
		for(int i=1;i<=n;i++)ct[rk[id[i]]]++;
		for(int i=1;i<=m;i++)ct[i]+=ct[i-1];
		for(int i=n;i>=1;i--)sa[ct[rk[id[i]]]--]=id[i];
		for(int i=1;i<=n;i++)trk[i]=rk[i];
		m=0;
		for(int i=1;i<=n;i++)rk[sa[i]]=(trk[sa[i]]==trk[sa[i-1]]&&trk[sa[i]+k]==trk[sa[i-1]+k])?m:++m;
		if(m==n)break;
	}
	for(int i=1;i<=n;i++){
		if(rk[i]==1)continue;
		int k=max(st[rk[i-1]][0]-1,0);
		while(s[i+k]==s[sa[rk[i]-1]+k])k++;
		st[rk[i]][0]=k;
	}
	for(int i=n;i>=1;i--)
		for(int j=1;i+(1<<j)-1<=n;j++)
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	lg[0]=-1;
	for(int i=1;i<=n;i++)lg[i]=lg[i/2]+1;
}
int lcp(int l,int r){
	l++;
	int d=lg[r-l+1];
	return min(st[l][d],st[r-(1<<d)+1][d]);
}
int lower(int x,int k){
	int l=1,r=x;
	while(l<r){
		int mid=l+r>>1;
		if(lcp(mid,x)>=k)r=mid;
		else l=mid+1;
	}
	return l;
}
int upper(int x,int k){
	int l=x,r=n;
	while(l<r){
		int mid=l+r+1>>1;
		if(lcp(x,mid)>=k)l=mid;
		else r=mid-1;
	}
	return l;
}
int na,nb;
struct node{
	int id,l,r;
}a[MAXN],b[MAXN];
bool cmp(node i,node j){
	return i.r-i.l>j.r-j.l;
}
int tot;
int val[MAXN*20];
struct tree{
	int ls,rs;
}t[MAXN*20];
int rt[MAXN];
struct edge{
	int to,nxt;
}g[MAXN*100];
int cnt,head[MAXN*20],deg[MAXN*20];
void add(int u,int v){
	g[++cnt]=(edge){u,head[v]};
	head[v]=cnt;
	deg[u]++;
}
void copy(int &p){
	t[++tot]=t[p];
	val[tot]=head[tot]=deg[tot]=0;
	p=tot;
}
void modify(int &p,int l,int r,int x,int d){
	if(l==r){
		int pp=p;
		copy(p);
		if(pp)add(p,pp);
		add(p,d);
		return;
	}
	copy(p);
	int mid=l+r>>1;
	if(x<=mid)modify(t[p].ls,l,mid,x,d);
	else modify(t[p].rs,mid+1,r,x,d);
	if(t[p].ls)add(p,t[p].ls);
	if(t[p].rs)add(p,t[p].rs);
}
void query(int p,int l,int r,int x,int y,int d){
	if(!p)return;
	if(x<=l&&r<=y){
		add(d,p);
		return;
	}
	int mid=l+r>>1;
	if(x<=mid)query(t[p].ls,l,mid,x,y,d);
	if(mid<y)query(t[p].rs,mid+1,r,x,y,d);
}
int m;
ll dp[MAXN*20];
int q[MAXN*20],hd,tl;
bool topo(){
	hd=1,tl=0;
	for(int i=1;i<=tot;i++){
		dp[i]=0;
		if(!deg[i])q[++tl]=i;
	}
	while(hd<=tl){
		int u=q[hd++];
		dp[u]+=val[u];
		for(int i=head[u];i;i=g[i].nxt){
			int v=g[i].to;
			dp[v]=max(dp[v],dp[u]);
			if(!--deg[v])q[++tl]=v;
		}
	}
	return tl==tot;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		cin>>s+1;
		n=strlen(s+1);
		build();
		cin>>na;
		for(int i=1;i<=na;i++){
			a[i].id=i;
			cin>>a[i].l>>a[i].r;
			val[i]=a[i].r-a[i].l+1;
		}
		sort(a+1,a+na+1,cmp);
		swap(a[2],a[3]);
		cin>>nb;
		for(int i=1;i<=nb;i++){
			b[i].id=i;
			cin>>b[i].l>>b[i].r;
			val[i+na]=0;
		}
		sort(b+1,b+nb+1,cmp);
		cnt=0;
		for(int i=1;i<=na+nb;i++)head[i]=deg[i]=0;
		tot=na+nb;
		for(int i=1,j=1;i<=nb;i++){
			rt[i]=rt[i-1];
			while(j<=na&&a[j].r-a[j].l>=b[i].r-b[i].l){
				modify(rt[i],1,n,rk[a[j].l],a[j].id);
				j++;
			}
			int x=lower(rk[b[i].l],b[i].r-b[i].l+1);
			int y=upper(rk[b[i].l],b[i].r-b[i].l+1);
			query(rt[i],1,n,x,y,na+b[i].id);
		}
		cin>>m;
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y;
			add(x,na+y);
		}
		if(topo()){
			ll ans=0;
			for(int i=1;i<=na;i++)ans=max(ans,dp[i]);
			cout<<ans<<'\n';
		}
		else cout<<-1<<'\n';
	}
	return 0;
}