并查集维护：y的最大最小值、城市数量
线段树维护：城市数量，洲数量
合并两个集合时，先在线段树上删除两个子集合的旧的信息，然后再将合并完的新集合更新到线段树。
//#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<iostream> #include<sstream> #include<cmath> #include<climits> #include<string> #include<map> #include<queue> #include<vector> #include<stack> #include<set> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define pb(a) push_back(a) #define INF 0x1f1f1f1f #define lson idx<<1,l,mid #define rson idx<<1|1,mid+1,r #define PI 3.1415926535898 template<class T> T min(const T& a,const T& b,const T& c) { return min(min(a,b),min(a,c)); } template<class T> T max(const T& a,const T& b,const T& c) { return max(max(a,b),max(a,c)); } void debug() { #ifdef ONLINE_JUDGE #else freopen("d:\in.txt","r",stdin); // freopen("d:\out1.txt","w",stdout); #endif } int getch() { int ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!=' ')return ch; } return EOF; } const int maxn=1001000; const int N=100100; struct Tree { int add1[maxn<<2],add2[maxn<<2]; int build() { memset(add1,0,sizeof(add1)); memset(add2,0,sizeof(add2)); return 0; } int update(int idx,int l,int r,int tl,int tr,int ad1,int ad2) { if(tl<=l&&tr>=r) { add1[idx]+=ad1; add2[idx]+=ad2; return 0; } int mid=(r+l)>>1; if(tl<=mid)update(lson,tl,tr,ad1,ad2); if(tr>mid)update(rson,tl,tr,ad1,ad2); return 0; } int query(int idx,int l,int r,int pos,int &a,int &b) { a+=add1[idx]; b+=add2[idx]; if(l==r)return 0; int mid=(r+l)>>1; if(pos<=mid)query(lson,pos,a,b); else query(rson,pos,a,b); return 0; } }tree; struct union_find { int maxv[N],minv[N],num[N]; int da[N]; void init(int *y,int n) { for(int i=0;i<n;i++) { da[i]=i; minv[i]=maxv[i]=y[i]; num[i]=1; } } int find(int a) { return a==da[a]?a:da[a]=find(da[a]); } void merge(int a,int b) { int fa=find(a),fb=find(b); if(fa!=fb) { if(maxv[fa]>minv[fa])tree.update(1,0,1000000,minv[fa],maxv[fa]-1,-num[fa],-1); if(maxv[fb]>minv[fb])tree.update(1,0,1000000,minv[fb],maxv[fb]-1,-num[fb],-1); num[fa]+=num[fb]; maxv[fa]=max(maxv[fa],maxv[fb]); minv[fa]=min(minv[fa],minv[fb]); da[fb]=fa; if(maxv[fa]>minv[fa])tree.update(1,0,1000000,minv[fa],maxv[fa]-1,num[fa],1); } } }uf; int x[N],y[N]; int main() { int t; scanf("%d",&t); for(int ca=1;ca<=t;ca++) { int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d",&x[i],&y[i]); uf.init(y,n); tree.build(); int m; scanf("%d",&m); for(int i=1;i<=m;i++) { char op[10]; scanf("%s",op); if(op[0]=='r') { int u,v; scanf("%d%d",&u,&v); uf.merge(u,v); }else { int a=0,b=0; int pos; scanf(" %d.%*d",&pos); tree.query(1,0,1000000,pos,a,b); printf("%d %d ",b,a); } } } return 0; }