不是很懂为什么这份代码不开O2 AC开了就全RE

回复帖子

@ZCDHJ 2018-12-02 21:44 回复

RT,求助 线段树合并

#include <iostream>
#include <cstdio>

const int MAXN = 1e5;

int n, m;
int fset[MAXN | 1], a[MAXN | 1];

inline int read() {
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) { 
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}

namespace Segtree {
    struct Segtree {
        int sumv;
        Segtree *ch[2];
        Segtree(Segtree *ch0 = NULL, Segtree *ch1 = NULL, int _sumv = 0) : sumv(_sumv) {
            ch[0] = ch0;
            ch[1] = ch1;
        }
    } *root[MAXN | 1];
    inline int sumv(Segtree *o) { return o == NULL ? 0 : o -> sumv; }
    void insert(Segtree *&o, int pos, int l = 1, int r = n) {
        if(o == NULL) o = new Segtree;
        ++(o -> sumv);
        if(l == r) return;
        int mid = (l + r) >> 1;
        pos <= mid ? insert(o -> ch[0], pos, l, mid) : insert(o -> ch[1], pos, mid + 1, r);
    }
    int kth(Segtree *o, int k, int l = 1, int r = n) {
        if(k > sumv(o)) return -1;
        if(l == r) return l;
        int mid = (l + r) >> 1;
        if(sumv(o -> ch[0]) >= k) return kth(o -> ch[0], k, l, mid);
        else return kth(o -> ch[1], k - sumv(o -> ch[0]), mid + 1, r);
    }
    Segtree *merge(Segtree *x, Segtree *y, int l = 1, int r = n) {
        if(x == NULL) return y;
        if(y == NULL) return x;
        if(l == r) return new Segtree(NULL, NULL, x -> sumv + y -> sumv);
        int mid = (l + r) >> 1;
        return new Segtree(merge(x -> ch[0], y -> ch[0], l, mid), merge(x -> ch[1], y -> ch[1], mid + 1, r), x -> sumv + y -> sumv);
    }
}

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

inline void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    fset[y] = x;
    Segtree::root[x] = Segtree::merge(Segtree::root[x], Segtree::root[y]);
}

inline int query(int x, int y) {
    x = find(x);
    int res = Segtree::kth(Segtree::root[x], y);
    return res == -1 ? -1 : a[res];
}

int main() {
    n = read();
    m = read();
    for(int i = 1; i <= n; ++i) {
        int tmp = read();
        a[tmp] = i;
        Segtree::insert(Segtree::root[i], tmp);
        fset[i] = i;
    }
    for(int i = 1; i <= m; ++i) merge(read(), read());
    for(int q = read(); q >= 1; --q) {
        char ch = getchar();
        while(ch < 'A' || ch > 'Z') ch = getchar();
        int a = read(), b = read();
        if(ch == 'Q') printf("%d\n", query(a, b));
        else merge(a, b);
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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