A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2733 永无乡 线段树合并
发表于: | 分类: Oi | 评论:0 | 阅读:50

题目描述BZ上的很清楚了……

$Solution$
大概就是一道思博数据结构题,做了几道发现,满满的都是套路……
首先,对于联通块的维护,就直接并查集就行了【为了秀速度,多写点也没什么
然后再合并块的时候可以直接权值线段树合并^权值线段树合并
然后查询的时候就比较一下 $size$ 和 $rank$ 的大小就行了,和 $Treap$ 啥的比较相像

然后就是裸题,都不用调试过样例就能过的裸题…………

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100000+5;
const int M = N << 5;

typedef long long LL;

int fa[N];
int T[N];
int size[N];

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

void Union(int x,int y)
{
    int fx = find(x),fy = find(y);
    if(fx == fy) return ;
    if(size[fx] < size[fy]) swap(fx,fy);
    fa[fy] = fx,size[fx] += size[fy];
}

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;

int tr[M],ls[M],rs[M],root[N];

inline void updata(int k)
{
    tr[k] = tr[ls[k]] + tr[rs[k]];
}

void change(int &k,int l,int r,int pos)
{
    if(!k) k = ++sz;
    if(l==r){tr[k]=1;return;}
    int mid = (l+r)>>1;
    if(pos <= mid) change(ls[k],l,mid,pos);
    else change(rs[k],mid+1,r,pos); updata(k);
}

int ask(int k,int l,int r,int size)
{
    if(l==r)return l;
    int mid = (l+r)>>1;
    if(tr[ls[k]] >= size) return ask(ls[k],l,mid,size);
    else return ask(rs[k],mid+1,r,size-tr[ls[k]]);
}

int merge(int x,int y)
{
    if(!x) return y;
    if(!y) return x;
    ls[x] = merge(ls[x],ls[y]);
    rs[x] = merge(rs[x],rs[y]);
    updata(x); return x;
}

int V[N];

int main()
{
    int n = read(), m = read();
    for(int i=1;i<=n;++i) V[i] = read(),size[fa[i] = i] = 1;
    for(int i=1;i<=m;++i) Union(read(),read());
    for(int i=1;i<=n;++i) change(root[find(i)],1,n,V[i]),T[V[i]] = i;
    int Q = read();char str[10];
    while(Q--)
    {
        scanf("%s",str);
        int x = read(),y = read();
        if(str[0] == 'Q')
        {
            int fx = find(x);
            if(tr[root[fx]] < y) {puts("-1");continue;}
            printf("%d\n",T[ask(root[fx],1,n,y)]);
        }
        else
        {
            int fx = find(x),fy = find(y);
            if(fx ^ fy)
            {
                fa[fy] = fx;
                root[fx] = merge(root[fx],root[fy]);
            }
        }
    }
}
Title - Artist
0:00

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

TOP