主题链接：
题意见白书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 100005struct 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]
版权声明：本文博客原创文章，博客，未经同意，不得转载。