SA+ST表维护height+单调队列维护：CF1073G

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134043286

https://www.luogu.com.cn/problem/CF1073G

lcp相关的，先跑个sa，然后height建个ST表

现在考虑询问，我们按A和B按 rkrk 排序。现在考虑B->A，反过来同理。

我们可以用单调队列维护，满足height是单增的。因为越往前lcp必然越短。同时要维护有多少个。然后对于当前后缀的答案就是单调队列的大小了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 400010
//#define M
//#define mo
struct node {
	int x, op; 
};
struct Node {
	int x, k; 
};
int n, m, i, j, k, T;
int tmp[N], bin[N], rk[N], sa[N], tot; 
int f[N/2][22], Log2[N]; 
int h[N], height[N], c[2], ans, na, nb, q; 
char s[N]; 

void psort() {
	memset(bin, 0, sizeof(bin)); 
	int i; 
	for(i=1; i<=n; ++i) bin[rk[i]]++; 
	for(i=1; i<=max(n, 128ll); ++i) bin[i]+=bin[i-1]; 
	for(i=n; i>=1; --i) sa[bin[rk[tmp[i]]]--]=tmp[i]; 
}

int lcp(int i, int j) {
	if(i==j) return n-i+1; 
	int l=rk[i]+1, r=rk[j]; 
	int k=Log2[r-l+1]; 
	return min(f[l][k], f[r-(1<<k)+1][k]); 
}

void SA() {
	for(i=1; i<=n; ++i) rk[i]=s[i], tmp[i]=i; 
	psort(); 
//	for(i=1; i<=n; ++i) printf("%lld ", sa[i]); printf("\n"); 
	for(j=1; j<n; j<<=1) {
		for(i=n-j+1, k=0; i<=n; ++i) tmp[++k]=i; 
		for(i=1; i<=n; ++i) if(sa[i]-j>0) tmp[++k]=sa[i]-j; 
		psort(); 
		tmp[sa[1]]=tot=1; 
		for(i=2; i<=n; ++i) {
			if(rk[sa[i]]!=rk[sa[i-1]] || rk[sa[i]+j]!=rk[sa[i-1]+j]) ++tot; 
			tmp[sa[i]]=tot; 
		}
		memcpy(rk, tmp, sizeof(tmp)); 
	}
//	for(i=1; i<=n; ++i) printf("%d ", sa[i]); printf("\n"); 
	for(i=1; i<=n; ++i) {
		h[i]=max(h[i-1]-1, 0ll); 
		j = sa[rk[i]-1]; 
		while(s[i+h[i]] == s[j+h[i]]) ++h[i]; 
	}
//	for(i=2; i<=n; ++i) printf("%d ", h[sa[i]]); 
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); q=read(); 
	scanf("%s", s+1); 
	SA(); 
	for(i=2; i<=n; ++i) height[i]=f[i][0]=h[sa[i]]; 
	for(k=1; k<=20; ++k) 
		for(i=1, j=(1<<k-1)+1; i+(1<<k)-1<=n; ++i, ++j)
			f[i][k]=min(f[i][k-1], f[j][k-1]);
	for(i=2; i<=n; ++i) Log2[i]=Log2[i>>1]+1; 
	while(q--) {
		na=read(); nb=read(); 
		vector<node>v; 
		for(i=1; i<=na; ++i) k=read(), v.pb({k, 0}); 
		for(i=1; i<=nb; ++i) k=read(), v.pb({k, 1}); 
		sort(v.begin(), v.end(), [] (node x, node y) { return rk[x.x]<rk[y.x]; }); 
		stack<Node>z[2]; ans=c[0]=c[1]=0; 
//		z[v[0].op].push({n-v[0].x+1, 1}); 
//		c[v[0].op]+=n-v[0].x+1; 
		for(i=1; i<na+nb; ++i) {
			auto  t=v[i-1]; 
			int o = t.op, k=1, H=lcp(t.x, v[i].x); 
			while(!z[o].empty() && z[o].top().x>=H) {
				auto t2 = z[o].top(); z[o].pop(); 
				k+=t2.k, c[o]-=t2.x*t2.k; 
			}
			z[o].push({H, k}); c[o]+=H*k; 
			k=0; 
			while(!z[o^1].empty() && z[o^1].top().x>=H) {
				auto t2 = z[o^1].top(); z[o^1].pop(); 
				k+=t2.k, c[o^1]-=t2.x*t2.k; 
			}
			if(k) z[o^1].push({H, k}), c[o^1]+=H*k; 
			
//			printf("(%d %d) %lld %lld\n", t.x, t.op, H, c[v[i].op^1]); 
			ans+=c[v[i].op^1]; 
		}
		printf("%lld\n", ans); 
		
	}
	return 0;
}