bzoj 3879 虚树
2024-10-10 23:02:58
题目大意:
给一个字符串,多次询问k个后缀,求它们两两间LCP长度总和
分析:
转化为后缀树,用虚树求
注意:
后缀树中代表后缀的点都是叶子节点
题目中取模并没有卵用
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
using namespace std;
typedef long long LL;
const int M=1000007;
inline int rd(){
int x=0;bool f=1;char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=0;
for(;isdigit(c);c=getchar()) x=x*10+c-48;
return f?x:-x;
}
int n,m;
char s[M];
int ch[M][26];
int pre[M];
LL len[M],sz[M];
int last=1,tot=1;
int g[M],te,hd[M],td;
struct edge{int y,next;}e[M],dw[M];
int dfn[M],tdfn;
LL ans;
int ln[M<<1],pos[M],T;
int a[M<<1][23];
int que[M*3];
int st[M],cnt;
int id[M];
void addedge(int x,int y){
e[++te].y=y;
e[te].next=g[x];
g[x]=te;
}
void addlink(int x,int y){
if(x==y) return ;
dw[++td].y=y;
dw[td].next=hd[x];
hd[x]=td;
}
int newnode(int x){
++tot;
len[tot]=x;
return tot;
}
void Sam(int x){
int p,q,np,nq;
p=last;
last=np=newnode(len[last]+1);
for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=np;
if(!p) pre[np]=1;
else{
q=ch[p][x];
if(len[q]==len[p]+1) pre[np]=q;
else{
nq=newnode(len[p]+1);
for(int i=0;i<26;i++) ch[nq][i]=ch[q][i];
pre[nq]=pre[q];
pre[q]=pre[np]=nq;
for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=nq;
}
}
}
void dfs(int x){
dfn[x]=++tdfn;
a[pos[x]=++T][0]=x;
int p,y;
for(p=g[x];p;p=e[p].next){
y=e[p].y;
dfs(y);
a[++T][0]=x;
}
}
int mn(int x,int y){
return dfn[x]<dfn[y]?x:y;
}
void init(){
int i,j,l;
for(i=2;i<=T;i++) ln[i]=ln[i>>1]+1;
for(i=T;i>0;i--){
l=ln[T-i+1];
for(j=1;j<=l;j++)
a[i][j]=mn(a[i][j-1],a[i+(1<<j-1)][j-1]);
}
}
int LCA(int x,int y){
x=pos[x],y=pos[y];
if(x>y)swap(x,y);
int l=ln[y-x+1];
return mn(a[x][l],a[y-(1<<l)+1][l]);
}
bool cmp(int x,int y){return dfn[x]<dfn[y];}
void vbuild(int z){
int i,x,anc;
sort(que+1,que+z+1,cmp);
z=unique(que+1,que+z+1)-(que+1);
for(i=1;i<z;i++){
x=LCA(que[i],que[i+1]);
hd[x]=0; sz[x]=0;
}
hd[1]=0; sz[1]=0;
for(i=1;i<=z;i++){
x=que[i];
hd[x]=0; sz[x]=1;
}
td=cnt=0;
st[++cnt]=1;
for(i=1;i<=z;i++){
x=que[i];
anc=LCA(x,st[cnt]);
if(anc==st[cnt]) st[++cnt]=x;
else{
while(cnt>1 && anc==LCA(st[cnt-1],x)){
addlink(st[cnt-1],st[cnt]);
cnt--;
}
addlink(anc,st[cnt]);
st[cnt]=anc;
st[++cnt]=x;
}
}
for(i=1;i<cnt;i++) addlink(st[i],st[i+1]);
}
void dp(int x){
int p,y;
for(p=hd[x];p;p=dw[p].next){
y=dw[p].y;
dp(y);
ans+=(sz[x]*sz[y])*len[x];
sz[x]+=sz[y];
}
}
int main(){
int i,z;
n=rd();m=rd();
scanf("%s",s+1);
for(i=n;i>0;i--){
Sam(s[i]-'a');
id[i]=last;
}
for(i=2;i<=tot;i++) addedge(pre[i],i);
dfs(1);
init();
while(m--){
z=rd();
for(i=1;i<=z;i++) que[i]=id[rd()];
vbuild(z);
ans=0;
dp(1);
printf("%lld\n",ans);
}
return 0;
}
最新文章
- (七)Transformation和action详解-Java&;Python版Spark
- 关于 K米 —— 的案例分析
- S1:变量
- Settings.System.getInt获取Setting里的设置信息
- apache vhost 访问权限配置
- android图片的压缩和水印
- Scala学习笔记--Actor和并发
- 使用NCoding归档进行存储数据时候报错
- google软件测试之道读后感(一)
- CCF系列之相邻数对(201409-1)
- 如何取消Microsoft账户登录电脑
- 程序员的沟通之痛https://blog.csdn.net/qq_35230695/article/details/80283720
- DocumentEvent事件的应用
- 0723掰棒子记录--vue的数据渲染
- 简单的使用Nginx框架搭建Web服务器~
- HTML5将<;video>;视频设置为页面动态背景
- Generalization and Equilibrium in Generative Adversarial Nets
- Python 字典的遍历
- HDU 1016:Prime Ring Problem
- 8VC Venture Cup 2016 - Elimination Round E. Simple Skewness 暴力+二分
热门文章
- Sublime text 3 如何格式化HTML代码
- Inno Setup入门(二十一)&mdash;&mdash;Inno Setup类参考(7)
- JQuery获取input type=";text";中的值的各种方式
- table详解
- spring 分散配置
- cannot create windows service for mysql
- TextureView+SurfaceTexture+OpenGL ES来播放视频(二)
- Spring Boot 系列教程4-JDBC
- PullToRefreshGridView上拉加载、下拉刷新
- surpersocket客户端