求助

回复帖子

@LiM_817  2019-01-29 10:37 回复

咋回事啊...调半天过了样例然后爆0...

有没有大佬帮忙看一眼啊...

fhq_treap + 启发式合并

#include <bits/stdc++.h>
#define dbg(x) cerr << #x " = " << x << "\n"
#define INF 0x3f3f3f3f

typedef long long LL;
typedef long double ld;
typedef unsigned long long ULL;

using namespace std;

template < typename T > inline void inp(T& t) {
    char c = getchar(); T x = 1; t = 0; while(!isdigit(c)) {if(c == '-') x = -1; c = getchar();}
    while(isdigit(c)) t = t * 10 + c - '0' , c = getchar();t *= x;
}
template < typename T , typename... Args > inline void inp(T& t , Args&... args) {inp(t); inp(args...);}
template < typename T > inline void outp(T t) {
    if(t < 0) putchar('-') , t = -t; T y = 10 , len = 1;
    while(y <= t) y *= 10 , len++; while(len--) y /= 10 , putchar(t / y + 48) , t %= y;
}
template < typename T > inline T mul(T x , T y , T MOD) {x=x%MOD,y=y%MOD;return ((x*y-(T)(((ld)x*y+0.5)/MOD)*MOD)%MOD+MOD)%MOD;}

const int MAXN = 100000 + 10;
struct fhq_treap {
    int val , rd , ls , rs , sz;
}t[MAXN]; 
int Nd , rt[MAXN] , f[MAXN];
int n , m;
int find(int x) {
    return x == f[x] ? f[x] : f[x] = find(f[x]);
}
void Pushup(int now) {
    t[now].sz = t[t[now].ls].sz + t[t[now].rs].sz + 1;
}
int NewNode(int val) {
    t[++Nd].val = val; t[Nd].rd = rand();
    t[Nd].ls = t[Nd].rs = 0; t[Nd].sz = 1;
    return Nd;
}
void split(int now , int& a , int& b , int val) {
    if(!now) {
        a = b = 0; return ;
    }
    if(t[now].val <= val) 
        a = now , split(t[now].rs , t[a].rs , b , val);
    else b = now , split(t[now].ls , a , t[b].ls , val);
    Pushup(now);
}
void merge(int& now , int a , int b) {
    if(!a || !b) {
        now = a + b;return ;
    }
    if(t[a].rd < t[b].rd) now = a , merge(t[now].rs , t[a].rs , b);
    else now = b , merge(t[now].ls , a , t[b].ls);
    Pushup(now);
}
int kth(int now , int k) {
    while(t[t[now].ls].sz + 1 != k) {
        if(t[t[now].ls].sz >= k) {
            now = t[now].ls; continue;
        }
        else if(t[t[now].ls].sz + 1 == k) return t[now].val;
        else {
            k -= t[t[now].ls].sz; k--;
            now = t[now].rs;
        }
    }
    return t[now].val;
}

void insert(int x , int val) {
    int z1 , z2;
    split(x , z1 , z2 , val);
    int z3 = NewNode(val); 
    merge(z1 , z1 , z3);
    merge(x , z1 , z2);
}
void dfs(int u , int v) {
    if(!v) return ;
    dfs(u , t[v].ls);
    insert(u , t[v].val);
    dfs(u , t[v].rs);
}
void Merge(int u , int v) {
    if(find(u) == find(v)) return ;
    if(t[rt[find(u)]].sz < t[rt[find(v)]].sz) swap(u , v);
    dfs(rt[find(u)] , rt[find(v)]);
    rt[find(v)] = rt[find(u)]; 
    f[find(v)] = find(u);
}
int rk[MAXN];
int main() {
    inp(n , m);
    for(int i = 1; i <= n; i++) { f[i] = i;
        int v; inp(v);
        rt[i] = NewNode(v); rk[v] = i;
    }

    for(int i = 1; i <= m; i++) {
        int a , b; inp(a , b);
        Merge(a , b); 
    }
    //cout << kth(rt[find(1)] , 1) << "DD\n";
    int q; inp(q);
    while(q--) {
        char s[3]; scanf("%s" , s);
        int x , y; inp(x , y);
        if(s[0] == 'B') {
            Merge(x , y);
        }
        else if(s[0] == 'Q') {
            if(t[rt[find(x)]].sz < y) puts("-1");
            else outp(rk[kth(rt[find(x)] , y)]) , puts("");
        }
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。