P4219 [BJOI2014] 大融合题解

SukiYuri · 2025-07-30 02:01:20 · 题解

分析

我们借鉴 Euler Tour Tree 的思想。

如果我们直接使用 Euler Tour Tree，即用平衡树维护欧拉环游序，即可解决此题，但这样做代码量巨大，实现十分复杂，~~主要是我不会~~。

因此我们考虑用平衡树维护树的括号序（也叫简化欧拉序）但是这样我们无法支持换根操作。也就没办法加边。考虑 LCT 加入 (u,v) 过程：将 u 设为根节点，连一条虚边到 v。这种操作对于我们来说是无法维护的。

考虑倒序操作，将加边操作变为删边，发现这个是好做的。考虑删边操作对括号序的影响：

假设现在有树：

它的括号序为：1 2 4 4 5 6 6 5 2 3 3 1

然后我们将边 2 5 删去，树变为两棵，括号序分别为 1 2 4 4 2 3 3 1，5 6 6 5。

容易发现，此时我们需要维护两个操作：

将区间 l\sim r 的数从序列里删去；
查询 l\sim r 间元素个数，即查询子树大小。

上述操作通过 FHQ-Treap 即可简单维护，复杂度 O(n+m\log n)。

代码

#include "iostream"
#include "cstdio"
#include "vector"
#include "random"
using namespace std;
const int maxn=2e5+5;
mt19937 gen(time(0));
struct Q {
    int op,x,y;
}q[maxn];
int dfn[maxn],op[maxn],ed[maxn],id,pos[maxn];
long long ans[maxn];
vector<int> G[maxn];
struct FHQ_Treap {
    int lc[maxn],rc[maxn],sz[maxn],fa[maxn],val[maxn],tt;
    unsigned rnd[maxn];
    inline int nd(int v) {
        ++tt; sz[tt]=1; rnd[tt]=gen(); val[tt]=v;
        return tt;
    }
    inline void pp(int u) {
        sz[u]=sz[lc[u]]+sz[rc[u]]+1; fa[u]=0;
        if(lc[u]) fa[lc[u]]=u; if(rc[u]) fa[rc[u]]=u;
    }
    void spt(int u,int v,int &l,int &r) {
        if(!u) return l=r=0,void();
        if(val[u]<=v) l=u,spt(rc[u],v,rc[u],r);
        else r=u,spt(lc[u],v,l,lc[u]); pp(u);
    }
    int mrg(int l,int r) {
        if(!l||!r) return l|r; int rt;
        if(rnd[l]<rnd[r]) lc[rt=r]=mrg(l,lc[r]);
        else rc[rt=l]=mrg(rc[l],r);
        pp(rt); return rt;
    }
    int getrt(int u) {
        while(fa[u]) u=fa[u];
        return u;
    }
    void bd(int &u,int l,int r) {
        if(l>r) return;
        int md=l+r>>1; pos[md]=u=nd(md);
        bd(lc[u],l,md-1); bd(rc[u],md+1,r); pp(u);
    }
    void deb(int u) {
        if(!u) return;
        cout<<u<<" "<<fa[u]<<" "<<val[u]<<" "<<lc[u]<<" "<<rc[u]<<" "<<sz[u]<<'\n';
        deb(lc[u]); deb(rc[u]);
    }
}lxt; // work work work work
void dfs(int u,int f) {
    dfn[op[u]=++id]=u;
    for(int v:G[u]) if(v!=f) dfs(v,u);
    dfn[ed[u]=++id]=u;
}
int main() {
    ios::sync_with_stdio(0);
    int n,m; cin>>n>>m;
    for(int i=1;i<=m;++i) {
        char s; int u,v; cin>>s>>u>>v;
        if(s=='A') {
            q[i]={0,u,v};
            G[u].push_back(v); G[v].push_back(u);
        }
        else q[i]={1,u,v};
    }
    for(int i=1;i<=n;++i) if(!op[i]) {
        int pos=id; dfs(i,0);
        lxt.bd(pos,pos+1,id); // lxt.deb(pos);
    }
    // for(int i=1;i<=id;++i) cout<<dfn[i]<<" \n"[i==id];
    for(int i=m;i;--i) {
        auto [opt,u,v]=q[i];
        if(op[u]>op[v]) swap(u,v);
        if(opt) {
            int rt=lxt.getrt(pos[op[u]]),a1,a2,a3;
            int x=lxt.sz[rt],y;
            lxt.spt(rt,op[v]-1,a1,a2); lxt.spt(a2,ed[v],a2,a3);
            y=lxt.sz[a2];
            ans[i]=1ll*(x-y)*y/4;
            lxt.mrg(a1,lxt.mrg(a2,a3));
        } else {
            int rt=lxt.getrt(pos[op[u]]),a1,a2,a3;
            lxt.spt(rt,op[v]-1,a1,a2); lxt.spt(a2,ed[v],a2,a3);
            lxt.mrg(a1,a3);
        }
    }
    for(int i=1;i<=m;++i) if(ans[i]) cout<<ans[i]<<'\n';
    return 0;
}
/*
8 6
A 2 3
A 3 4
A 3 8
A 8 7
A 6 5
Q 3 8
*/

P4219 [BJOI2014] 大融合 题解

分析

代码

P4219 [BJOI2014] 大融合题解