题解：P11098 [ROI 2022 Day 1] 滑梯

是青白呀 · 2024-11-06 21:26:10 · 题解

不难发现所有经过的管道会形成一个树形的结构，每一个询问实际上等价于求两点在树上的 LCA。于是考虑把树求出来之后跑 LCA 算法即可做到 O(n^2)，瓶颈在于树的点数是 O(n^2) 级别的。

不难发现很多点是无效的，于是考虑对这棵树建立虚树，只保留 n+1 个叶子结点、n 个既有左儿子、又有右儿子的分叉结点、以及 O(q) 个询问结点。

首先对于每一层求出该层的分叉结点，可以通过使用树状数组维护路径经过点的横坐标的方式求出，每次需要的操作是后缀 -1 和单点查询。

然后考虑建树。我们从第 n 层向第 0 层，由下往上扫描，维护当前层的每一个点在虚树上向下走遇到的（包含自己的）首个点的编号，需要支持的操作是的求第 k 个点的点值、单点修改以及合并两个相邻点。这些操作可以用 FHQ 维护，但常数较大。我们亦可以用线段树维护，额外在叶子上维护一个标记 tag，其为 1 当且仅当这个点是某个合并形成的连续段的第一个点。此时求第 k 个点的下标可以用线段树上二分实现。于是对于每一层，我们先求出要合并的两个点的标号，并新建一个节点作为它们虚树上的父亲；再遍历该层的所有询问点，对于每个点查询线段树上维护的、虚树上下方首个点，然后新建一个点作为其父亲即可。注意所有新建点的操作都要同时在线段树上进行单点修改。

最后使用倍增、树剖、欧拉序等任意一种方式求 LCA 即可。总复杂度 O(n\log n)，代码较复杂，常数较大。

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
#define double long double
#define qingbai 666
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=5e5+5,M=6,S=(1<<8)+5,inf=1e9+7,mo=1e9+7;
const double eps=1e-8;
void read(int &p){
    int x=0,w=1;
    char ch=0;
    while(!isdigit(ch)){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    p=x*w;
}
int n,a[N],m,cntp,qid[N][2],bel[N*2];
pii q[N][2],p[N*2];
int cntn=0;
int pt[N];
struct BIT{
    int t[N];
    void add(int x,int v){
        for(int i=x;i<=n;i+=lowbit(i))
            t[i]+=v;
    }
    int query(int x){
        int res=0;
        for(int i=x;i;i-=lowbit(i))
            res+=t[i];
        return res;
    }
}BIT;
vector<pii>targp[N];
vector<int>e[N*4];
struct seg{
    int t[4*N],sum[4*N];
    void pushup(int x){
        sum[x]=sum[ls(x)]+sum[rs(x)];
    }
    void modifyn(int x,int le,int ri,int p,int v){
        if(le==ri){
            t[x]=v;
            return;
        }
        int mid=(le+ri)>>1;
        if(p<=mid)modifyn(ls(x),le,mid,p,v);
        else modifyn(rs(x),mid+1,ri,p,v);
    }
    void modifys(int x,int le,int ri,int p,int v){
        if(le==ri){
            sum[x]=v;
            return;
        }
        int mid=(le+ri)>>1;
        if(p<=mid)modifys(ls(x),le,mid,p,v);
        else modifys(rs(x),mid+1,ri,p,v);
        pushup(x);
    }
    int queryp(int x,int le,int ri,int v,int op){
        if(le==ri){
            if(op)bel[op]=cntn,e[cntn].push_back(t[x]),t[x]=cntn;
            return le;
        }
        int mid=(le+ri)>>1;
        if(sum[ls(x)]>=v)return queryp(ls(x),le,mid,v,op);
        else return queryp(rs(x),mid+1,ri,v-sum[ls(x)],op);
    }
    int queryn(int x,int le,int ri,int p){
        if(le==ri)return t[x];
        int mid=(le+ri)>>1;
        if(p<=mid)return queryn(ls(x),le,mid,p);
        else return queryn(rs(x),mid+1,ri,p);
    }
}T;
int fa[N*4][20],dep[N*4];
pii ttp[N*4];
void dfs(int x,int f){
    dep[x]=dep[f]+1;
    fa[x][0]=f;
    rep(i,1,19)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(auto j:e[x])
        dfs(j,x);
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    repp(i,19,0)
        if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
    if(x==y)return x;
    repp(i,19,0)
        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
signed main(){
    read(n);
    rep(i,1,n)
        read(a[i]),BIT.add(i,1);
    rep(i,1,n){
        pt[a[i]]=BIT.query(a[i]);
        BIT.add(a[i]+1,-1);
    }
    read(m);
    rep(i,1,m){
        read(q[i][0].fir),read(q[i][0].sec),read(q[i][1].fir),read(q[i][1].sec);
        if(q[i][0]>q[i][1])swap(q[i][0],q[i][1]);
        q[i][0].fir++,q[i][0].sec++,q[i][1].fir++,q[i][1].sec++;
        p[++cntp]=q[i][0],p[++cntp]=q[i][1];
    }
    sort(p+1,p+cntp+1),cntp=unique(p+1,p+cntp+1)-p-1;
    rep(i,1,m){
        qid[i][0]=lower_bound(p+1,p+cntp+1,q[i][0])-p;
        qid[i][1]=lower_bound(p+1,p+cntp+1,q[i][1])-p;
    }
    rep(i,1,cntp)
        targp[p[i].fir].push_back(mp(p[i].sec,i));
    rep(i,1,n+1){
        cntn++,ttp[i]=mp(n+1,i);
        T.modifyn(1,1,n+1,i,cntn);
        T.modifys(1,1,n+1,i,1);
    }
    for(auto j:targp[n+1])
        bel[j.sec]=j.fir;
    repp(i,n,1){
        int targ=T.queryp(1,1,n+1,pt[i],0),nxtt=T.queryp(1,1,n+1,pt[i]+1,0);
        int x=T.queryn(1,1,n+1,targ),y=T.queryn(1,1,n+1,nxtt);
        T.modifys(1,1,n+1,nxtt,0);
        cntn++,ttp[cntn]=mp(i,pt[i]);
        e[cntn].push_back(x),e[cntn].push_back(y);
        T.modifyn(1,1,n+1,targ,cntn);
        int nid=cntn;
        for(auto j:targp[i]){
            if(j.fir==pt[i])bel[j.sec]=nid;
            else cntn++,ttp[cntn]=mp(i,j.fir),T.queryp(1,1,n+1,j.fir,j.sec);
        }
    }
    dfs(cntn,0);
    rep(i,1,m){
        int lcap=lca(bel[qid[i][0]],bel[qid[i][1]]);
        printf("%d %d\n",ttp[lcap].fir-1,ttp[lcap].sec-1);
    }
    return 0;
}