繰り返しサブストリング-SAM-イニシアチブマージ-セグメントツリー
52262 ワード
1つの文字列に1つのサブ列sの重み値を複数回尋ねる.1つの文字列の重み値は、少なくとも2回発生したサブ列の最長の長さとして定義されます.n , m ≤ 1 0 5 n,m\le10^5 n,m≤105. 问题解:シリアルを逆にしてSAMを作ることを考えています.明らかに質問は先に二分しなければならない.それは,ある区間内の点に対応して2つの点が存在するか否かを求め,そのLCAのvalが2点以上の値を求めることである.どのような点対が答えとなる可能性があるかを考慮すると,明らかに3つの接頭辞の下にa,b,cがa L C A(p),p s(b)=L C A(p),p s(c))LCA(ps(a),ps(b)=LCA(ps(a),ps(c)=LCA(ps(a),ps(b)=LCA(ps(a),ps(b)=LCA(ps(a),ps(c))を満たす場合,明らかに選択(a,c)は(a,b)よりも優れないので,啓発的に統合したすべての答えとなる可能性のある点対を求め,O(n l g n)O(nlgn)O(nlgn)個があり、答えになる可能性のあるすべての点形は(a,b,val)(a>bと仮定する)である.次に、矩形で最大値を尋ねる質問で、オフラインで直接線分ツリーを見つけることができます.
#include
using namespace std;
typedef pair<int,int> pii;
typedef set<int>::iterator sit;
namespace INPUT_SPACE{
const int BS=(1<<24)+5;char Buffer[BS],*HD,*TL;inline int gc() { if(HD==TL) TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);return (HD==TL)?EOF:*HD++; }
inline int inn() { int x,ch;while((ch=gc())<'0'||ch>'9');x=ch^'0';while((ch=gc())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0');return x; }
inline int instr(char *s) { int n=0,ch;while((ch=gc())<'a'||ch>'z');s[++n]=char(ch);while((ch=gc())>='a'&&ch<='z') s[++n]=char(ch);return n; }
}using INPUT_SPACE::inn;using INPUT_SPACE::instr;
namespace OUTPUT_SPACE{
char ss[500000*15],tt[20];int ssl,ttl;inline int Flush() { return fwrite(ss+1,sizeof(char),ssl,stdout),ssl=0,0; }
inline int print(int x) { if(!x) ss[++ssl]='0';for(ttl=0;x;x/=10) tt[++ttl]=char(x%10+'0');for(;ttl;ttl--) ss[++ssl]=tt[ttl];return ss[++ssl]='
'; }
}using OUTPUT_SPACE::print;using OUTPUT_SPACE::Flush;
const int N=200010,SIG=26,INF=INT_MAX/10;
vector<pii> ps[N],q[N];char s[N];int ans[N];
struct SAM{
int val[N],fa[N],ch[N][SIG],rt,las,node_cnt,id[N];
set<int> s[N];vector<int> g[N];
inline int new_node(int v) { return val[++node_cnt]=v,node_cnt; }
inline int _init() { return node_cnt=0,rt=las=new_node(0); }
inline int extend(int w,int i)
{
int p=las,np=new_node(val[p]+1);
while(p&&!ch[p][w]) ch[p][w]=np,p=fa[p];
if(!p) fa[np]=rt;
else{
int q=ch[p][w],v=val[p]+1;
if(val[q]==v) fa[np]=q;
else{
int nq=new_node(v);
memcpy(ch[nq],ch[q],sizeof ch[q]);
fa[nq]=fa[q],fa[q]=fa[np]=nq;
while(p&&ch[p][w]==q) ch[p][w]=nq,p=fa[p];
}
}
return id[las=np]=i;
}
inline int dfs(int x)
{
if(id[x]) s[x].insert(id[x]);s[x].insert(INF);
Rep(i,g[x])
{
int y=g[x][i];dfs(y);
if(s[x].size()<s[y].size()) s[x].swap(s[y]);
if(s[y].empty()) continue;
for(sit it=s[y].begin();it!=s[y].end();it++) if(*it!=INF)
{
sit it2=s[x].lower_bound(*it);
if(*it2!=INF) ps[*it2].pb(mp(*it,val[x]));
if(it2!=s[x].begin()) it2--,ps[*it].pb(mp(*it2,val[x]));
}
for(sit it=s[y].begin();it!=s[y].end();it++) s[x].insert(*it);set<int>().swap(s[y]);
}
return 0;
}
inline int solve() { rep(i,2,node_cnt) g[fa[i]].pb(i);return dfs(rt); }
}t;
struct segment{
int v,l,r;segment *ch[2];
}*rt;
inline int build(segment* &rt,int l,int r)
{
rt=new segment,rt->l=l,rt->r=r,rt->v=0;
if(l==r) return 0;int mid=(l+r)>>1;
return build(rt->ch[0],l,mid),build(rt->ch[1],mid+1,r);
}
inline int update(segment* &rt,int p,int v)
{
int l=rt->l,r=rt->r,mid=(l+r)>>1;rt->v=max(rt->v,v);
if(l==r) return 0;return update(rt->ch[p>mid],p,v);
}
inline int query(segment* &rt,int s,int t)
{
int l=rt->l,r=rt->r,mid=(l+r)>>1;
if(s<=l&&r<=t) return rt->v;int ans=0;
if(s<=mid) ans=max(ans,query(rt->ch[0],s,t));
if(mid<t) ans=max(ans,query(rt->ch[1],s,t));
return ans;
}
inline int check(int l,int r,int x) { return query(rt,l+x-1,r)>=x; }
inline int query(int l,int r)
{
int L=1,R=r-l+1;
while(L<=R)
{
int mid=(L+R)>>1;
if(check(l,r,mid)) L=mid+1;
else R=mid-1;
}
return R;
}
int main()
{
int n=inn(),m=inn(),r;instr(s),t._init();
reverse(s+1,s+n+1);rep(i,1,n) t.extend(s[i]-'a',i);
t.solve(),build(rt,1,n);
rep(i,1,m) r=n-inn()+1,q[r].pb(mp(n-inn()+1,i));
rep(i,1,n)
{
Rep(j,ps[i]) update(rt,ps[i][j].fir,ps[i][j].sec);
Rep(j,q[i]) ans[q[i][j].sec]=query(q[i][j].fir,i);
}
rep(i,1,m) print(ans[i]);return Flush(),0;
}