一道强行二合一题。

首先根据题目中图形不交的性质，想到建树，每个图形的父亲表示包含其的最小图形。

建树的过程可以用扫描线。

一条与 $y$ 轴平行的直线与某个图形至多有两个交点，其中 $y$ 坐标小的所有点称为上边界，$y$ 坐标大的称为下边界。

给定直线的 $x$ 坐标如何求交点的纵坐标？圆可以直接套解析式，多边形可以枚举每条边判断，或者二分。此题点数不超过 $34$ 所以代码中是枚举。

从左到右扫描，在一个图形的左端点加入上下边界，右端点删除。

根据图形不交的性质，求一个图形的父亲相当于求其某个顶点所在的最小图形。

将所有边界按 $y$ 坐标排序，二分找到这个点下方的第一个边界。如果是图形 $i$ 的上边界，则所求为 $fa_i$；如果是下边界，则所求为 $i$。

需要支持插入删除求后继，用 set 实现。

建出树之后，问题转化为单点修改，求某个点到根路径异或和。

求前缀异或之后，相当于子树异或一个值，单点查询，dfs 序 + 树状数组即可。

时间复杂度 $O((nl+m)\log n)$ 或者 $O((n\log l+m)\log n)$，取决于求交点的方式。

#include<bits/stdc++.h>
using namespace std;
using db=double;
const db eps=1e-7;
const int N=1e5+3,M=N*3;
db w,u;
struct C{//圆
	db x,y,r;
	void in(){scanf("%lf%lf%lf",&x,&y,&r),r=max(r,eps);}
	db up(){return y-sqrt(abs(r*r-(x-w)*(x-w)));}
	db dn(){return y+sqrt(abs(r*r-(x-w)*(x-w)));}
};
struct P{//多边形
	int l;db x[37],y[37];
	void in(){
		scanf("%d",&l);
		for(int i=0;i<l;++i)scanf("%lf%lf",x+i,y+i);
		x[l]=x[0],y[l]=y[0];
	}
	db up(){
		db r=1e99;
		for(int i=0;i<l;++i)if((x[i]-eps<w&&x[i+1]+eps>w)||(x[i+1]-eps<w&&x[i]+eps>w))r=min(r,abs(x[i]-x[i+1])<eps?min(y[i],y[i+1]):(y[i+1]-y[i])/(x[i+1]-x[i])*(w-x[i])+y[i]);
		return r;
	}
	db dn(){
		db r=-1e99;
		for(int i=0;i<l;++i)if((x[i]-eps<w&&x[i+1]+eps>w)||(x[i+1]-eps<w&&x[i]+eps>w))r=max(r,abs(x[i]-x[i+1])<eps?max(y[i],y[i+1]):(y[i+1]-y[i])/(x[i+1]-x[i])*(w-x[i])+y[i]);
		return r;
	}
};
struct G{//图形
	bool o;C c;P p;
	void in(){char t;scanf(" %c",&t),t=='C'?c.in():(o=1,p.in());}
	db up(){return o?p.up():c.up();}
	db dn(){return o?p.dn():c.dn();}
}g[N];
db get(int x){return x<M?(x<N?g[x].up():g[x-N].dn()):u;}
struct cmp{
	bool operator()(int x,int y)const{
		if(x+N==y||y+N==x)return x<y;
		return get(x)<get(y);
	}
};
struct D{//点
	db x,y;int id,o;
	bool operator<(D a)const{return x<a.x;}
}d[M];
struct Q{bool o;int u,v;}q[N];//询问
set<int,cmp>s;
int v[N],sv[N],fa[N],n,id,l[N],r[N],t[N];
basic_string<int>e[N];
void dfs(int x){for(int i:e[x])l[i]=++id,sv[i]=sv[x]^v[i],dfs(i),r[i]=id+1;}
void add(int x,int v){for(;x<=n;x+=x&-x)t[x]^=v;}
int sum(int x){int r=0;for(;x;x-=x&-x)r^=t[x];return r;}//树状数组部分
int main(){
	int m,i,j,k,t=0,ans=0;
	char c;
	db x0,y0,x1,y1;
	scanf("%d%d",&n,&m),g[0].c.r=1e99;
	for(i=1;i<=n;++i)if(g[i].in(),scanf("%d",v+i),g[i].o){
		for(j=0,x0=1e99,x1=-1e99;j<g[i].p.l;++j){
			if(x0>g[i].p.x[j])x0=g[i].p.x[j],y0=g[i].p.y[j];
			if(x1<g[i].p.x[j])x1=g[i].p.x[j],y1=g[i].p.y[j];
		}
		d[++t]={x0,y0,i,0},d[++t]={x1,y1,i,3};
	}else d[++t]={g[i].c.x-g[i].c.r,g[i].c.y,i,0},d[++t]={g[i].c.x+g[i].c.r,g[i].c.y,i,3};
	for(i=1;i<=m;++i)if(scanf(" %c",&c),c=='Q')scanf("%lf%lf%lf%lf",&x0,&y0,&x1,&y1),d[++t]={x0,y0,i,1},d[++t]={x1,y1,i,2};
	else q[i].o=1,scanf("%d%d",&q[i].u,&q[i].v);
	for(sort(d+1,d+t+1),s.insert(0),s.insert(N),i=1;i<=t;++i)if(k=d[i].id,d[i].o>2)s.erase(k),s.erase(k+N);else{
		w=d[i].x,u=d[i].y,j=*s.upper_bound(M),j=j<N?fa[j]:j-N;
		if(!d[i].o)fa[k]=j,e[j]+=k,s.insert(k),s.insert(k+N);
		else if(d[i].o==1)q[k].u=j;else q[k].v=j;
	}//扫描线部分
	for(dfs(0),i=1;i<=m;++i)if(q[i].o)j=q[i].u,k=q[i].v^v[j],v[j]=q[i].v,add(l[j],k),add(r[j],k);
	else printf("%d\n",ans^=sv[q[i].u]^sv[q[i].v]^sum(l[q[i].u])^sum(l[q[i].v]));
	return 0;
}