题目大意
一个长度为(n)的(01)串，(q)次询问，每次询问求([l,r])内的前缀选两个出来，(lcp)的最大值。
LCT做法
就是求两两(lca)深度的最大值。
询问按右端点排序，每加一个右端点就看一下跟每个左端点(l)的(lca)深度是多少，就可以更新(l)及以前的答案了。
从(LCT) (access)求(lca)的方法得到启发。
这个过程就是每次从一个点往上跳，每遇到一种颜色就把这个颜色的答案跟遇到的点深度取(max)（跟这个颜色的(lca)就是第一次遇到的点），然后把一整条链染色（编号大的颜色可以覆盖编号小的颜色，因为每次更新答案都是更新一个前缀）。
任何时刻一种颜色都会形成一条链，用(LCT)的一条实链表示颜色相同的点，边(access)边更新答案并染色即可。
居然(1A)了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mxn=200010;
int rd(){
int x=0,flg=1;
char c=getchar();
for (;(c<48||c>57)&&c!='-';c=getchar());
if (c=='-') flg=-1,c=getchar();
for (;c>47&&c<58;x=x*10+c-48,c=getchar());
return flg*x;
}
int n,tr[mxn];
void add(int i,int x){
i=n-i+1;
for (;i<=n;i+=i&-i) tr[i]=max(tr[i],x);
}
int sum(int i){
i=n-i+1;
int ret=0;
for (;i;i-=i&-i) ret=max(ret,tr[i]);
return ret;
}
struct nd{
int dep,tag;
nd *ls,*rs,*fa;
}pool[mxn],*tp=pool;
bool noroot(nd *i){
return i->fa&&(i->fa->ls==i||i->fa->rs==i);
}
void pushdown(nd *i){
if (i->ls) i->ls->tag=i->tag;
if (i->rs) i->rs->tag=i->tag;
}
void rotate(nd *i){
nd *f=i->fa,*s;
if (noroot(f))
if (f->fa->ls==f) f->fa->ls=i;
else f->fa->rs=i;
else;
i->fa=f->fa,f->fa=i;
if (f->ls==i) f->ls=s=i->rs,i->rs=f;
else f->rs=s=i->ls,i->ls=f;
if (s) s->fa=f;
}
nd *stk[mxn];
void splay(nd *x){
int tpp=1;
stk[1]=x;
for (nd *y=x;noroot(y);stk[++tpp]=y=y->fa);
for (;tpp;pushdown(stk[tpp--]));
for (nd *y;noroot(x);rotate(x))
if (noroot(y=x->fa)) rotate((y->fa->ls==y)^(y->ls==x)?x:y);
}
void access(nd *x,int tg){
for (nd *y=0;x;x=(y=x)->fa){
splay(x),x->rs=y;
add(x->tag,x->dep);
x->tag=tg;
}
}
int cur,tot,fa[mxn],len[mxn],trans[mxn][2],idx[mxn];
nd *id[mxn];
char s[mxn];
int ins(int u,int c){
int x=++tot,v;
len[x]=len[u]+1;
for (;u&&!trans[u][c];trans[u][c]=x,u=fa[u]);
if (!u) fa[x]=1;
else if (len[v=trans[u][c]]==len[u]+1) fa[x]=v;
else{
fa[++tot]=fa[v],fa[x]=fa[v]=tot,len[tot]=len[u]+1;
for (int i=0;i<2;++i) trans[tot][i]=trans[v][i];
for (;u&&trans[u][c]==v;trans[u][c]=tot,u=fa[u]);
}
return x;
}
struct ndd{
int l,r,id;
bool operator<(const ndd a)const{
return r<a.r;
}
}a[mxn];
int q,ans[mxn];
int main()
{
scanf("%d%d%s",&n,&q,s);
cur=tot=1;
for (int i=0;i<n;++i) idx[i+1]=cur=ins(cur,s[i]-'0');
for (int i=1;i<=tot;++i) id[i]=++tp,tp->dep=len[i];
for (int i=2;i<=tot;++i) id[i]->fa=id[fa[i]];
for (int i=1;i<=q;++i)
a[i].l=rd(),a[i].r=rd(),a[i].id=i;
sort(a+1,a+q+1);
for (int i=1,cur=1;i<=q;++i){
for (;cur<=a[i].r;access(id[idx[cur]],cur),++cur);
ans[a[i].id]=sum(a[i].l);
}
for (int i=1;i<=q;++i)
printf("%d
",ans[i]);
return 0;
}
启发式合并+二维数点做法
每个点维护(endpos)集合。
考虑合并两个集合会对哪些询问造成贡献。两个来自不同集合的(endpos) (x,y) ((x<y))，更新包含([x,y])的询问。
发现只有(O(n))个区间是有用的，其他都包含了这些区间，不用计算。进一步分析较小集合的每个数最多只会造成两个贡献的区间（另一个集合中的前驱后继）。
把所有这样的区间拉出来，根据启发式合并总数是(nlogn)级别的。
然后就是一个二维数点，可以用树状数组来做。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
int rd(){
int x=0,flg=1;
char c=getchar();
for (;(c<48||c>57)&&c!='-';c=getchar());
if (c=='-') flg=-1,c=getchar();
for (;c>47&&c<58;x=x*10+c-48,c=getchar());
return flg*x;
}
const int mxn=200010;
struct nd{
int l,r,x;
bool operator<(const nd a)const{
return l>a.l;
}
}a[mxn<<5],b[mxn];
int n,cur,tot,fa[mxn],len[mxn],id[mxn],trans[mxn][2];
char s[mxn];
int ins(int u,int c,int idd){
int x=++tot,v;
id[x]=idd,len[x]=len[u]+1;
for (;u&&!trans[u][c];trans[u][c]=x,u=fa[u]);
if (!u) fa[x]=1;
else if (len[v=trans[u][c]]==len[u]+1) fa[x]=v;
else{
fa[++tot]=fa[v],fa[x]=fa[v]=tot;
id[tot]=idd,len[tot]=len[u]+1;
for (int i=0;i<2;++i) trans[tot][i]=trans[v][i];
for (;u&&trans[u][c]==v;trans[u][c]=tot,u=fa[u]);
}
return x;
}
int head[mxn],son[mxn][2],idd[mxn],N,M;
set<int> lis[mxn];
void dfs(int u){
if (!son[u][0]&&!son[u][1]){
idd[u]=++M;
lis[M].insert(id[u]+1);
return;
}
if (son[u][0]) dfs(son[u][0]);
if (son[u][1]) dfs(son[u][1]);
int ls=idd[son[u][0]],rs=idd[son[u][1]];
if (lis[ls].size()<lis[rs].size()) swap(ls,rs);
set<int>::iterator sx=lis[rs].begin();
for (;sx!=lis[rs].end();sx++){
int x=*sx;
set<int>::iterator sl=lis[ls].lower_bound(x),sr=sl;
if (sl!=lis[ls].begin()){
sl--;
a[++N]=(nd){*sl,x,len[u]};
}
if (sr!=lis[ls].end()){
a[++N]=(nd){x,*sr,len[u]};
}
}
idd[u]=ls;
sx=lis[rs].begin();
for (;sx!=lis[rs].end();sx++) lis[ls].insert(*sx);
if (id[u]+1==len[u]){
int x=id[u]+1;
set<int>::iterator sl=lis[ls].lower_bound(x),sr=sl;
if (sl!=lis[ls].begin()){
sl--;
a[++N]=(nd){*sl,x,len[u]};
}
if (sr!=lis[ls].end()){
a[++N]=(nd){x,*sr,len[u]};
}
lis[ls].insert(x);
}
}
void init(){
cur=tot=1;
for (int i=0;i<n;++i) cur=ins(cur,s[i]-'0',i);
for (int i=2;i<=tot;++i)
son[fa[i]][s[id[i]-len[fa[i]]]-'0']=i;
dfs(1);
}
int q,tr[mxn],ans[mxn];
void add(int i,int x){
for (;i<=n;i+=i&-i) tr[i]=max(tr[i],x);
}
int sum(int i){
int ret=0;
for (;i;i-=i&-i) ret=max(ret,tr[i]);
return ret;
}
int main()
{
// freopen("history.in","r",stdin);
// freopen("hist.out","w",stdout);
scanf("%d%d%s",&n,&q,s);
init();
for (int i=1;i<=q;++i){
int l=rd(),r=rd();
b[i]=(nd){l,r,i};
}
sort(a+1,a+N+1);
sort(b+1,b+q+1);
for (int i=1,cur=1;i<=q;++i){
for (;cur<=N&&a[cur].l>=b[i].l;add(a[cur].r,a[cur].x),++cur);
ans[b[i].x]=sum(b[i].r);
}
for (int i=1;i<=q;++i)
printf("%d
",ans[i]);
return 0;
}