（upd：字符串问题AC）
（upd：字符串问题写了80分）
太菜了做不到满分啊……以后再看吧。
异或粽子：
正常人都是可持久化Trie一眼秒（我是弱智）
#include<iostream> #include<cstdio> #include<queue> using namespace std; typedef long long i64; const int N=7e5+5; const int D=64; const int S=N*D; int cnt,c[S][2],z[S]; i64 a[N],s[N]; int f[N]; struct inf{ i64 s; int x; bool operator<(const inf a)const{ return s<a.s; } }; priority_queue<inf>q; int ins(i64 x,int v){ int r,u,i; i64 t; r=u=++cnt; z[u]=z[v]+1; for(i=D-1;i>=0;i--){ t=(x>>i)&1; c[u][t^1]=c[v][t^1]; ++cnt; c[u][t]=cnt; u=cnt; v=c[v][t]; z[u]=z[v]+1; } return r; } int dlt(i64 x,int v){ int r,u,i; i64 t; if(z[v]==1)return 0; r=u=++cnt; z[u]=z[v]-1; for(i=D-1;i>=0;i--){ t=(x>>i)&1; c[u][t^1]=c[v][t^1]; if(z[c[v][t]]==1) break; ++cnt; c[u][t]=cnt; u=cnt; v=c[v][t]; z[u]=z[v]-1; } return r; } i64 slv(i64 x,int v){ i64 s=0,t; int i; for(i=D-1;i>=0;i--){ t=((x>>i)&1)^1; if(c[v][t]){ s+=t<<i; v=c[v][t]; } else{ s+=(t^1)<<i; v=c[v][t^1]; } } return s; } int main() { int n,m,i,v; scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ scanf("%lld",&a[i]); a[i]=a[i]^a[i-1]; f[i]=ins(a[i-1],f[i-1]); s[i]=slv(a[i],f[i]); q.push((inf){a[i]^s[i],i}); } i64 ans=0; for(i=1;i<=m;i++){ v=q.top().x; ans+=a[v]^s[v]; q.pop(); f[v]=dlt(s[v],f[v]); if(f[v]){ s[v]=slv(a[v],f[v]); q.push((inf){a[v]^s[v],v}); } } printf("%lld",ans); return 0; }
字符串问题：
SA+树套树区间连边，内层树可以用后缀代替。
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; typedef long long i64; const int N=2e5+5; const int D=20; const int S=7e6+6; const int M=2e7+7; char s[N]; int t1[N],t2[N],c[S]; int sa[N],rk[N],ht[N]; int lg2[N]; int gr[N][D]; void gtsa(int n,int m){ int *x=t1,*y=t2; int i,j,p=0; for(i=0;i<=m;i++) c[i]=0; for(i=1;i<=n;i++) ++c[x[i]=s[i]]; for(i=1;i<=m;i++) c[i]+=c[i-1]; for(i=n;i;i--) sa[c[x[i]]--]=i; for(j=1;j<=n&&p<n;j<<=1){ p=0; for(i=n-j+1;i<=n;i++) y[++p]=i; for(i=1;i<=n;i++) if(sa[i]>j) y[++p]=sa[i]-j; for(i=0;i<=m;i++) c[i]=0; for(i=1;i<=n;i++) ++c[x[y[i]]]; for(i=1;i<=m;i++) c[i]+=c[i-1]; for(i=n;i;i--) sa[c[x[y[i]]]--]=y[i]; swap(x,y); x[sa[1]]=1; p=1; for(i=2;i<=n;i++) x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j]?p:++p; m=p; } for(i=1;i<=n;i++) rk[sa[i]]=i; p=0; for(i=1;i<=n;i++){ j=sa[rk[i]-1]; if(p)--p; while(s[i+p]==s[j+p]) ++p; ht[rk[i]]=p; } memset(gr,0,sizeof(gr)); for(i=1;i<=n;i++) gr[i][0]=ht[i]; for(j=1;j<=lg2[n];j++) for(i=1;i+(1<<j)-1<=n;i++) gr[i][j]=min(gr[i][j-1],gr[i+(1<<j-1)][j-1]); } i64 f[S]; int w[S]; int l[S],e[M],x[M]; int cnt,ecnt; void pshe(int u,int v){ ++ecnt;x[ecnt]=l[u];l[u]=ecnt;e[ecnt]=v; } i64 clc(int v){ if(c[v]==2)return f[v]; c[v]=1; f[v]=0; for(int i=l[v];i;i=x[i]){ if(c[e[i]]==1){ f[v]=-1; c[v]=2; return f[v]; } else{ if(clc(e[i])==-1){ f[v]=-1; return f[v]; } f[v]=max(f[v],clc(e[i])); } } c[v]=2; f[v]+=w[v]; return f[v]; } struct dst{ int p,h,l; }a[N],b[N]; int in[S][2],cd[S][2],ocnt,st[S]; vector<int>dt[S]; bool cmp(dst a,dst b){ return a.p<b.p||a.p==b.p&&a.h<b.h; } int bld(int l,int r,int bg,int ed){ int mid=(l+r)>>1,v=++ocnt; in[v][0]=l; in[v][1]=r; cd[v][0]=cd[v][1]=0; int x,i,j,p; if(l<r){ for(x=bg;x<=ed;x++) if(a[x].p>mid)break; cd[v][0]=bld(l,mid,bg,x-1); cd[v][1]=bld(mid+1,r,x,ed); for(p=bg,i=bg,j=x;i<x||j<=ed;p++) if(j>ed||i<x&&a[i].h<=a[j].h) b[p]=a[i++]; else b[p]=a[j++]; for(i=bg;i<=ed;i++) a[i]=b[i]; } st[v]=cnt+1; vector<int>().swap(dt[v]); dt[v].resize(ed-bg+1); for(i=bg;i<=ed;i++){ ++cnt; dt[v][i-bg]=a[i].h; pshe(cnt,t1[a[i].l]); if(i<ed)pshe(cnt,cnt+1); } return v; } int bnsr(int h,int v){ int l=0,r=dt[v].size()-1,mid; while(l<=r){ mid=(l+r)>>1; if(dt[v][mid]>=h) r=mid-1; else l=mid+1; } return l; } void addsgm(int d,int h,int v){ int x=bnsr(h,v); if(x<dt[v].size()) pshe(d,st[v]+x); } void lksgm(int d,int h,int v,int l,int r){ if(l<=in[v][0]&&in[v][1]<=r){ addsgm(d,h,v); return; } if(l<=in[cd[v][0]][1]) lksgm(d,h,cd[v][0],l,r); if(in[cd[v][1]][0]<=r) lksgm(d,h,cd[v][1],l,r); } int gtmn(int l,int r){ return min(gr[l][lg2[r-l]],gr[r-(1<<lg2[r-l])+1][lg2[r-l]]); } int n,na,nb; int bnsrl(int p,int h){ int l=1,r=p,mid; while(l<=r){ mid=(l+r)>>1; if(gtmn(mid,p)>=h) r=mid-1; else l=mid+1; } return l-1; } int bnsrr(int p,int h){ int l=p+1,r=n,mid; while(l<=r){ mid=(l+r)>>1; if(gtmn(p+1,mid)>=h) l=mid+1; else r=mid-1; } return r; } void cpt(){ scanf("%s",s+1); n=strlen(s+1); gtsa(n,127); cnt=ocnt=ecnt=0; memset(l,0,sizeof(l)); memset(w,0,sizeof(w)); int i,la,ra,lb,rb,m,u,v; scanf("%d",&na); for(i=1;i<=na;i++){ scanf("%d%d",&la,&ra); a[i].p=rk[la]; a[i].h=ra-la+1; a[i].l=i; t1[i]=++cnt; w[t1[i]]=a[i].h; } sort(a+1,a+na+1,cmp); int rt=bld(1,n,1,na); scanf("%d",&nb); for(i=1;i<=nb;i++){ scanf("%d%d",&lb,&rb); b[i].p=rk[lb]; b[i].h=rb-lb+1; t2[i]=++cnt; la=bnsrl(b[i].p,b[i].h); ra=bnsrr(b[i].p,b[i].h); lksgm(t2[i],b[i].h,rt,la,ra); } scanf("%d",&m); for(i=1;i<=m;i++){ scanf("%d%d",&u,&v); pshe(t1[u],t2[v]); } memset(c,0,sizeof(c)); memset(f,0,sizeof(f)); i64 ans=0; for(i=1;i<=na;i++){ if(clc(t1[i])==-1){ ans=-1; break; } ans=max(ans,clc(t1[i])); } printf("%lld ",ans); } int main() { int T,i; scanf("%d",&T); for(i=2;i<N;i++) lg2[i]=lg2[i>>1]+1; while(T--) cpt(); return 0; }
春节十二响（清明十二响）：
由一条链的部分分可以得到贪心做法，长链剖分即可。我用的斜堆。
#include<iostream> #include<cstdio> #include<vector> using namespace std; typedef long long i64; const int N=2e5+5; int c[N][2],a[N],s[N]; vector<int>e[N]; int unn(int u,int v){ if(!u)return v; if(!v)return u; if(a[u]<a[v])swap(u,v); c[u][1]=unn(c[u][1],v); s[u]+=s[v]; if(s[c[u][1]]>s[c[u][0]]) swap(c[u][0],c[u][1]); return u; } int mrg(int u,int v){ if(!u)return v; if(!v)return u; int r=0,p,q; while(u&&v){ p=u; u=unn(c[u][0],c[u][1]); c[p][0]=c[p][1]=0; s[p]=1; q=v; v=unn(c[v][0],c[v][1]); c[q][0]=c[q][1]=0; s[q]=1; if(a[p]<a[q])swap(p,q); r=unn(r,p); } if(u)r=unn(r,u); if(v)r=unn(r,v); return r; } int dfs(int v,int p){ int r=0,i,u; for(i=0;i<e[v].size();i++) if(e[v][i]!=p) r=mrg(r,dfs(e[v][i],v)); c[v][0]=c[v][1]=0; s[v]=1; r=unn(v,r); } i64 gtsz(int v){ if(!v)return 0; return (i64)a[v]+gtsz(c[v][0])+gtsz(c[v][1]); } int main() { int n,i,f; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=2;i<=n;i++){ scanf("%d",&f); e[f].push_back(i); } printf("%lld",gtsz(dfs(1,0))); return 0; }