SPOJ COT 4 题解
将s,t都反向，然后二分。
/*
{
######################
# Author #
# Gary #
# 2021 #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
// int x=0;
// char ch=getchar();
// while(ch<'0'||ch>'9'){
// ch=getchar();
// }
// while(ch>='0'&&ch<='9'){
// x=(x<<1)+(x<<3)+(ch^48);
// ch=getchar();
// }
// return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MAXN=300000+233;
vector<int> tree[MAXN];
const int MAXLEN=1e5+20;
struct state{
int len,link,minlen;
unordered_map<char,int> ch;
};
struct SAM{
int sz=0;
state st[MAXLEN+MAXLEN];
void sam_init(){
st[0].len=0;
st[0].link=-1;
sz=0;
}
SAM(){
sam_init();
}
int sam_extend(char c,int last){
if(st[last].ch.find(c)!=st[last].ch.end()){
return st[last].ch[c];
}
int cur=++sz;
st[cur].len=st[last].len+1;
int p=last;
while(p!=-1&&st[p].ch.find(c)==st[p].ch.end()){
st[p].ch[c]=cur;
p=st[p].link;
}
if(p==-1){
st[cur].link=0;
}
else{
int q=st[p].ch[c];
if(st[q].len==st[p].len+1){
st[cur].link=q;
}
else{
int clone;
clone=++sz;
st[clone].len=st[p].len+1;
st[clone].ch=st[q].ch;
st[clone].link=st[q].link;
while(p!=-1&&st[p].ch.find(c)!=st[p].ch.end()&&st[p].ch[c]==q){
st[p].ch[c]=clone;
p=st[p].link;
}
st[cur].link=st[q].link=clone;
}
}
return cur;
}
void gettree(){
rb(i,1,sz) tree[st[i].link].PB(i);
}
}sam;
int cnt;
int son[MAXN][26],fa[MAXN],belong[MAXN],is[MAXN],stay[MAXN],val[MAXN],anc[MAXN][32][4],depth[MAXN];
vector<mp> failtree[MAXN];
void lab(int now){
for(auto it:tree[now]){
lab(it);
if(!belong[now]) belong[now]=belong[it];
}
}
int getanc(int now,int k){
if(k>depth[now]) return -1;
rep(i,4){
now=anc[now][k&31][i];
k>>=5;
}
return now;
}
void buildanc(){
rb(i,1,cnt) rep(k,4) anc[i][0][k]=i;
rb(j,1,31) rb(i,1,cnt) anc[i][j][0]=anc[fa[i]][j-1][0];
rb(k,1,3) rb(i,1,cnt) rb(j,1,31){
if(j==1){
anc[i][1][k]=anc[anc[i][16][k-1]][16][k-1];
}
else{
anc[i][j][k]=anc[anc[i][j-1][k]][1][k];
}
}
}
void gao(int now){
for(auto it:tree[now]) gao(it);
for(auto it:tree[now]){
failtree[now].PB({val[getanc(belong[it],sam.st[now].len)],it});
}
}
int tot=0,tmprank[MAXN];
void my_sort(int now){
sort(ALL(failtree[now]));
tmprank[now]=++tot;
for(auto it:failtree[now]){
my_sort(it.SEC);
}
}
int rnk[MAXN],sa[MAXN];
void my_sort(){
sam.gettree();
lab(0);
gao(0);
my_sort(0);
vector<int> use;
rb(i,0,cnt) use.PB(tmprank[is[i]]);
sort(ALL(use));
rb(i,0,cnt){
rnk[i]=lower_bound(ALL(use),tmprank[is[i]])-use.begin()+1,sa[rnk[i]]=i;
// cout<<rnk[i]<<"!
";
}
}
mp range[300000+20];
mp crange[26];
int ans[300000+20];
int Len[300000+20];
vector<pair<int,mp> > query[MAXN];
int lowbound(int l,int r,int x,int lent){
if(rnk[getanc(sa[l],lent)]>=x){
return l;
}
if(rnk[getanc(sa[r],lent)]<x){
return r+1;
}
while(l<r){
int mid=(l+r)>>1;
int anc=getanc(sa[mid],lent);
if(rnk[anc]>=x){
r=mid;
}
else{
l=mid+1;
}
}
return l;
}
mp merge(mp A,mp B,int lent){
if(A.FIR==INF||B.FIR==INF) return {INF,-INF};
mp ret;
ret.FIR=lowbound(A.FIR,A.SEC,B.FIR,lent);//找到第一个>=x的位置
ret.SEC=lowbound(A.FIR,A.SEC,B.SEC+1,lent);
ret.SEC--;
if(ret.FIR>ret.SEC) ret={INF,-INF};
return ret;
}
int bit[MAXN+1];
void add(int pos,int val=1){
while(pos<=MAXN){
bit[pos]+=val;
pos+=pos&(-pos);
}
}
int quey(int pos){
int ret=0;
while(pos){
ret+=bit[pos];
pos-=pos&(-pos);
}
return ret;
}
int quey(int l,int r){
return quey(r)-quey(l-1);
}
void goanswer(int now){
add(rnk[now]);
for(auto it:query[now]){
if(it.SEC.FIR==1||it.SEC.FIR>it.SEC.SEC){
continue;
}
ans[it.FIR]=quey(it.SEC.FIR,it.SEC.SEC);
}
rep(i,26) if(son[now][i]) goanswer(son[now][i]);
add(rnk[now],-1);
}
int main(){
int Q;
scanf("%d",&Q);
vector<pair<int,mp> > ope;
stay[1]=0;
int n=1;
rb(i,1,Q){
int ty;
scanf("%d",&ty);
if(ty==1){
int si;
char c;
scanf("%d",&si);
cin>>c;
++n;
if(son[stay[si]][c-'a']);
else{
son[stay[si]][c-'a']=++cnt;
fa[cnt]=stay[si];
val[cnt]=c-'a';
depth[cnt]=depth[fa[cnt]]+1;
}
stay[n]=son[stay[si]][c-'a'];
}
if(ty==2){
int x,ti;
char c;
scanf("%d%d",&x,&ti),cin>>c;
ope.PB({x,{ti,c-'a'}});
}
if(ty==3){
int ti,tj;
scanf("%d%d",&ti,&tj);
ope.PB({ty,{ti,tj}});
}
if(ty==4){
int ti,si;
scanf("%d%d",&ti,&si);
ope.PB({ty,{ti,si}});
}
}
rb(i,1,cnt) is[i]=sam.sam_extend(val[i]+'a',is[fa[i]]),belong[is[i]]=i;
buildanc();
my_sort();
range[1]={1,n};
rep(i,26) crange[i]={INF,-INF};
rb(i,1,cnt){
check_min(crange[val[i]].FIR,rnk[i]);
check_max(crange[val[i]].SEC,rnk[i]);
}
int Que=0;
n=1;
for(auto it:ope){
if(it.FIR==0){
range[++n]=merge(range[it.SEC.FIR],crange[it.SEC.SEC],Len[it.SEC.FIR]);
Len[n]=Len[it.SEC.FIR]+1;
}
if(it.FIR==1){
range[++n]=merge(crange[it.SEC.SEC],range[it.SEC.FIR],1);
Len[n]=Len[it.SEC.FIR]+1;
}
if(it.FIR==3){
range[++n]=merge(range[it.SEC.SEC],range[it.SEC.FIR],Len[it.SEC.SEC]);
Len[n]=Len[it.SEC.FIR]+Len[it.SEC.SEC];
check_min(Len[n],1000000000);
}
if(it.FIR==4){
Que++;
query[stay[it.SEC.SEC]].PB({Que,range[it.SEC.FIR]});
}
}
goanswer(0);
rb(i,1,Que){
printf("%d
",ans[i]);
}
return 0;
}