洛谷 P3302 【SDOI2013】森林题解

2020-3-5 xiaoh

题意

给定一个有 $n$ 个节点的森林( $1\leq n\leq 8\times 10^4$ ).要求实现如下两种共 $m$ 个操作( $1\leq m\leq 8\times 10^4$ ):
1.连边,保证连边之后依然是森林;
2.查询两点间路径上点权的第 $k$ 大,保证两点联通且第 $k$ 大存在.
注意:算法要求强制在线.

题解

237行……本题突破了本人的代码极限QAQ
首先考虑本题适用于哪种数据结构.对于操作 $1$ ,用 $LCT$ 维护是再好不过的了.但是此时对于询问 $2$ ,我们只能暴力截下整段序列处理,最快的用快排思想寻找第 $k$ 大也要 $O(n)$ ,根本不可行……
所以考虑从操作 $2$ 下手.注意到若无操作 $1$ ,则用主席树便可很好地在 $O(n\log n)$ 的时间内维护(题目在此,戳我).那么怎么样在至多增加一个 $\log$ 的时间内将算法扩展至支持动态连边呢?我们惊喜地发现,操作中仅有加边,没有删边.那就意味着我们可以使用启发式合并来处理.所以我们每次动态的维护倍增的 $LCA$ ,查询第 $k$ 大的主席树,以及每个节点的 $size$ .那就意味着我们要同时维护倍增数组,主席树和并查集(大雾)……所以我们只要纯粹的把这三者的代码(如果你认为前向星和离散化也是一个数据结构的话就是五个啦QAQ)揉在一起,再使用启发式合并对每次小的那个子树暴力的修改它的倍增数组,并重建这一部分的主席树即可.时间复杂度 $O(n\log n+m\log^2n)$ ,只要 $dsu$ 没写挂应该就能过了……
当然其实本题最难的是编码.为了方便,笔者将三个数据结构进行了封装,以免函数名/变量名发生冲突.

题解

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=80010,LOGN=19;
int n,m,t;
int a[MAXN];
int tot=1;
int edge[MAXN*2],nxt[MAXN*2],hd[MAXN];
int mp2[MAXN];
int lastans=0;
inline void add_edge(int u,int v)
{
    edge[tot]=v,nxt[tot]=hd[u],hd[u]=tot++;
}
bool book[MAXN];
class Union_find{//并查集
    int f[MAXN],sz[MAXN];
public:
    inline void init()
    {
        for(int i=1;i<=n;i++) f[i]=i,sz[i]=1;
    }
    int find(int x)
    {
        return f[x]=(x==f[x])? f[x]:find(f[x]);
    }
    inline void Union(int u,int v)
    {
        u=find(u),v=find(v);
        f[v]=u,sz[u]+=sz[v];
    }
    int& operator [](int x)
    {
        return sz[x];
    }
}g;
queue<int> q;
class lca{//倍增数组
    int LCA[MAXN][LOGN+1];
    int d[MAXN];
    void prework(int x)//预处理
    {
        int tmp=x;
        d[x]=1,q.push(x),book[x]=1;
        while(!q.empty())
        {
            int x=q.front();q.pop();
            for(int i=hd[x];i;i=nxt[i])
            if(!book[edge[i]])
            {
                int y=edge[i];
                g.Union(tmp,x);
                d[y]=d[x]+1;
                LCA[y][0]=x;
                q.push(y),book[y]=1;
                for(int j=1;j<=LOGN;j++) LCA[y][j]=LCA[LCA[y][j-1]][j-1];
            }
        }
    }
public:
    void init()
    {
        for(int i=1;i<=n;i++)
        if(!book[i]) prework(i);
    }
    inline int query(int x,int y)//查询
    {
        if(d[x]<d[y]) swap(x,y);
        for(int i=LOGN;i>=0;i--)
        if(d[LCA[x][i]]>=d[y]) x=LCA[x][i];
        if(x==y) return x;
        for(int i=LOGN;i>=0;i--)
        if(LCA[x][i]!=LCA[y][i]) x=LCA[x][i],y=LCA[y][i];
        return LCA[x][0];
    }
    inline void update(int x,int y)//暴力修改小树倍增数组中的值
    {
        d[y]=d[x]+1,LCA[y][0]=x;
        for(int j=1;j<=LOGN;j++) LCA[y][j]=LCA[LCA[y][j-1]][j-1];
        q.push(y);
        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(int i=hd[u];i;i=nxt[i])
            if(edge[i]!=LCA[u][0])
            {
                int v=edge[i];
                d[v]=d[u]+1;
                LCA[v][0]=u;
                q.push(v);
                for(int j=1;j<=LOGN;j++) LCA[v][j]=LCA[LCA[v][j-1]][j-1];
            }
        }
        add_edge(x,y),add_edge(y,x);
    }
    int* operator [](int x)
    {
        return LCA[x];
    }
}LCA;
unordered_map<int,int> mp;//只要没有特殊数据,unordered_map的复杂度就是常数级别的,会比map快一点
int b[MAXN];
inline void prework()
{
    for(int i=1;i<=n;i++) b[i]=a[i];
    sort(b+1,b+n+1);
    int cnt=0;
    for(int i=1;i<=n;i++)
    if(!mp[b[i]]) mp[b[i]]=++cnt,mp2[cnt]=b[i];
    for(int i=1;i<=n;i++) a[i]=mp[a[i]];
}
struct node{
    int l,r;
    int val;
};
class Segment_Tree{//主席树
    int tot;
    node f[MAXN*4+MAXN*LOGN*LOGN];
    int rt[MAXN];
    inline void pushup(int p)
    {
        f[p].val=f[f[p].l].val+f[f[p].r].val;
    }
    int build(int l,int r)
    {
        int p=++tot;
        if(l==r) return p;
        int mid=(l+r)>>1;
        f[p].l=build(l,mid),f[p].r=build(mid+1,r);
        return p;
    }
    int modify(int p,int l,int r,int x,int y)
    {
        int now=++tot;
        f[now]=f[p];
        if(l==r)
        {
            f[now].val+=y;
            return now;
        }
        int mid=(l+r)>>1;
        if(x<=mid) f[now].l=modify(f[p].l,l,mid,x,y);
        else f[now].r=modify(f[p].r,mid+1,r,x,y);
        pushup(now);
        return now;
    }
    void dfs(int p,int f)//遍历整棵树并建主席树树
    {
        rt[p]=modify(rt[f],1,n,a[p],1);
        for(int i=hd[p];i;i=nxt[i])
        if(edge[i]!=f) dfs(edge[i],p);
    }
public:
    void init()
    {
        rt[0]=build(1,n);
        for(int i=1;i<=n;i++)
        if(!rt[i]) dfs(i,0);
    }
    void update(int p,int f)//递归暴力重建小树的主席树
    {
        rt[p]=modify(rt[f],1,n,a[p],1);
        for(int i=hd[p];i;i=nxt[i])
        if(edge[i]!=f) dfs(edge[i],p);
    }
    int query(int p,int q,int r,int s,int lp,int rp,int k)//查询第k大
    {
        if(lp==rp) return lp;
        int mid=(lp+rp)>>1;
        int val=f[f[p].l].val+f[f[q].l].val-f[f[r].l].val-f[f[s].l].val;
        if(k<=val) return query(f[p].l,f[q].l,f[r].l,f[s].l,lp,mid,k);
        else return query(f[p].r,f[q].r,f[r].r,f[s].r,mid+1,rp,k-val);
    }
    int& operator [](int x)
    {
        return rt[x];
    }
}f;
int main()
{
    read(t);
    read(n),read(m),read(t);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        read(u),read(v);
        add_edge(u,v),add_edge(v,u);
    }
    prework();
    LCA.init(),g.init(),f.init();
    for(int i=1;i<=t;i++)
    {
        char op[2];
        int x,y;
        scanf("%s",op);
        read(x),read(y);
        x^=lastans,y^=lastans;
        if(op[0]=='Q')
        {
            int k;
            read(k);
            k^=lastans;
            int l=LCA.query(x,y);
            write(lastans=mp2[f.query(f[x],f[y],f[l],f[LCA[l][0]],1,n,k)]),putchar('\n');
        }
        else
        {
            if(g[g.find(x)]<g[g.find(y)]) swap(x,y);
            g.Union(x,y),LCA.update(x,y),f.update(y,x);
        }
    }
	return 0;
}

洛谷 P3302 【SDOI2013】森林 题解

2020-3-5 xiaoh

题意

题解

题解

洛谷 P3302 【SDOI2013】森林题解