1455 - Kingdom

线段树 + 并查集：因为需要查找y值，所以x值不需要存储，然后就是给出的查询C，这个要注意，有可能超出y的范围；  
自己的思路是把y值翻倍，所以c值就可以变为整数进行查询。并查集是用来连接两棵子树的， 而线段树是把连接成的子树的y值区间进行更新，  
就是把以前的两棵子树的区间删除掉，把新的子树的区间加到线段树里面，然后就可以了  
//#pragma comment(linker, "/STACK:1024000000,1024000000")  
#include <iostream>  
#include <stack>  
#include <queue>  
#include <cstdio>  
#include <cstdlib>  
#include <cmath>  
#include <set>  
#include <vector>  
#include <cstring>  
#include <algorithm>  
  
#define INF 0x3fffffff  
#define N 100010  
#define M (2000010 << 2)  
#define LL long long  
#define mod 95041567  
  
using namespace std;  
  
struct Node{  
    int city, state;  
};  
  
int p[N], up[N], down[N], sum[N], Index[N];  
Node tree[M];  
  
int find(int x){  
    return p[x] == x ? x : p[x] = find(p[x]);  
}  
  
void update(int rt, int l, int r, int L, int R, int city, int state){  
    int lc = rt << 1;  
    int rc = lc + 1;  
    int mid = (r - l)/ 2 + l;  
    if(l == L && r == R){  
        tree[rt].city += city;  
        tree[rt].state += state;  
        return ;  
    }  
    if(L > mid) update(rc, mid + 1, r, L, R, city, state);  
    else if(R <= mid) update(lc, l, mid, L, R, city, state);  
    else {  
        update(rc, mid + 1, r, mid + 1, R, city, state);  
        update(lc, l, mid, L, mid, city, state);  
    }  
}  
  
void maintain(int u, int v, int l, int r){  
    p[v] = u;  
    if(down[v] != up[v] && sum[v] > 0) update(1, l, r, down[v], up[v], -sum[v], -1);  
    if(down[u] != up[u] && sum[u] > 0) update(1, l, r, down[u], up[u], -sum[u], -1);  
    sum[u] += sum[v];  
    sum[v] = 0;  
    up[u] = max(up[u], up[v]);  
    down[u] = min(down[u], down[v]);  
    if(up[u] != down[u] && sum[u] > 0) update(1, l, r, down[u], up[u], sum[u], 1);  
}  
  
void query(int rt, int l, int r, int L, int &ans1, int &ans2){  
    int mid = (r - l) / 2 + l;  
    int lc = rt << 1;  
    int rc = lc + 1;  
    if(l == r){  
        if(l != L) return ;  
        ans1 += tree[rt].state;  
        ans2 += tree[rt].city;  
        return ;  
    }  
    if(L > mid) query(rc, mid + 1, r, L, ans1 += tree[rt].state, ans2 += tree[rt].city);  
    else query(lc, l, mid, L, ans1 += tree[rt].state, ans2 += tree[rt].city);  
}   
  
int main() {  
  //  freopen("in.txt", "r", stdin);  
    int t;  
    scanf("%d", &t);  
    while(t -- ){  
        int n, m, l = INF, r = 0;  
        scanf("%d", &n);  
        for(int i = 0; i < n; ++ i){  
            int x, y;  
            scanf("%d %d", &x, &y);  
            p[i] = i;  
            up[i] = down[i] = 2 * y;  
            sum[i] = 1;  
            l = min(y * 2, l);  
            r = max(y * 2, r);  
        }  
        for(int i = 0; i < ((r + 10) << 2); ++ i) tree[i].city = tree[i].state = 0;  
        scanf("%d", &m);  
        for(int i = 0; i < m; ++ i){  
            char s[15];  
            scanf("%s", s);  
            if(s[0] == 'r'){  
                int u, v;  
                scanf("%d %d", &u, &v);  
                u = find(u);  
                v = find(v);  
                if(u == v) continue;  
                maintain(u, v, l, r);  
            }  
            else {  
                double f;  
                scanf("%lf", &f);  
                int ans1 = 0, ans2 = 0;  
                int c = int(f * 2.0);  
                if(c >= l && c <= r) query(1, l, r, c, ans1, ans2);  
                printf("%d %d\n", ans1, ans2);  
            }  
        }  
    }  
    return 0;  
}

补充：软件开发 , C++ ,