题目概述Cmostp解题报告建出SAM，考虑离线，每次添加一个前缀节点 $p_i$ 的时候，就是把 $p_i$ 到 $fail$ 树根路径上的节点的最右终止端点改为 $i$ 。查询 $[L,R]$ 时，只要当前最右终止端点在 $[L,R]$ 范围内的节点都可以计入答案，节点 $x$ 产生的贡献为 $MAX_x-MAX_{fail_x}$ 。考虑如何维护最右终止端点。我们可以利用LCT，每次 $p_i$ 往上更新其实就是Access操作，每次更新的均摊复杂度是 $O(\log_2n)$ 的。然后利用树状数组查询最右终止端点在 $[L,R]$ 范围内的节点贡献之和。复杂度是 $O(n\log^2_2n+q\log_2n)$ ，但其实只有Access的LCT+树状数组跑得飞快。示例程序#include<cstdio> #include<cctype> #include<algorithm> #define fr first #define sc second #define mp make_pair using namespace std; typedef long long LL; const int maxn=500000,maxt=maxn<<1,maxi=26; int n,Q,ID[maxn+5];char s[maxn+5]; int pl,ro,fai[maxt+5],son[maxt+5][maxi],MAX[maxt+5],val[maxt+5]; int fa[maxt+5],to[maxt+5][2],pos[maxt+5],tag[maxt+5];LL sum[maxt+5]; pair<pair<int,int>,int> q[maxn+5]; LL ans[maxn+5],c[maxn+5]; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } int reads(char *s){ int len=0;char ch=readc(); while (!islower(ch)) {if (ch==EOF) return EOF;ch=readc();} while (islower(ch)) s[++len]=ch,ch=readc(); s[len+1]=0;return len; } struct fastO{ int si;char buf[100000]; fastO() {si=0;} void putc(char ch){ if (si==100000) fwrite(buf,1,si,stdout),si=0; buf[si++]=ch; } ~fastO() {fwrite(buf,1,si,stdout);} }fo; template<typename T> void writei(T x,char ch='\n'){ int len=0,buf[100]; if (x<0) fo.putc('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) fo.putc(buf[--len]+48); if (ch) fo.putc(ch); } inline int newnode() {pl++;return pl;} int Extend(int p,int c,int id){ int np=newnode();MAX[np]=MAX[p]+1;ID[id]=np; while (p && !son[p][c]) son[p][c]=np,p=fai[p]; if (!p) {fai[np]=ro;return np;} int q=son[p][c];if (MAX[p]+1==MAX[q]) {fai[np]=q;return np;} int nq=newnode();MAX[nq]=MAX[p]+1; for (int i=0;i<maxi;i++) son[nq][i]=son[q][i]; fai[nq]=fai[q];fai[q]=fai[np]=nq; while (p && son[p][c]==q) son[p][c]=nq,p=fai[p]; return np; } #define is_ro(p) (to[fa[p]][0]!=(p) && to[fa[p]][1]!=(p)) #define Son(p) ((p)==to[fa[p]][1]) inline void Pushup(int p) {sum[p]=sum[to[p][0]]+val[p]+sum[to[p][1]];} void Rotate(int t){ int p=fa[t],d=Son(t);to[p][d]=to[t][d^1];to[t][d^1]=p; if (!is_ro(p)) to[fa[p]][Son(p)]=t;Pushup(p);Pushup(t); if (to[p][d]) fa[to[p][d]]=p;fa[t]=fa[p];fa[p]=t; } inline void Addtag(int p,int k) {tag[p]=k;pos[p]=k;} void Pushdown(int p) {if (tag[p]) Addtag(to[p][0],tag[p]),Addtag(to[p][1],tag[p]),tag[p]=0;} void Splay(int p){ static int top,stk[maxn+5];stk[top=1]=p; for (int i=p;!is_ro(i);i=fa[i]) stk[++top]=fa[i]; while (top) Pushdown(stk[top--]); for (int pre=fa[p];!is_ro(p);Rotate(p),pre=fa[p]) if (!is_ro(pre)) Rotate(Son(p)==Son(pre)?pre:p); } void Add(int x,LL y) {for (;x<=n;x+=x&-x) c[x]+=y;} LL Sum(int x) {int sum=0;for (;x;x-=x&-x) sum+=c[x];return sum;} void Merge(int p,int j){ for (int lst=0;p;lst=p,p=fa[p]){ Splay(p); if (pos[p]) Add(pos[p],-sum[to[p][0]]-val[p]); pos[p]=j;Addtag(to[p][0],j); Add(j,sum[to[p][0]]+val[p]); to[p][1]=lst;Pushup(p); } } int main(){ readi(n);readi(Q);reads(s); ro=newnode(); for (int i=1,p=ro;i<=n;i++) p=Extend(p,s[i]-'a',i); for (int i=2;i<=pl;i++) fa[i]=fai[i],val[i]=sum[i]=MAX[i]-MAX[fai[i]]; for (int i=1;i<=Q;i++) readi(q[i].fr.sc),readi(q[i].fr.fr),q[i].sc=i; sort(q+1,q+1+Q); for (int i=1,j=1;i<=Q;i++){ int L=q[i].fr.sc,R=q[i].fr.fr; while (j<=n && j<=R) Merge(ID[j],j),j++; ans[q[i].sc]=Sum(R)-Sum(L-1); } for (int i=1;i<=Q;i++) writei(ans[i]); return 0; }
[离线+可持久化树+线段树分治+并查集按秩合并+哈希]2022牛客暑期多校训练营8 I【Equivalence in Connectivity】题解
题目概述Equivalence in Connectivity解题报告好像确实有维护动态图的方法……但是可能是考场上写不出的那种……考虑离线，建出可持久化树，如果用并查集维护图的连通性，会发现不能维护删边，因此我们考虑如何只进行加边操作和撤销。可持久化树中，如果在 $t$ 点加入了 $(x,y)$ 边，我们可以认为 $(x,y)$ 在 $t$ 的DFS序 $[in_t,out_t]$ 都出现了，而如果 $t$ 点是删边，则认为是把 $[in_t,out_t]$ 中的 $(x,y)$ 边删掉。因此实际上对于每条边，都可以拆成若干个连续的区间，表示含有这条边的区间。这样我们只需要利用线段树分治就可以实现只加边和撤销而不删边。考虑如何维护区间，首先先给每条边都标号，记录 $last_i$ 表示 $i$ 边当前处理到的DFS序。做DFS，处理到 $t$ 点时，假设边的标号为 $i$ ：加边：入栈时，将 $last_i$ 更新为 $in_t$ 。出栈时，说明 $last_i$ 到 $out_t$ 都含有 $i$ 边，加入线段树中。删边：入栈时，说明 $last_i$ 到 $in_t-1$ 都含有 $i$ 边，加入线段树中。出栈时，将 $last_i$ 更新为 $out_t+1$ 。由于保证了加边和删边都合法且不重复，因此入栈和出栈时就可以确定区间。而刚开始给的边可以认为是刚进入DFS时的加边操作。最后考虑如何比较两张图的连通性，可以使用这样的哈希：给每个点都随机一个权值，然后对于每个连通块 $i$ ，权值为 $sum_i\cdot MIN_i$ ，$sum_i$ 表示 $i$ 连通块所有点权值的异或，$MIN_i$ 表示 $i$ 连通块的最小值。一张图的权值为所有连通块权值的加和。示例程序#include #include<vector> #include<random> #include<cstdio> #include<cctype> #include<algorithm> #define fr first #define sc second #define mp make_pair using namespace std; typedef unsigned long long ULL; const int maxn=100000,maxm=200000,maxt=maxn<<2,maxp=5e6,BA=999917; int te,K,n,m,X[maxn+5],Y[maxn+5]; mt19937_64 mrand(164984); ULL ha[maxn+5]; int cnt;map<pair<int,int>,int> f; int E,lnk[maxn+5],nxt[maxn+5],to[maxn+5]; struct Data {int x,y,fl;} q[maxn+5]; int lt[maxn+5],rt[maxn+5],who[maxn+5]; int lst[maxm+5]; vector< pair<int,int> > e[maxt+5]; ULL fat[maxn+5],rk[maxn+5],sum[maxn+5],MIN[maxn+5],HA; int top;pair<ULL*,ULL> stk[maxp+5]; int ID[maxn+5]; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } struct fastO{ int si;char buf[100000]; fastO() {si=0;} void putc(char ch){ if (si==100000) fwrite(buf,1,si,stdout),si=0; buf[si++]=ch; } ~fastO() {fwrite(buf,1,si,stdout);} }fo; template<typename T> void writei(T x,char ch='\n'){ int len=0,buf[100]; if (x<0) fo.putc('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) fo.putc(buf[--len]+48); if (ch) fo.putc(ch); } inline void Add(int x,int y) {to[++E]=y;nxt[E]=lnk[x];lnk[x]=E;} void Build(int L,int R,int p=1){ e[p].clear(); if (L==R) return; int mid=L+(R-L>>1); Build(L,mid,p<<1);Build(mid+1,R,p<<1|1); } void Insert(int L,int R,pair<int,int> k,int l=1,int r=K,int p=1){ if (L==l && r==R) {e[p].push_back(k);return;} int mid=l+(r-l>>1); if (R<=mid) Insert(L,R,k,l,mid,p<<1); else if (L>mid) Insert(L,R,k,mid+1,r,p<<1|1); else Insert(L,mid,k,l,mid,p<<1),Insert(mid+1,R,k,mid+1,r,p<<1|1); } void DFS(int x){ lt[x]=++lt[0];who[lt[0]]=x; if (x>1){ int id=f[mp(q[x].x,q[x].y)]; if (q[x].fl) lst[id]=lt[x]; else if (lst[id]<lt[x]) Insert(lst[id],lt[x]-1,mp(q[x].x,q[x].y)); } for (int j=lnk[x];j;j=nxt[j]) DFS(to[j]); rt[x]=lt[0]; if (x>1){ int id=f[mp(q[x].x,q[x].y)]; if (q[x].fl && lst[id]<=rt[x]) Insert(lst[id],rt[x],mp(q[x].x,q[x].y)); lst[id]=rt[x]+1; } } void Change(ULL *x,ULL y) {stk[++top]=mp(x,*x);*x=y;} int getfa(int x) {return x==fat[x]?x:getfa(fat[x]);} void Solve(int L,int R,int p=1){ int lst=top; for (auto x:e[p]){ int X=getfa(x.fr),Y=getfa(x.sc); if (X==Y) continue; if (rk[X]<rk[Y]) swap(X,Y); ULL now=HA; now-=MIN[Y]*sum[Y]; now-=MIN[X]*sum[X]; Change(&MIN[X],min(MIN[X],MIN[Y])); Change(&sum[X],sum[X]^sum[Y]); now+=MIN[X]*sum[X]; Change(&fat[Y],X); if (rk[X]==rk[Y]) Change(&rk[X],rk[X]+1); Change(&HA,now); } if (L==R){ ha[who[L]]=HA; while (top!=lst) *stk[top].fr=stk[top].sc,top--; return; } int mid=L+(R-L>>1); Solve(L,mid,p<<1);Solve(mid+1,R,p<<1|1); while (top!=lst) *stk[top].fr=stk[top].sc,top--; } inline bool cmp(const int &i,const int &j) {return ha[i]<ha[j];} int main(){ for (readi(te);te;te--){ readi(K);readi(n);readi(m); cnt=0;f.clear(); for (int i=1;i<=m;i++){ readi(X[i]);readi(Y[i]); f[mp(X[i],Y[i])]=++cnt; } E=0;for (int i=1;i<=K;i++) lnk[i]=0; for (int i=2;i<=K;i++){ int fa;readi(fa); char ch=readc();while (!islower(ch)) ch=readc(); int x,y;readi(x);readi(y); if (!f.count(mp(x,y))) f[mp(x,y)]=++cnt; Add(fa,i);q[i]=(Data){x,y,ch=='a'}; } for (int i=1;i<=m;i++) lst[i]=1; Build(1,K);lt[0]=0;DFS(1); for (int i=1;i<=m;i++) if (lst[i]<=K) Insert(lst[i],K,mp(X[i],Y[i])); HA=0; for (int i=1;i<=n;i++) fat[i]=i,rk[i]=0,sum[i]=mrand(),MIN[i]=i,HA+=sum[i]*i; Solve(1,K); for (int i=1;i<=K;i++) ID[i]=i; sort(ID+1,ID+1+K,cmp); int tot=0; for (int i=1,j;i<=K;i=j){ for (j=i+1;j<=K && ha[ID[i]]==ha[ID[j]];j++); tot++; } writei(tot); for (int i=1,j;i<=K;i=j){ for (j=i+1;j<=K && ha[ID[i]]==ha[ID[j]];j++); writei(j-i,0); for (int k=i;k<j;k++) fo.putc(' '),writei(ID[k],0); fo.putc('\n'); } } return 0; }