A simple Blog for wyx I've been down the bottle hoping.
BZOJ 3123 [SDOI2013] 森林 主席树 启发式合并
发表于: | 分类: Oi | 评论:0 | 阅读:122

写在前面:如果你莫名re,请先看讨论版。可能会发现一些奇怪的问题

今天本来数据结构写的挺顺手的,看到旁边的 $Alex$ Re了,我就点开看看……本来挺简单的题,结果差点GG

给定一个森林,给定两个操作,第一个是查询两点间的权值第 $K$ 小,第二种是连接两个点,保证任意一个时刻该图都是森林或者树

首先如果只有第一个操作那就是裸地cot ,但是他现在要求连接两个顶点,开始的时候以为这题还带删除一条边,还想是不是树套树,后来仔细一看没有这个操作,那这个东西就比较裸了
首先第一个感觉是离线+线段树合并,好像按照时间序合并也没什么不可以,不知道有没有这么写的

然后就是启发式合并主席树了,由于是启发式合并,也就是说我们每次暴力拆掉小的数据结构,然后粘到大的上面。
来计算一下这个时间复杂度吧
首先一种极限情况是每个东西都比较小,我们相当于每次只需要拆掉一个东西插入一个东西,均摊复杂度下来一个东西一次插入就是美妙的 $O(nlog(n))$
另外一种情况就是每次合并的东西都等大,那显然每次合并之后规模都会减小一半,也就是说一个东西最多被插入 $log$ 次,再被拆开 $log$ 次,而每一次的操作都是 $log$ 的,时间复杂度就是 $nlog^2n$
对于启发式合并维护size,可以借助并查集
第一次写的时候不知道错哪了无限Re,现在再思考一下可能是拒绝了并查集强心维护的锅

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 80000+5;
const int M = N << 1;
const int Maxm = 32*17*N;
using namespace std;

int head[N],tot,size[N];
int tr[Maxm],ls[Maxm],rs[Maxm];
int depth[N],fa[N][18],val[N];
int root[N],q[N],a[N],T[N],F[N];

struct graph
{
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];

inline void add(int x,int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y);
    head[x] = cnt;
    edge[++cnt] = graph(head[y],x);
    head[y] = cnt;
}

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int sz;

void insert(int L,int R,int x,int &y,int pos)
{
    y = ++sz; ls[y] = ls[x],rs[y] = rs[x]; tr[y] = tr[x] + 1;
    if(L==R) return;
    int mid = (L+R) >> 1;
    if(pos <= mid)insert(L,mid,ls[x],ls[y],pos);
    else insert(mid+1,R,rs[x],rs[y],pos);
}

int ask(int L,int R,int k1,int k2,int k3,int k4,int pos)
{
    if(L==R) return T[L];
    int mid = (L+R) >> 1;
    if(tr[ls[k3]]+tr[ls[k4]]-tr[ls[k1]]-tr[ls[k2]] >= pos)return ask(L,mid,ls[k1],ls[k2],ls[k3],ls[k4],pos);
    else return  ask(mid+1,R,rs[k1],rs[k2],rs[k3],rs[k4],pos-(tr[ls[k3]]+tr[ls[k4]]-tr[ls[k1]]-tr[ls[k2]]));
}

int Lca(int x,int y)
{
    if(depth[x] < depth[y]) swap(x,y);
    int tt = depth[x] - depth[y];
    for(int i=17;~i;--i)
        if((1<<i) & tt) x = fa[x][i];
    if(x == y) return x;
    for(int i=17;~i;--i)
        if(fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

void init(int x)
{
    for(int j=1;j<=17;++j)
        fa[x][j] = fa[fa[x][j-1]][j-1];
}

void DFS(int x)
{
    int l = 1, r = 0;
    q[++r] = x;
    while(l<=r)
    {
        int tt = q[l++]; 
        init(tt);
        insert(1,tot,root[fa[tt][0]],root[tt],a[tt]);
        for(int i=head[tt];i;i=edge[i].next)
            if(edge[i].to != fa[tt][0])
            {
                fa[edge[i].to][0] = tt;
                depth[edge[i].to] = depth[tt]  + 1;
                q[++r] = edge[i].to;
            }
    }
}

inline int find(int x)
{
    return F[x] ^ x ? F[x] = find(F[x]) : F[x];
}

int testcase;

int main()
{
    cin >> testcase;
    int n = read(), m = read(), q = read();
    for(int i=1;i<=n;++i) a[i] = T[i] = read();
    sort(T+1,T+n+1);
    for(int i=1;i<=n;++i) if(T[i] != T[i-1]) T[++tot] = T[i];
    for(int i=1;i<=n;++i) a[i] = lower_bound(T+1,T+tot+1,a[i]) - T;
    for(int i=1;i<=n;++i) size[F[i] = i] = 1;
    for(int i=1;i<=m;++i)
    {
        int x = read(), y = read(); add(x,y);
        int fx = find(x), fy = find(y);
        if(fx != fy)
        {
            if(size[fx] < size[fy]) swap(fx,fy);
            size[fx] += size[fy]; F[fy] = fx;
        }
    }
    for(int i=1;i<=n;++i)
        if(!root[i])
            DFS(i);
    char str[10];
    int lastans = 0;
    for(int i=1;i<=q;++i)
    {
        scanf("%s",str);
        if(str[0] == 'Q')
        {
            int x = read() ^ lastans, y = read()^lastans, K = read()^lastans;
            int tmp1 = Lca(x,y) , tmp2 = fa[tmp1][0];
            printf("%d\n",lastans = ask(1,tot,root[tmp1],root[tmp2],root[x],root[y],K));
        }
        else
        {
            int x = read()^lastans, y = read()^lastans;
            int fx = find(x), fy = find(y);
            add(x,y);
            if(size[fx] < size[fy])
                swap(fx,fy),swap(x,y);
            F[fy] = fx, size[fx] += size[fy];
            fa[y][0] = x; depth[y] = depth[x] + 1;
            DFS(y);
        }
    }
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP