专项测试-字符串1
T1 回文子串
特点是k很小
修改将区间分成三段，中间一段肯定全是同一个数，可以O(1)算，然后线段树区间修改
两端这两段总长度是O(k)级别的，暴力扫，线段树单点修改
询问区间也分成三段，中间一段区间查询
两端两段因为受区间限制，所以线段树上的答案和实际贡献不符，这个也单独暴扫计算
代码
#include
using namespace std;
const int N=1e5+11;
const int siz=500;
struct tree{
int l,r;
int sum,lazy;
}tre[4*N];
int sum,t;
char tx[N],blo[N];
int tmd[N],tmo[N];
int blg[N];
int n,k,q;
int ed1,ed2;
inline int min_(int x,int y){return x>y?y:x;}
inline int max_(int x,int y){return x>y?x:y;}
inline int read()
{
int s=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
inline char readc()
{
char ch=getchar();
while(ch>'z'||ch<'a') ch=getchar();
return ch;
}
void build(int i,int l,int r)
{
tre[i].l=l,tre[i].r=r;
if(l==r) return;
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
return;
}
inline void pushdowns(int i)
{
if(tre[i].l==tre[i].r) return;
tre[i<<1].lazy=tre[i<<1|1].lazy=tre[i].lazy;
tre[i<<1].sum=(tre[i<<1].r-tre[i<<1].l+1)*tre[i].lazy;
tre[i<<1|1].sum=(tre[i<<1|1].r-tre[i<<1|1].l+1)*tre[i].lazy;
tre[i].lazy=0;
return;
}
void insert(int i,int l,int r,int val)
{
if(tre[i].lazy) pushdowns(i);
if(tre[i].l>=l&&tre[i].r<=r) {tre[i].lazy=val;tre[i].sum=(tre[i].r-tre[i].l+1)*val;return;}
int mid=(tre[i].l+tre[i].r)>>1;
if(l<=mid) insert(i<<1,l,r,val);
if(r>mid) insert(i<<1|1,l,r,val);
tre[i].sum=tre[i<<1].sum+tre[i<<1|1].sum;
return;
}
int query(int i,int l,int r)
{
if(tre[i].lazy) pushdowns(i);
if(tre[i].l>=l&&tre[i].r<=r) return tre[i].sum;
int mid=(tre[i].l+tre[i].r)>>1;
int sum=0;
if(l<=mid) sum=query(i<<1,l,r);
if(r>mid) sum+=query(i<<1|1,l,r);
return sum;
}
inline char get_c(int x){return tmo[blg[x]]>tmd[x]?blo[blg[x]]:tx[x];}
int get_sum(int i,int l,int r)
{
int num1=0,num2=0;
while(num1l-1&&i+num1<=r&&get_c(i+num1)==get_c(i-num1)) ++num1;
while(num2l-1&&i+num2+1<=r&&get_c(i+num2+1)==get_c(i-num2)) ++num2;
return num1+num2;
}
void insertc(int l,int r,char c)
{
int bl=l/siz+1;
int br=r/siz+1;
if(bl==br) for(int i=l;i<=r;++i) tmd[i]=t,tx[i]=c;
else
{
for(int i=l;blg[i]==blg[l];++i) tmd[i]=t,tx[i]=c;
for(int i=r;blg[i]==blg[r];--i) tmd[i]=t,tx[i]=c;
for(int i=bl+1;i<=br-1;++i) tmo[i]=t,blo[i]=c;
}
return;
}
void chg(int l,int r,char c)
{
insertc(l,r,c);
int l1,r1,l2,r2;
l1=max_(1,l-k),r1=min_(n,r+k);
l2=min_(n,l+k/2),r2=max_(1,r-k/2);
for(int i=l1;i<=l2;++i) insert(1,i,i,get_sum(i,1,n));
for(int i=r2;i<=r1;++i) insert(1,i,i,get_sum(i,1,n));
if(l2+1<=r2-1) insert(1,l2+1,r2-1,ed1+ed2);
return;
}
int get_ans(int l,int r)
{
if(k==1) return r-l+1;
int sum=0;
if(r-l+1<=k) for(int i=l;i<=r;++i) sum+=get_sum(i,l,r);
else
{
int ll=l+k/2,rr=r-k/2;
for(int i=l;i>(tx+1);
n=strlen(tx+1);
k=read(),q=read();
build(1,1,n);
if(k&1) ed1=k/2+1,ed2=k/2;
else ed1=k/2,ed2=k/2;
for(int num,s,i=1;i<=n;++i) insert(1,i,i,get_sum(i,1,n)),blg[i]=i/siz+1;
for(int i=1;i<=blg[n];++i) tmo[i]=-1;
char c;
for(int ty,l,r,i=1;i<=q;++i)
{
t=i;
ty=read();
l=read(),r=read();
if(ty==1) c=readc(),chg(l,r,c);
else printf("%d\n",get_ans(l,r));
}
return 0;
}
T2 recollection
这个直接给了一个trie,要求\(lcp(r(u),r(v)))+lcs(r(u),r(v))\)的最大值
lcp 就是两点在trie上的lca的深度
lcs 可以考虑建出个广义sam，然后建出后缀链接的树，这时两个后缀节点在这棵树上的len[lca]就是lcs
于是问题就变成了trie上的每个点x，计算x的子树内的点两两在后缀链接树上len[lca]的最大值
当一个点固定时，即求深度最大的lca
结论:一个点x，和一个点集V，x与\(v\in V\)的\(\max(dep_{lca}(x,v))\)，在V中点按照dfs序排序后，x的dfs序的前驱和后继中取到
维护trie上点的子树在后缀链接树上对应的后缀点的dfs序，启发式合并set即可
复杂度\(O(n\log^2n)\)
代码
#include
using namespace std;
const int N=4e5+11;
struct qxxx{
int v,next;
}cc[2*N];
int n,tot=1;
int ans;
int pg[N];
int fa[N],col[N];
int link[N],len[N],dep[N],depp[N];
int pos[N],p[N];
int first[N],cnt;
int dfn[N],rle[N],num;
int f[N][20];
set st[N];
queue dui;
map tran[N],ch[N];
void qxx(int u,int v){cc[++cnt]={v,first[u]};first[u]=cnt;return;}
inline int max_(int x,int y){return x>y?x:y;}
inline int read()
{
int s=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
int insert_sam(int last,int w)
{
int x=++tot,p=last;
len[x]=len[p]+1;
for(;p&&!tran[p][w];p=link[p]) tran[p][w]=x;
if(!p) link[x]=1;
else
{
int q=tran[p][w];
if(len[q]==len[p]+1) link[x]=q;
else
{
int clone=++tot;
len[clone]=len[p]+1;
link[clone]=link[q];
for(map::iterator it=tran[q].begin();it!=tran[q].end();++it) tran[clone][it->first]=it->second;
link[q]=link[x]=clone;
for(;p&&tran[p][w]==q;p=link[p]) tran[p][w]=clone;
}
}
return x;
}
void get_sam()
{
int u=1;
map::iterator it;
for(it=ch[u].begin();it!=ch[u].end();++it) dui.push(it->second);
tot=1;
pos[1]=1;
while(dui.size())
{
u=dui.front();
dui.pop();
pos[u]=insert_sam(pos[fa[u]],col[u]);
for(it=ch[u].begin();it!=ch[u].end();++it) dui.push(it->second);
}
return;
}
void dfs_lkt(int x)
{
dfn[x]=++num;
rle[num]=x;
for(int i=first[x];i;i=cc[i].next) dep[cc[i].v]=dep[x]+1,dfs_lkt(cc[i].v);
return;
}
int get_lca(int x,int y)
{
if(dep[x]=0;--i)
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
for(int i=pg[dep[x]];i>=0;--i)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
if(x!=y) x=f[x][0];
return x;
}
int add(int x,int y,int lcp)
{
if(st[p[x]].size()::iterator ti,now;
for(ti=st[py].begin();ti!=st[py].end();++ti)
{
if(*ti>*st[px].begin())
{
now=st[px].lower_bound(*ti);
xx=*(--now);
ans=max_(ans,lcp+len[get_lca(rle[xx],rle[*ti])]);
}
if(*ti<*st[px].rbegin())
{
xx=*st[px].lower_bound(*ti);
ans=max_(ans,lcp+len[get_lca(rle[xx],rle[*ti])]);
}
}
for(ti=st[py].begin();ti!=st[py].end();++ti) st[px].insert(*ti);
st[py].clear();
return px;
}
void get_ans(int x)
{
int lcp=depp[x]-1;
st[p[x]].insert(dfn[pos[x]]);
for(map::iterator it=ch[x].begin();it!=ch[x].end();++it)
{
int y=it->second;
depp[y]=depp[x]+1;
get_ans(y);
p[x]=add(x,y,lcp);
}
return;
}
int main()
{
n=read();
for(int x,c,i=2;i<=n;++i)
{
x=read(),c=read();
fa[i]=x,col[i]=c;
ch[x][c]=i;
}
get_sam();
for(int i=1;i<=tot;++i) pg[i]=log2(i);
for(int i=2;i<=tot;++i) qxx(link[i],i),f[i][0]=link[i];
int logn=pg[tot];
for(int i=1;i<=logn;++i) for(int j=1;j<=tot;++j) f[j][i]=f[f[j][i-1]][i-1];
dep[1]=1,dfs_lkt(1);
for(int i=1;i<=n;++i) p[i]=i;
depp[1]=1,get_ans(1);
cout< T3
没改出来，MLE了
还是说一下思路吧，考虑分成三部分(1,u),(1,v),跨过lca(u,v)
第三个暴算，复杂度\(\sum|S|\)
前两个，建出询问串的AC自动机，一个串被匹配的次数就是fail树上子树和
dfs原树，把lca->u这条链放树上，用(1,u)的答案减去(1,lca)的答案