题解：
树套树
treap+线段树
treap就把线段树上的节点弄一下
然后修改的时候
把中间的一段一起加
把两头重新计算（二分+hash）
代码：
#include<bits/stdc++.h> using namespace std; typedef unsigned int U; const int N=600005; int n,m,x,len,cur,st[N],en[N],q[N][3],stq[N]; int pre[N],y[N],h[N],T[N],tag[N],enq[N]; U po[N]; char op[9],s[N],pool[N],str[N]; namespace DS { const int N=15000005; int tot,l[N],r[N],v[N]; U f[N]; void up(int x) { v[x]=v[l[x]]+v[r[x]]; f[x]=f[l[x]]*po[v[r[x]]]+f[r[x]]; } int build(int a,int b,int c,int d) { int x=++tot; if (a==b) { v[x]=1; f[x]=str[a]; return x; } int mid=(a+b)/2; if (c<=mid)l[x]=build(a,mid,c,d); if (d>mid)r[x]=build(mid+1,b,c,d); up(x); return x; } int merge(int x,int y,int a,int b) { if (!x||!y)return x+y; int z=++tot,mid=(a+b)/2; l[z]=merge(l[x],l[y],a,mid); r[z]=merge(r[x],r[y],mid+1,b); up(z); return z; } U hash(int x,int k) { int a=1,b=cur,mid,t; U h=0; while (a<b) { mid=(a+b)/2; t=v[l[x]]; if (k<=t) { b=mid; x=l[x]; } else { h=h*po[t]+f[l[x]]; k-=t; a=mid+1; x=r[x]; } } return h*po[v[x]]+f[x]; } } void ins(int x,int p) { pre[x]=DS::merge(pre[x],p,1,cur); } void down(int x) { if (pre[x]) { ins(x<<1,pre[x]); ins(x<<1|1,pre[x]); pre[x]=0; } } void push(int x,int a,int b,int c,int d,int p) { if (c<=a&&b<=d) { ins(x,p); return; } down(x); int mid=(a+b)/2; if (c<=mid)push(x<<1,a,mid,c,d,p); if (d>mid)push(x<<1|1,mid+1,b,c,d,p); } void root(int x,int a,int b,int c) { if (a==b) { T[a]=DS::merge(T[a],pre[x],1,cur); pre[x]=0; return; } down(x); int mid=(a+b)/2; if (c<=mid)root(x<<1,a,mid,c); else root(x<<1|1,mid+1,b,c); } int lcp(int x,int y) { root(1,1,n,x); root(1,1,n,y); x=T[x];y=T[y]; int l=1,r=min(DS::v[x],DS::v[y]),t=0; while (l<=r) { int mid=(l+r)/2; if (DS::hash(x,mid)==DS::hash(y,mid))l=(t=mid)+1; else r=mid-1; } return t; } void tag1(int x,int p) { h[x]+=p; tag[x]+=p; } void pb(int x) { if (tag[x]) { tag1(x<<1,tag[x]); tag1(x<<1|1,tag[x]); tag[x]=0; } } void up(int x) { h[x]=min(h[x<<1],h[x<<1|1]); } void build(int x,int a,int b) { if (a==b) { h[x]=lcp(a,a+1); return; } int mid=(a+b)/2; build(x<<1,a,mid); build(x<<1|1,mid+1,b); up(x); } void cal(int x,int a,int b,int c) { if (a==b) { h[x]=lcp(a,a+1); return; } pb(x); int mid=(a+b)/2; if (c<=mid)cal(x<<1,a,mid,c); else cal(x<<1|1,mid+1,b,c); up(x); } void change(int x,int a,int b,int c,int d,int p) { if (c<=a&&b<=d) { tag1(x,p); return; } pb(x); int mid=(a+b)/2; if (c<=mid)change(x<<1,a,mid,c,d,p); if (d>mid)change(x<<1|1,mid+1,b,c,d,p); up(x); } int ask(int x,int a,int b,int c,int d) { if (c<=a&&b<=d)return h[x]; pb(x); int mid=(a+b)/2,t=N; if (c<=mid)t=ask(x<<1,a,mid,c,d); if (d>mid)t=min(t,ask(x<<1|1,mid+1,b,c,d)); return t; } void makepush(int l,int r,int A,int B) { push(1,1,n,l,r,DS::build(1,cur,A,B)); if (l<r)change(1,1,n-1,l,r-1,B-A+1); if (l>1)cal(1,1,n-1,l-1); if (r<n)cal(1,1,n-1,r); } int query(int l,int r) { if (l==r)return lcp(l,l); return ask(1,1,n-1,l,r-1); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%s",s); len=strlen(s); st[i]=cur+1; for (int j=0;j<len;j++)pool[++cur]=s[j]; en[i]=cur; } for (int i=1;i<=m;i++) { scanf("%s%d%d",op,&q[i][1],&q[i][2]); if (op[0]=='Q')q[i][0]=1; else { scanf("%s",s); len=strlen(s); stq[i]=cur+1; for (int j=0;j<len;j++)pool[++cur]=s[j]; enq[i]=cur; } } int cur=0; for (int i=m;i;i--) if (!q[i][0]) { x=cur+1; for (int j=stq[i];j<=enq[i];j++)str[++cur]=pool[j]; stq[i]=x; enq[i]=cur; } for (int i=1;i<=n;i++) { x=cur+1; for (int j=st[i];j<=en[i];j++)str[++cur]=pool[j]; st[i]=x;en[i]=cur; } po[0]=1; for (int i=1;i<=cur;i++)po[i]=po[i-1]*233; for (int i=1;i<=n;i++)T[i]=DS::build(1,cur,st[i],en[i]); build(1,1,n-1); for (int i=1;i<=m;i++) if (q[i][0])printf("%d ",query(q[i][1],q[i][2])); else makepush(q[i][1],q[i][2],stq[i],enq[i]); }