当前位置：首页 > news >正文

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

news 2025/9/14 15:07:01

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

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

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

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

#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;
}