Solution 【主席树|[LOJ]#2720. 「NOI2018」你的名字 后缀自动机+主席树】首先讲一下一个68分的水法：建广义SAM，然后每次询问完之后暴力撤销，复杂度未知。
这种做法本身复杂度好像就不对，而且也没法扩展，考虑另外的做法。
考虑每个询问串前缀的贡献。首先要保证本质不同，所以先求出每个前缀的最短的没有在之前出现过的后缀，这个可以对每个询问串建SAM求。然后要求出每个前缀的最短的没有在 S S S出现过的后缀，如果是68分，相当于在 S S S的SAM上匹配，求最长匹配的后缀长度。考虑多了 [ l , r ] [l,r] [l,r]限制之后怎么搞，如果匹配到 x x x节点，就相当于在 p a r e n t parent parent树上 x x x的子树中有满足条件的点，这个点一定是 <
= r <
=r <=r的最大值，因为我们要求的最短没有出现后缀长度=最长出现后缀长度+1，一定是找最大的那个，那么用一个主席树支持求这个就行了。
Code
#include
using namespace std;
#define LL long long
#define pa pair
const int Maxn=1000010;
const int inf=2147483647;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
char s[Maxn],str[Maxn<<1];
int n;
struct SAM
{
int son[Maxn<<1][26],mx[Maxn<<1],par[Maxn<<1];
int lst,tot;
void init(){lst=tot=1;
}
void clear()
{
for(int i=1;
i<=tot;
i++)
{
par[i]=mx[i]=0;
for(int j=0;
j<26;
j++)son[i][j]=0;
}
}
void extend(int x)
{
int p=lst,np=++tot;
mx[np]=mx[p]+1;
while(p&&!son[p][x])son[p][x]=np,p=par[p];
if(!p)par[np]=1;
else
{
int q=son[p][x];
if(mx[p]+1==mx[q])par[np]=q;
else
{
int nq=++tot;
mx[nq]=mx[p]+1;
for(int i=0;
i<26;
i++)son[nq][i]=son[q][i];
par[nq]=par[q];
par[q]=par[np]=nq;
while(son[p][x]==q)son[p][x]=nq,p=par[p];
}
}
lst=np;
}
}T1,T2;
int Len[Maxn],ed[Maxn];
bool mark[Maxn<<1];
int c[Maxn*24],lc[Maxn*24],rc[Maxn*24],cnt=0,root[Maxn<<1];
void insert(int&u,int l,int r,int p)
{
if(!u)u=++cnt;
c[u]++;
if(l==r)return;
int mid=l+r>>1;
if(p<=mid)insert(lc[u],l,mid,p);
else insert(rc[u],mid+1,r,p);
}
void merge(int&u1,int u2)
{
if(!u1){u1=u2;
return;
}
if(!u2)return;
c[u1]+=c[u2];
merge(lc[u1],lc[u2]),merge(rc[u1],rc[u2]);
}
int query(int L,int R,int l,int r,int k)
{
if(!R||c[R]==c[L])return -1;
if(l==r)return l;
int mid=l+r>>1;
if(k<=mid)return query(lc[L],lc[R],l,mid,k);
int t=query(rc[L],rc[R],mid+1,r,k);
if(t!=-1)return t;
return query(lc[L],lc[R],l,mid,k);
}
vectorG[Maxn<<1];
int in[Maxn<<1],out[Maxn<<1],dfn=0;
void dfs(int x)
{
in[x]=++dfn;
for(int i=0;
i 推荐阅读
- 主席树|HDU4417（主席树）
- 【后缀自动机】 CodeForces 235C Cyclical Quest
- 主席树|191101CSP模拟题解
- 后缀自动机|[Codeforces] 1037 H. Security 后缀自动机+主席树