Luogu

Gym

分析

析合树模板题。

如果两个点在析合树上的 LCA 是析点,那么答案就是这个析点对应的段;否则还要找到两个点所在的两棵子树,LCA 的儿子序列中这两个子树间的子序列才是答案。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,m,p[N];

namespace H {
    int f[17][N],g[17][N],lg[N];
    void build() {
        for (int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
        for (int i=1;i<=n;++i) f[0][i]=g[0][i]=p[i];
        for (int i=1;i<=16;++i)
            for (int j=1;j<=n;++j) {
                f[i][j]=max(f[i-1][j],f[i-1][j+(1<<(i-1))]);
                g[i][j]=min(g[i-1][j],g[i-1][j+(1<<(i-1))]);
            }
    }
    int qmax(int l,int r) { int t=lg[r-l+1]; return max(f[t][l],f[t][r-(1<<t)+1]); }
    int qmin(int l,int r) { int t=lg[r-l+1]; return min(g[t][l],g[t][r-(1<<t)+1]); }
}

#define ls (o<<1)
#define rs (o<<1|1)
namespace S {
    int minv[N<<2],addv[N<<2];
    void pushup(int o) { minv[o]=min(minv[ls],minv[rs]); }
    void pushdown(int o) {
        if (addv[o]) {
            addv[ls]+=addv[o],minv[ls]+=addv[o];
            addv[rs]+=addv[o],minv[rs]+=addv[o];
            addv[o]=0;
        }
    }
    void modify(int o,int l,int r,int ql,int qr,int w) {
        if (ql<=l&&r<=qr) { addv[o]+=w,minv[o]+=w; return; }
        int mid=(l+r)>>1; pushdown(o);
        if (ql<=mid) modify(ls,l,mid,ql,qr,w);
        if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
        pushup(o);
    }
    int query(int o,int l,int r) {
        if (l==r) return l;
        int mid=(l+r)>>1; pushdown(o);
        if (!minv[ls]) return query(ls,l,mid);
        else return query(rs,mid+1,r);
    }
}
#undef ls
#undef rs

int rt;
struct edge { int v,nxt; } e[N];
int head[N];
void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

namespace T {
    int sta1[N],top1=0,sta2[N],top2=0,sta[N],top=0;
    int id[N],tot=0,L[N],R[N],M[N],tp[N];

    bool check(int l,int r) { return H::qmax(l,r)-H::qmin(l,r)==r-l; }

    void build() {
        for (int i=1;i<=n;++i) {
            while (top1&&p[i]<=p[sta1[top1]])
                S::modify(1,1,n,sta1[top1-1]+1,sta1[top1],p[sta1[top1]]),--top1;
            S::modify(1,1,n,sta1[top1]+1,i,-p[i]),sta1[++top1]=i;
            while (top2&&p[i]>=p[sta2[top2]])
                S::modify(1,1,n,sta2[top2-1]+1,sta2[top2],-p[sta2[top2]]),--top2;
            S::modify(1,1,n,sta2[top2]+1,i,p[i]),sta2[++top2]=i;
            id[i]=++tot,L[tot]=R[tot]=i;
            int lim=S::query(1,1,n),cur=tot;
            while (top&&L[sta[top]]>=lim) {
                if (tp[sta[top]]&&check(M[sta[top]],i))
                    R[sta[top]]=i,addEdge(sta[top],cur),cur=sta[top--];
                else if (check(L[sta[top]],i)) {
                    ++tot,tp[tot]=1,L[tot]=L[sta[top]],R[tot]=i,M[tot]=L[cur];
                    addEdge(tot,sta[top--]),addEdge(tot,cur),cur=tot;
                } else {
                    ++tot,addEdge(tot,cur);
                    do addEdge(tot,sta[top--]); while (top&&!check(L[sta[top]],i));
                    L[tot]=L[sta[top]],R[tot]=i,addEdge(tot,sta[top--]),cur=tot;
                }
            }
            S::modify(1,1,n,1,i,-1),sta[++top]=cur;
        }
        rt=sta[1];
    }
}

int dep[N],fa[N],sz[N],hson[N],top[N];
void dfs1(int u,int f) {
    dep[u]=dep[fa[u]=f]+1,sz[u]=1;
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
void dfs2(int u,int anc) {
    top[u]=anc;
    if (hson[u]) dfs2(hson[u],anc);
    for (int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}
int LCA(int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
int jump(int u,int p) {
    int f;
    while (top[u]!=top[p]) f=top[u],u=fa[top[u]];
    return u==p?f:hson[p];
}

void query(int l,int r) {
    int u=T::id[l],v=T::id[r],t=LCA(u,v);
    if (!T::tp[t]) printf("%d %d\n",T::L[t],T::R[t]);
    else printf("%d %d\n",T::L[jump(u,t)],T::R[jump(v,t)]);
}

int main() {
    n=read();
    for (int i=1;i<=n;++i) p[i]=read();
    H::build(),T::build(),dfs1(rt,0),dfs2(rt,rt);
    m=read();
    while (m--) { int l=read(),r=read(); query(l,r); }
    return 0;
}
最后修改:2020 年 11 月 12 日 10 : 27 PM