题目描述
一天Blinker醒来，发现自己成为了一个二维世界的点，而且被标记上了一个奇怪的值。 这个世界是由N个边界互不相交（且不相切）的图形组成，这里图形仅包括圆和凸多边形。每个图形还有一个权值。每次Blinker走进或走出某个图形时（相切时经过不算），Blinker的标记值就会被异或上那个值。 现在，我们记录了Blinker在这个世界的M天的信息。每天可能发生两种事情，一种是某个图形的权值更改为某个值；另一种是Blinker从某个点走到另一个点。 我们假设Blinker首次出发前的标记值为0，我们希望知道他每次到达目的地后的标记
值。
输入格式
输入的第一行包含2个数，N和M，分别表示这个世界的图形数和记录的天数。 接下来有N行，每行表示一个图形。 如果一行以字符C开头，表示这个图形是一个圆，后面紧跟着三个实数x, y, r和一个整数v，分别表示圆的x坐标，y坐标和圆的半径以及该图形对应的值。 如果一行以字符P开头，表示这个图形是凸多边形，后面紧跟着一个整数L，表示凸多
边形的点数，然后后面有L对实数x0,y0,x1,y1…，表示L个点的坐标，这一行最后一个数是一个整数v，表示这个图形对应的值，保证凸多边形上的点按照顺时针给出。 接下来有M行，每行表示一天的记录信息。
如果一行以字符Q开头，表示这一天Blinker出行了，接下来有x0,y0,x1,y1四个实数，分别表示出发点的坐标和目的地的坐标。
如果一行以字符C开头，表示这一天某个图形的值改变了，接下来有两个i 和v，表示输入中第i 个出现的图形的值变成v。
输出格式
对于Blinker的每个出行输出他到达目的地后的标记值，很显然这个值与Blinker的路径无关。
提示
1<=N<=100000，1<=M<=100000，单个凸多边形的点数小于等于34。图形互不相交，且Blinker的出发点和目的地不在图形的边界。
题解：
- 由于只有包含和相离所以是一个树形结构，只需要找到每个图形的父亲建树；
- 询问即树链上的异或和，BIT维护即可；
- 将每个多边形分成上壳和下壳；
- 按$x$坐标扫描，图不相交，有个性质：一旦加入图形的上下关系就是确定的，$splay$维护$y$坐标的大小；
- 查询$(x,y)$可以直接在扫描到$x$的时候查找$y$的前驱，如果是下壳则就是查到的图形，否则是它的父亲；
- 点定位和图形定位都是这个思路；
- 我看的Claris的题解，自己写了，改了两天一直只有30，又不会造数据，不得已只能照着代码改成和$std$要像不像的才过了。。。。TAT
- 至今不知道自己错哪里了。。。。
#include<bits/stdc++.h>
#define ld double
using namespace std;
const int N=;
const ld inf=1e20,eps=1e-;
int n,m,cnt,tot,o=,hd[N],f[N],st[N],ed[N],idx,c[N],rt,ch[N<<][],fa[N<<],bl[N<<];
ld X;
struct Edge{int v,nt;}E[N<<];
char s[];
struct P{
ld x,y;
P(ld _x=,ld _y=):x(_x),y(_y){};
bool operator <(const P&a)const{return x==a.x?y<a.y:x<a.x;}
}q[N<<];
struct line{ld x;int id,typ;}B[N<<];
struct Graph{
int typ,w;
int n;P p[];
P O;ld R;
void init(){
scanf("%s",s+);
typ=s[]=='P';
if(!typ)scanf("%lf%lf%lf%d",&O.x,&O.y,&R,&w);
else{
scanf("%d",&n);
for(int j=;j<n;++j)scanf("%lf%lf",&p[j].x,&p[j].y);
scanf("%d",&w);
p[n]=p[];
}
}
ld getl(){
if(!typ)return O.x-R;
ld re=inf;
for(int i=;i<n;++i)re=min(re,p[i].x);
return re;
}
ld getr(){
if(!typ)return O.x+R;
ld re=-inf;
for(int i=;i<n;++i)re=max(re,p[i].x);
return re;
}
ld cal0(ld x){
if(!typ)return O.y+sqrt(max(R*R-(x-O.x)*(x-O.x),0.0));
ld re=-inf;
for(int i=;i<n;++i){
ld A=p[i].x,B=p[i].y,C=p[i+].x,D=p[i+].y;
if(A>C)swap(A,C),swap(B,D);
if(x<A-eps||x>C+eps)continue;
if(x<A+eps){re=max(re,B);continue;}
if(x>C-eps){re=max(re,D);continue;}
re=max(re,B+(D-B)/(C-A)*(x-A));
}
return re;
}
ld cal1(ld x){
if(!typ)return O.y-sqrt(max(R*R-(x-O.x)*(x-O.x),0.0));
ld re=inf;
for(int i=;i<n;++i){
ld A=p[i].x,B=p[i].y,C=p[i+].x,D=p[i+].y;
if(A>C)swap(A,C),swap(B,D);
if(x<A-eps||x>C+eps)continue;
if(x<A+eps){re=min(re,B);continue;}
if(x>C-eps){re=min(re,D);continue;}
re=min(re,B+(D-B)/(C-A)*(x-A));
}
return re;
}
}A[N];
struct Query{int typ,u,v,x;}C[N];
bool cmpB(const line&a,const line&b){
if(a.typ&&b.typ&&a.id==b.id)return a.typ>b.typ;
return a.x<b.x;
}
bool cmp1(int k,ld y){
if(k==(n<<|))return ;
if(k==(n<<))return ;
ld t=k&?A[k>>].cal1(X):A[k>>].cal0(X);
return t<y;
}
bool cmp2(int x,int y){
if(x==(n<<|))return ;
if(x==(n<<))return ;
if((x^y)==)return x&;
ld t1=x&?A[x>>].cal1(X):A[x>>].cal0(X),
t2=y&?A[y>>].cal1(X):A[y>>].cal0(X);
return t1<t2;
}
void rotate(int x,int&k){
int y=fa[x],z=fa[y];
if(y!=k)ch[z][ch[z][]==y]=x;else k=x;
int l=ch[y][]==x,r=l^;
fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;
ch[y][l]=ch[x][r],ch[x][r]=y;
}
void splay(int x,int&k){
for(int y,z;x!=k;rotate(x,k)){
y=fa[x],z=fa[y];
if(y!=k)rotate((ch[z][]==y)^(ch[y][]==x) ? x : y , k);
}
}
void adde(int u,int v){
E[o]=(Edge){v,hd[u]};
f[v]=u;hd[u]=o++;
}
void ins(int&k,int x){
if(!k){k=x;return;}
int d=cmp2(k,x);
ins(ch[k][d],x);
fa[ch[k][d]]=k;
}
int find(ld y){
int k=rt,re=;
while(k){
if(cmp1(k,y))re=k,k=ch[k][];
else k=ch[k][];
}return re;
}
void add(int x){
/*if(x==20193){
puts("haha");
}*/
int p=x<<,q=p|;
ins(rt,p);ins(rt,q);
splay(q,rt);
int t=ch[q][];
while(ch[t][])t=ch[t][];
adde(t&?t>>:f[t>>],x);
splay(t,rt);
}
void del(int x){
splay(x,rt);
int y=ch[x][];
while(ch[y][])y=ch[y][];
splay(y,ch[x][]);
ch[y][]=ch[x][];
fa[ch[x][]]=y;
fa[rt=y]=;
}
void getp(int x){
int t=find(q[x].y);
bl[x]=t&?t>>:f[t>>];
splay(t,rt);
}
void mfy(int x,int y){for(;x<=n;x+=x&-x)c[x]^=y;}
int ask(int x){int re=;for(;x;x-=x&-x)re^=c[x];return re;}
void upd(int x,int y){
swap(y,A[x].w);y^=A[x].w;
mfy(st[x],y);mfy(ed[x]+,y);
}
int que(int x){return ask(st[x]);}
void dfs(int u){
st[u]=++idx;
mfy(st[u],A[u].w);
for(int i=hd[u];i;i=E[i].nt)dfs(E[i].v);
ed[u]=idx;
mfy(ed[u]+,A[u].w);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("T3.in","r",stdin);
freopen("T3.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i){
A[i].init();
B[++cnt]=(line){A[i].getl(),i,};
B[++cnt]=(line){A[i].getr(),i,-};
}
for(int i=;i<=m;++i){
scanf("%s",s+);
C[i].typ=s[]=='Q';
if(!C[i].typ)scanf("%d%d",&C[i].u,&C[i].x);
else{
C[i].u=++tot,scanf("%lf%lf",&q[tot].x,&q[tot].y);
B[++cnt]=(line){q[tot].x,tot,};
C[i].v=++tot,scanf("%lf%lf",&q[tot].x,&q[tot].y);
B[++cnt]=(line){q[tot].x,tot,};
}
}
sort(B+,B+cnt+,cmpB);
++n;
ch[rt=n<<][]=n<<|;
fa[n<<|]=n<<;
for(int i=;i<=cnt;++i){
X=B[i].x;
if(B[i].typ==)add(B[i].id);
else if(B[i].typ==-)del(B[i].id<<),del(B[i].id<<|);
else getp(B[i].id);
}
dfs(n);
int ans=;
for(int i=;i<=m;++i)if(C[i].typ){
ans^=que(bl[C[i].u])^que(bl[C[i].v]);
printf("%d\n",ans);
}else upd(C[i].u,C[i].x);
return ;
}
#include<bits/stdc++.h>
#define ld double
using namespace std;
const int N=;
inline int M(int x,int y){return (x+y)%y;}
const ld eps=1e-;
int n,m,cnt,tot;
char s[];
struct P{
ld x,y;int id;
P(ld _x=,ld _y=,int _id=):x(_x),y(_y),id(_id){};
bool operator <(const P&a)const{return x==a.x?y<a.y:x<a.x;}
}q[N<<];
struct line{ld x;int id,typ;}B[N<<];
struct Graph{
int typ,w;
int n,t1,t2,l,r;P p[];
P O;ld R;
void init(int i){
scanf("%s",s+);
typ=s[]=='P';
if(!typ){
scanf("%lf%lf%lf%d",&O.x,&O.y,&R,&w);
B[++cnt]=(line){O.x-R,i,};
B[++cnt]=(line){O.x+R,i,-};
}
else{
scanf("%d",&n);
scanf("%lf%lf",&p[].x,&p[].y);
l=;r=;
for(int j=;j<n;++j){
scanf("%lf%lf",&p[j].x,&p[j].y);
if(p[j].x<p[l].x)l=j;
if(p[j].x>p[r].x)r=j;
}
t1=t2=l;
while(fabs(p[t1].x-p[M(t1+,n)].x)<eps)t1=M(t1+,n); //
while(fabs(p[t2].x-p[M(t2-,n)].x)<eps)t2=M(t2-,n); //
scanf("%d",&w);
B[++cnt]=(line){p[l].x,i,};
B[++cnt]=(line){p[r].x,i,-};
}
}
}A[N];
struct Query{
int typ;
int u,v,x;
void init(int i){
scanf("%s",s+);
typ=s[]=='Q';
if(!typ)scanf("%d%d",&u,&x);
else{
q[++tot].id=i<<;
scanf("%lf%lf",&q[tot].x,&q[tot].y);
q[++tot].id=i<<|;
scanf("%lf%lf",&q[tot].x,&q[tot].y);
}
}
}C[N];
bool cmpB(const line&a,const line&b){return fabs(a.x-b.x)<eps?a.typ>b.typ:a.x<b.x;}
ld cal(int k,ld x){
int i=k>>;
if(!A[i].typ){
P O = A[i].O;
ld d=sqrt(A[i].R*A[i].R - (x-O.x)*(x-O.x) + eps);//
return k&?O.y-d:O.y+d;
}else{
int&t=k&?A[i].t2:A[i].t1,ad=k&?-:;
while(t!=A[i].r&&A[i].p[M(t+ad,A[i].n)].x<x-eps)t=M(t+ad,A[i].n);//
P p1=A[i].p[t],p2=A[i].p[M(t+ad,A[i].n)];
return p1.y+(x-p1.x)/(p2.x-p1.x)*(p2.y-p1.y);
}
}
bool cmpA(int k,ld x,ld y){
if(k==(n<<|))return ;
if(k==(n<<))return ;
return cal(k,x)<=y;
}
namespace Splay{
int rt,ch[N<<][],fa[N<<];
void init(){
int p=n<<,q=n<<|;
ch[rt=p][]=q;
fa[q]=p;
}
void rotate(int x,int&k){
int y=fa[x],z=fa[y];
if(y!=k)ch[z][ch[z][]==y]=x;else k=x;
int l=ch[y][]==x,r=l^;
fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;
ch[y][l]=ch[x][r],ch[x][r]=y;
}
void splay(int x,int&k){
for(int y,z;x!=k;rotate(x,k)){
y=fa[x],z=fa[y];
if(y!=k)rotate((ch[z][]==y)^(ch[y][]==x) ? x : y , k);
}
}
int find(ld x,ld y){
int k=rt,re=;
while(k){
if(cmpA(k,x,y))re=k,k=ch[k][];
else k=ch[k][];
}splay(re,rt);
return re;
}
void ins(int i){
int t=ch[rt][];
while(ch[t][])t=ch[t][];
{
splay(t,ch[rt][]);
}
int p=i<<,q=p|;
ch[t][]=p;fa[p]=t;
ch[p][]=q;fa[q]=p;
{
splay(q,rt);
}
}
/*
void del(int i){
int p=i<<1,q=i<<1|1;
splay(p,rt);
splay(q,ch[p][0]);
int t=ch[q][0];
while(ch[t][1])t=ch[t][1];
splay(t,ch[q][0]);
ch[t][1]=ch[p][1];
fa[ch[p][1]]=t;
fa[rt=t]=0;
}
*/
void del(int x){
splay(x,rt);
int y=ch[x][];
while(ch[y][])y=ch[y][];
splay(y,ch[x][]);
ch[y][]=ch[x][];
fa[ch[x][]]=y;
fa[rt=y]=;
}
}
namespace BIT{
int o=,hd[N],fa[N],st[N],ed[N],idx,c[N];
struct Edge{int v,nt;}E[N];
void adde(int u,int v){E[o]=(Edge){v,hd[u]};hd[u]=o++;}
void add(int x,int y){for(;x<=n;x+=x&-x)c[x]^=y;}
int ask(int x){int re=;for(;x;x-=x&-x)re^=c[x];return re;}
void upd(int x,int y){
swap(y,A[x].w);y^=A[x].w;
add(st[x],y);add(ed[x]+,y);
}
int que(int x){return ask(st[x]);}
void dfs(int u){
st[u]=++idx;
add(st[u],A[u].w);
for(int i=hd[u];i;i=E[i].nt)dfs(E[i].v);
ed[u]=idx;
add(ed[u]+,A[u].w);
}
}
namespace IO{
int sta[],top;
char s[],*p=s;
void push(char x){
if(p==s+)fwrite(s,,,stdout),p=s;
*p++=x;
}
void write(int x){
if(!x){push('');push('\n');return;}
while(x)sta[++top]=x%,x/=;
while(top)push(sta[top--]^'');
push('\n');
}
void flush(){fwrite(s,,p-s,stdout);}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("nightmare.in","r",stdin);
freopen("nightmare.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)A[i].init(i);
for(int i=;i<=m;++i)C[i].init(i);
sort(B+,B+cnt+,cmpB);
sort(q+,q+tot+);
n++;Splay::init();
int j=;
for(int i=;i<=cnt;++i){
while(j<=tot&&q[j].x<=B[i].x){
int t=Splay::find(q[j].x,q[j].y),bl;
if(t&)bl=t>>;else bl=BIT::fa[t>>];
if(q[j].id&)C[q[j].id>>].v=bl;
else C[q[j].id>>].u=bl;
j++;
}
if(B[i].typ==){
int pos=B[i].id;
int t=Splay::find(B[i].x , A[pos].typ? A[pos].p[A[pos].l].y : A[pos].O.y);
if(t&)BIT::adde(t>>,pos),BIT::fa[pos]=t>>;
else BIT::adde(BIT::fa[t>>],pos),BIT::fa[pos]=BIT::fa[t>>];
Splay::ins(pos);
}else Splay::del(B[i].id<<),Splay::del(B[i].id<<|);
}
while(j<=tot){
if(q[j].id&)C[q[j].id>>].v=n;
else C[q[j].id>>].u=n;
j++;
}
BIT::dfs(n);
/*{
for(int i=1;i<n;++i)printf("%d\n",BIT::fa[i]==n?0:BIT::fa[i]);
}*/
int ans=;
for(int i=;i<=m;++i)if(C[i].typ){
int tmp=;
tmp^=BIT::que(C[i].u);
tmp^=BIT::que(C[i].v);
ans^=tmp;
IO::write(ans);
}else BIT::upd(C[i].u,C[i].x);
IO::flush();
return ;
}
(WA)