bzoj3467: Crash和陶陶的游戏

就一篇题解：

BZOJ3467 : Crash和陶陶的游戏 - weixin_34248487的博客 - CSDN博客

1.离线，建出Atrie树；B树的倍增哈希数组，节点按照到根路径字典序排序

2.处理A节点对应前缀对应B中的极长可以匹配的区间。在父亲节点区间内二分即可

3.更新答案：

①加入A点，找区间中B中已经出现点个数。树状数组

②加入B点，本质是B到根的字符串放在trie最大匹配长度，二分，哈希表存A树是否有这个前缀，得到的长度就是当前匹配长度。

直上直下的链本质是字符串的前缀后缀。

动态更新hash很难，就离线，在可能贡献的集合内找到当前出现的。

假装有代码.jpg

这个是两个logn的

可以变成一个logn！

sort是不必要的，

对于②B树点对trie的影响，不妨直接倍增+hash找到最长的匹配位置y，在y的位置++，然后①时候子树查询即可！

通过提前打好标记使得不用同时考虑很多！

（类似预处理）

还有可能一个点有多个c儿子，要合并成一个。①的时候整个子树++，表示到根的路径上多了一个点，②的时候，匹配最长位置单点查询这个值

两个树状数组

注意，unsigned long long哈希

单模数随便rand就卡掉了

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^'0')
#define ul unsigned long long
#define ll unsigned long long
using namespace std;
il void rd(int &x){char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);
}
template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');}
template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{
const int N=2e5+5;
const ul base=233;
const int orz=100000;struct HA{int nxt[N],hd[N],cnt;ul val[N];int id[N];void ins(int x,ll h){int pos=h%orz;nxt[++cnt]=hd[pos];hd[pos]=cnt;val[cnt]=h;id[cnt]=x;}int query(ll h){int pos=h%orz;for(reg i=hd[pos];i;i=nxt[i]){if(val[i]==h) return id[i];}return -1;}
}ha;
//trie
int ch[N][26];
int id[N];//is
int n;
int tot;
int lp;
ul pw[(1<<17)+233];
void ins(int x,int c){++lp;x=id[x];
//    cout<<" true fa "<<x<<" ch "<<ch[x][c]<<endl;if(ch[x][c]){id[lp]=ch[x][c];return;}id[lp]=++tot;ch[x][c]=tot;
}
int dfn[N],df,dfn2[N];
void fin(int x,ul haxi,int d){dfn[x]=++df;if(x!=1){ha.ins(x,haxi);}for(reg i=0;i<26;++i){if(ch[x][i]){fin(ch[x][i],haxi+(ll)pw[d]*(i+1),d+1);}}dfn2[x]=df;
}
//B tree
int cur;
struct node{int nxt,to;int val;
}e[2*N];
int hd[N],cnt;
void add(int x,int y,int z){e[++cnt].nxt=hd[x];e[cnt].to=y;e[cnt].val=z;hd[x]=cnt;
}
int fa[N][18];
ul hsh[N][18];
void dfs(int x){for(reg i=hd[x];i;i=e[i].nxt){int y=e[i].to;fa[y][0]=x;hsh[y][0]=e[i].val+1;dfs(y);}
}
//question
struct que{int typ,fa,c;int x;
}q[N];int get(int x){ll now=0;int has=0;int ret=0;for(reg j=17;j>=0;--j){if(!fa[x][j]) continue;ll tmp=((ll)now+pw[has]*hsh[x][j]);int nc=ha.query(tmp);if(nc!=-1){ret=nc;now=tmp;has+=(1<<j);x=fa[x][j];//shit
        }}return ret;
}struct treearray{int f[N];int n;void upda(int x,int c){for(;x<=n;x+=x&(-x)) f[x]+=c;}int query(int x){int ret=0;for(;x;x-=x&(-x)) ret+=f[x];return ret;}
}t1,t2;
int main(){rd(n);char s[233];++tot;++cur;//startlp=1;id[1]=1;ll ans=0;ans=1;//1 1for(reg i=1;i<=n;++i){rd(q[i].typ);rd(q[i].fa);//rd(q[i].c);scanf("%s",s+1);q[i].c=s[1]-'a';if(q[i].typ==1){ins(q[i].fa,q[i].c);q[i].x=id[lp];
//            prt(id,1,lp);}else{++cur;q[i].x=cur;add(q[i].fa,cur,q[i].c);}
//        cout<<tot<<" ";
    }
//    cout<<endl<<endl;dfs(1);
//    cout<<"after dfs "<<tot<<endl;
//    prt(id,1,lp);
    pw[0]=1;for(reg i=1;i<=(1<<17);++i){pw[i]=(ll)pw[i-1]*base;//%mod;
    }for(reg j=1;j<=17;++j){for(reg i=1;i<=cur;++i){fa[i][j]=fa[fa[i][j-1]][j-1];hsh[i][j]=((ll)hsh[i][j-1]+(ll)hsh[fa[i][j-1]][j-1]*pw[1<<(j-1)]);//%mod)%mod;
        }}
//    cout<<"after bezeng "<<endl;fin(1,0,0);
//    cout<<" after fin "<<endl;t1.n=t2.n=tot;
//    cout<<" tot "<<tot<<endl;
//    prt(dfn,1,tot);
//    cout<<" dfn2-------------------------- "<<endl;
//    prt(dfn2,1,tot);int tc=0,tb=0;for(reg i=1;i<=n;++i){if(q[i].typ==1){//add trie++tc;
//            cout<<"trie "<<endl;int x=q[i].x;//ch[id[q[i].fa]][q[i].c];
//            cout<<"x "<<x<<" tc "<<tc<<endl;ans+=t1.query(dfn2[x])-t1.query(dfn[x]-1);t2.upda(dfn[x],1);t2.upda(dfn2[x]+1,-1);}else{//add B tree++tb;
//            cout<<" Btree "<<endl;
//            cout<<" x "<<q[i].x<<endl;int y=get(q[i].x);
//            cout<<" y "<<y<<" tb "<<tb<<" dfn "<<dfn[y]<<endl;if(y){ans+=t2.query(dfn[y]);t1.upda(dfn[y],1);}++ans;}printf("%lld\n",ans);}return 0;
}}
signed main(){
//    freopen("5.in","r",stdin);
//    freopen("my.out","w",stdout);
    Miracle::main();return 0;
}/*Author: *Miracle*Date: 2019/3/26 18:56:24
*/