题目链接：点击打开链接

题意见白书P248

思路：

先把读入的y值都扩大2倍变成整数

然后离散化一下

用线段树来维护y轴 区间上每个点的 城市数量和联通块数量，

然后用并查集维护每个联通块及联通块的最大最小y值，还要加并查集的秩来记录每个联通块的点数

然后就是模拟搞。。

T^T绝杀失败题。。似乎数组开小了一点就过了，==

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; #define rank Rank #define L(x) (x<<1) #define R(x) (x<<1|1) #define Lson(x) tree[x].l #define Rson(x) tree[x].r #define Sum0(x) tree[x].sum[0] #define Lazy0(x) tree[x].lazy[0] #define Sum1(x) tree[x].sum[1] #define Lazy1(x) tree[x].lazy[1] inline int Mid(int x, int y){return (x+y)>>1;} #define N 100005 struct Point{ int x, y; }p[100005]; struct que{ int u, v, op; }Q[200005]; vector
       
        G; int n, q; char s[10]; struct node{ int l, r, sum[2], lazy[2]; }tree[N<<4]; void push_down(int id){ if(Lazy1(id)) { Sum1(L(id)) += Lazy1(id); Sum1(R(id)) += Lazy1(id); Lazy1(L(id)) += Lazy1(id); Lazy1(R(id)) += Lazy1(id); Lazy1(id) = 0; } if(Lazy0(id)) { Sum0(L(id)) += Lazy0(id); Sum0(R(id)) += Lazy0(id); Lazy0(L(id)) += Lazy0(id); Lazy0(R(id)) += Lazy0(id); Lazy0(id) = 0; } } void push_up(int id){Sum0(id) = Sum0(L(id)) + Sum0(R(id));Sum1(id) = Sum1(L(id)) + Sum1(R(id));} void build(int l, int r, int id){ Lson(id) = l; Rson(id) = r; Sum0(id) = Lazy0(id) = Sum1(id) = Lazy1(id) = 0; if(l == r) return ; int mid = Mid(l, r); build(l, mid, L(id)); build(mid+1, r, R(id)); } void updata(int l, int r, int val, int now, int id){ push_down(id); if(l == Lson(id) && Rson(id) == r) { if(now==0)Sum0(id) += val, Lazy0(id) += val; else Sum1(id) += val, Lazy1(id) += val; return ; } int mid = Mid(Lson(id), Rson(id)); if(mid < l) updata(l, r, val, now, R(id)); else if(r <= mid) updata(l, r, val, now, L(id)); else { updata(l, mid, val, now, L(id)); updata(mid+1, r, val, now, R(id)); } push_up(id); } int query(int pos, int now, int id){ push_down(id); if(Lson(id)==Rson(id))if(now==0)return Sum0(id); else return Sum1(id); int mid = Mid(Lson(id), Rson(id)); int ans; if(mid < pos) return query(pos, now, R(id)); else return query(pos, now, L(id)); } int f[100005], rank[100005], S[100005], X[100005]; //每个集合的上下界 int find(int x){return x==f[x]?x:f[x] = find(f[x]);} void Union(int x, int y){ int fx = find(x), fy = find(y); if(fx == fy)return; if(S[fx] > S[fy]) swap(fx, fy); if(S[fx] <= X[fy]){ updata(S[fx], X[fy], 1, 0, 1); updata(S[fx], X[fy], rank[fx] + rank[fy], 1, 1); updata(X[fx], S[fx], rank[fy], 1, 1); updata(X[fy], S[fy], rank[fx], 1, 1); } else if(X[fx] >= X[fy]) { updata(X[fx], S[fx], -1, 0, 1); updata(X[fy], X[fx], rank[fx], 1, 1); updata(S[fx], S[fy], rank[fx], 1, 1); } else { updata(X[fy], S[fx], -1, 0, 1); updata(X[fx], X[fy], rank[fy], 1, 1); updata(S[fx], S[fy], rank[fx], 1, 1); } if(rank[fy]