Gym - 101908H Police Hypothesis (树链剖分/LCT+字符串哈希)

题意：有一棵树，树上每个结点上有一个字母，有两种操作：

1）询问树上两点u,v间有向路径上有多少个字母和某个固定的字符串相匹配

2）将结点u的字母修改为x

树剖+线段，暴力维护前缀和后缀哈希值（正反都要维护）以及区间内匹配的个数，合并两区间时判断一下跨过分界点的情况就行了。由于被匹配的字符串长度不超过100，所以最多只需维护长度为100的前缀/后缀。

但即使这样复杂度也足足有$O(100nlog^2n)$啊，这常数是得有多小才能过掉...

注意各种条件判断和细节处理，还有就是这题内存比较吃紧，使用动态开点可以节省一半的内存。

 #include<bits/stdc++.h>

 using namespace std;

 typedef unsigned long long ll;

 const int N=1e5+,M=;

 int hd[N],n,ne,m,Len,fa[N],son[N],siz[N],dep[N],top[N],dfn[N],rnk[N],tot,rt,ls[N<<],rs[N<<],tot2;

 ll H,pm[N];

 char s1[N],s2[N];

 struct D {

     int len,sum;

     ll L[],R[];

     D(int ch=) {

         len=;

         sum=(Len==&&ch==H);

         L[]=R[]=ch;

     }

 } tr[N<<][];

 struct E {int v,nxt;} e[N<<];

 D operator+(const D& a,const D& b) {

     if(a.L[]==)return b;

     if(b.L[]==)return a;

     D c;

     c.len=a.len+b.len;

     c.sum=a.sum+b.sum;

     for(int i=; i<=min(,c.len); ++i) {

         if(i<=a.len)c.L[i]=a.L[i];

         else c.L[i]=a.L[a.len]*pm[i-a.len]+b.L[i-a.len];

         if(i<=b.len)c.R[i]=b.R[i];

         else c.R[i]=a.R[i-b.len]*pm[b.len]+b.R[b.len];

     }

     for(int i=max(,Len-b.len); i<=a.len&&i<=Len-; ++i)if(a.R[i]*pm[Len-i]+b.L[Len-i]==H)c.sum++;

     return c;

 }

 void addedge(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}

 void dfs1(int u,int f,int d) {

     fa[u]=f,son[u]=,siz[u]=,dep[u]=d;

     for(int i=hd[u]; ~i; i=e[i].nxt) {

         int v=e[i].v;

         if(v==fa[u])continue;

         dfs1(v,u,d+),siz[u]+=siz[v];

         if(siz[v]>siz[son[u]])son[u]=v;

     }

 }

 void dfs2(int u,int tp) {

     top[u]=tp,dfn[u]=++tot,rnk[dfn[u]]=u;

     if(son[u])dfs2(son[u],top[u]);

     for(int i=hd[u]; ~i; i=e[i].nxt) {

         int v=e[i].v;

         if(v==fa[u]||v==son[u])continue;

         dfs2(v,v);

     }

 }

 #define mid ((l+r)>>1)

 void pu(int u) {

     tr[u][]=tr[ls[u]][]+tr[rs[u]][];

     tr[u][]=tr[rs[u]][]+tr[ls[u]][];

 }

 void upd(int p,int x,int& u=rt,int l=,int r=tot) {

     if(l==r) {tr[u][]=tr[u][]=D(x); return;}

     p<=mid?upd(p,x,ls[u],l,mid):upd(p,x,rs[u],mid+,r);

     pu(u);

 }

 void build(int& u=rt,int l=,int r=tot) {

     u=++tot2;

     if(l==r) {tr[u][]=tr[u][]=D(s2[rnk[l]-]); return;}

     build(ls[u],l,mid),build(rs[u],mid+,r),pu(u);

 }

 D qry(int L,int R,int f,int u=rt,int l=,int r=tot) {

     if(l>=L&&r<=R)return tr[u][f];

     if(l>R||r<L)return D();

     if(f==)return qry(L,R,f,ls[u],l,mid)+qry(L,R,f,rs[u],mid+,r);

     else return qry(L,R,f,rs[u],mid+,r)+qry(L,R,f,ls[u],l,mid);

 }

 int qry2(int u,int v) {

     D L=D(),R=D(),M;

     for(; top[u]!=top[v];) {

         if(dep[top[u]]>dep[top[v]])L=L+qry(dfn[top[u]],dfn[u],),u=fa[top[u]];

         else R=qry(dfn[top[v]],dfn[v],)+R,v=fa[top[v]];

     }

     if(dep[u]>dep[v])M=qry(dfn[v],dfn[u],);

     else M=qry(dfn[u],dfn[v],);

     return (L+M+R).sum;

 }

 int main() {

     pm[]=;

     for(int i=; i<N; ++i)pm[i]=pm[i-]*M;

     memset(hd,-,sizeof hd),ne=;

     scanf("%d%d",&n,&m);

     scanf("%s%s",s1,s2),Len=strlen(s1);

     H=;

     for(int i=; i<Len; ++i)H=H*M+s1[i];

     for(int i=; i<n; ++i) {

         int u,v;

         scanf("%d%d",&u,&v);

         addedge(u,v);

         addedge(v,u);

     }

     dfs1(,,),dfs2(,);

     build(rt);

     while(m--) {

         int f,u,v;

         char ch;

         scanf("%d",&f);

         if(f==)scanf("%d%d",&u,&v),printf("%d\n",qry2(u,v));

         else scanf("%d %c",&u,&ch),upd(dfn[u],ch);

     }

     return ;

 }

当然还有$O(100nlogn)$的LCT毒瘤做法，代码比树剖短，需要特判的地方少，而且更省内存，但是常数巨大，需要优化下常数才能过，比如改个引用传递什么的。

 #include<bits/stdc++.h>

 using namespace std;

 typedef unsigned long long ll;

 const int N=1e5+,M=;

 int n,m,a[N],fa[N],ch[N][],flp[N],sta[N],tp,Len;

 ll H,pm[N];

 char s1[N],s2[N];

 struct D {

     int len,sum;

     ll L[],R[];

     D(int ch=) {

         len=;

         sum=(Len==&&ch==H);

         L[]=R[]=ch;

     }

 } tr[N][];

 D operator+(const D& a,const D& b) {

     if(a.L[]==)return b;

     if(b.L[]==)return a;

     D c;

     c.len=a.len+b.len;

     c.sum=a.sum+b.sum;

     for(int i=; i<=min(,c.len); ++i) {

         if(i<=a.len)c.L[i]=a.L[i];

         else c.L[i]=a.L[a.len]*pm[i-a.len]+b.L[i-a.len];

         if(i<=b.len)c.R[i]=b.R[i];

         else c.R[i]=a.R[i-b.len]*pm[b.len]+b.R[b.len];

     }

     for(int i=max(,Len-b.len); i<=a.len&&i<=Len-; ++i)if(a.R[i]*pm[Len-i]+b.L[Len-i]==H)c.sum++;

     return c;

 }

 #define l(u) ch[u][0]

 #define r(u) ch[u][1]

 void rev(int u) {flp[u]^=,swap(l(u),r(u)),swap(tr[u][],tr[u][]);}

 void pu(int u) {

     tr[u][]=tr[l(u)][]+D(s2[u])+tr[r(u)][];

     tr[u][]=tr[r(u)][]+D(s2[u])+tr[l(u)][];

 }

 void pd(int u) {if(flp[u])rev(l(u)),rev(r(u)),flp[u]=;}

 int sf(int u) {return u==r(fa[u]);}

 bool isrt(int u) {return u!=l(fa[u])&&u!=r(fa[u]);}

 void rot(int u) {

     int v=fa[u],f=sf(u);

     if(!isrt(v))ch[fa[v]][sf(v)]=u;

     ch[v][f]=ch[u][f^],fa[ch[v][f]]=v;

     fa[u]=fa[v],ch[u][f^]=v,fa[v]=u,pu(v);

 }

 void splay(int u) {

     sta[tp=]=u;

     for(int v=u; !isrt(v); v=fa[v])sta[++tp]=fa[v];

     for(; ~tp; pd(sta[tp--]));

     for(; !isrt(u); rot(u))if(!isrt(fa[u])&&sf(fa[u])==sf(u))rot(fa[u]);

     pu(u);

 }

 void access(int u) {for(int v=; u; splay(u),r(u)=v,pu(u),u=fa[v=u]);}

 void makert(int u) {access(u),splay(u),rev(u);}

 void link(int u,int v) {makert(u),fa[u]=v;}

 void join(int u,int v) {makert(u),access(v),splay(v);}

 void upd(int u,int ch) {splay(u),s2[u]=ch;}

 int qry(int u,int v) {join(u,v); return tr[v][].sum;}

 int main() {

     pm[]=;

     for(int i=; i<N; ++i)pm[i]=pm[i-]*M;

     scanf("%d%d",&n,&m);

     scanf("%s%s",s1,s2+),Len=strlen(s1);

     H=;

     for(int i=; i<Len; ++i)H=H*M+s1[i];

     for(int i=; i<n; ++i) {

         int u,v;

         scanf("%d%d",&u,&v);

         link(u,v);

     }

     while(m--) {

         int f,u,v;

         char ch;

         scanf("%d",&f);

         if(f==)scanf("%d%d",&u,&v),printf("%d\n",qry(u,v));

         else scanf("%d %c",&u,&ch),upd(u,ch);

     }

     return ;

 }

巴特西

Gym - 101908H Police Hypothesis (树链剖分/LCT+字符串哈希)

最新文章

热门文章