bzoj 5365 [Lydsy1805月赛]回文树

bzoj 5365 [Lydsy1805月赛]回文树

​​ 虽然lct不能维护hash是错的

但是我们的AK王icefox巨佬依然可以AK 这就是具有神犇体质的人

因为自己没写过直接贴大爷的代码了

get一个技能判断回文可以用正向hash和逆向hash判断 是否相同即可确定是否回文

​

因为字符随机，所以同样的字符很少，我们对于同样的字符内部暴力两两枚举，看x->y是不是一个回文串。 怎么看呢？蒟蒻我不会… 比赛时胡乱写了一个假的lct维护树上hash值。 一开始没维护sz，它过了…过了… 发现后改过，它RE了…缘来是我写挂了qaq 改对过了美滋滋，然而elijahqi巨佬告诉我你太naive了…你这样rev之后hash值根本不对…囧 然而过了，可能因为数据随机吧qaq，反正正解也是爆搜【逃】

#include using namespace std;#define ll long long#define inf 0x3f3f3f3f#define N 100010#define k1 11117#define ull unsigned long longinline char gc(){ static char buf[1<<16],*S,*T; if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}int n,fa[N],c[N][2],sz[N],v[N],q[N];ull hs[N],bin[N];ll ans=0;bool rev[N];vectora[N];inline void update(int p){ int l=c[p][0],r=c[p][1]; sz[p]=sz[l]+sz[r]+1; hs[p]=hs[l]*bin[sz[r]+1]+v[p]*bin[sz[r]]+hs[r];}inline void dorev(int x){ if(!x) return;rev[x]^=1;swap(c[x][0],c[x][1]);update(x);}inline bool isroot(int x){ return x!=c[fa[x]][0]&&x!=c[fa[x]][1];}inline void pushdown(int p){ if(!rev[p]) return;rev[p]=0; dorev(c[p][0]);dorev(c[p][1]);}inline void rotate(int x){ int y=fa[x],z=fa[y],l=x==c[y][1],r=l^1; if(!isroot(y)) c[z][y==c[z][1]]=x; fa[c[x][r]]=y;fa[y]=x;fa[x]=z; c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);}inline void splay(int x){ int top=0;q[++top]=x; for(int xx=x;!isroot(xx);xx=fa[xx]) q[++top]=fa[xx]; while(top) pushdown(q[top--]); while(!isroot(x)){ int y=fa[x],z=fa[y]; if(!isroot(y)){ if(x==c[y][1]^y==c[z][1]) rotate(x); else rotate(y); }rotate(x); }}inline void access(int x){ int y=0;while(x){splay(x);c[x][1]=y;update(x);y=x;x=fa[x];}}inline void makeroot(int x){ access(x);splay(x);dorev(x);}inline void link(int x,int y){ makeroot(x);fa[x]=y;}inline ull cal(int x,int y){ makeroot(x);access(y);splay(y);return hs[y];}int main(){ //freopen("h.in","r",stdin); int tst=read(); while(tst--){ n=read();ans=n;memset(fa,0,sizeof(fa));memset(c,0,sizeof(c));bin[0]=1; memset(rev,0,sizeof(rev));memset(hs,0,sizeof(hs));memset(sz,0,sizeof(sz)); for(int i=1;i<=n;++i) v[i]=read(),a[v[i]].push_back(i),bin[i]=bin[i-1]*k1; for(int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。