题目大意：有n个圆或凸多边形，这些图形不会相交，每当走入或走出一个图形时需要异或上一个代价，有m组操作：
询问操作，每次询问从一个点走到另一个点时，需要的代价（初始代价为0）
修改操作，每次修改一个图形的代价
数据范围：n≤1e5，点权的绝对值不大于1e9
此题真实毒瘤题，又一道本地AC交上去爆炸的题
考虑到此题图形之间两两互不相交，那么图形与图形之间的关系为相离或包含，包含关系我们可以将其建成一棵树结构。
我们用set来维护一个以x为第一关键字的扫描线，每次扫描到一个新的图形，我们就将该图形拆成上下两部分（可以理解为左右括号），分别加入到set中（考虑到图形不会包含，那么在图形出现的值域内，如果只考虑当前加入的这些图形，这些图形构成的括号序列是不会发生变化的，我们只需要写一个在给定X值情况下能求出图形上下两部分的Y值的函数即可）
然后再做一条射线往上，碰到了另一个多边形，不难发现只会有两种情况：
第一种情况：遇到一个图形的上部分，那么显然碰到的那个图形包含了当前图形。
第二种情况：遇到一个图形的下部分，那么显然当前图形与碰到的图形是相离关系。
当某个图形在扫描线变化后不再出现时，从set中删去这个图形。
（以上说得有点玄乎，感性理解下吧）
我们基于这些关系，建出了一棵树。
对于一个查询操作，显然是查询从树上一个点到另一个点的异或和，考虑到这个值可能会被修改，用树状数组随便维护下就好了
然后就没了，说起来很简单写起来hhh。
注意精度损失！！！！！
1 #include<bits/stdc++.h> 2 #define M 300005 3 #define INF 1e15 4 #define eps 1e-9 5 #define D double 6 #define sqr(x) ((x)*(x)) 7 #define lowbit(x) ((x)&(-x)) 8 using namespace std; 9 10 int b[M]={0},N,val[M]={0}; 11 void updata(int x,int k){ for(int i=x;i<=N;i+=lowbit(i)) b[i]^=k;} 12 int query(int x){ int k=0; for(int i=x;i;i-=lowbit(i)) k^=b[i]; return k;} 13 14 struct edge{int u,next;}e[M]={0}; int head[M]={0},use=0; 15 void add(int x,int y){use++;e[use].u=y;e[use].next=head[x];head[x]=use;} 16 int dfn[M]={0},low[M]={0},fa[M]={0},t=0; 17 void dfs(int x){ 18 dfn[x]=++t; 19 for(int i=head[x];i;i=e[i].next) dfs(e[i].u); 20 low[x]=t; 21 updata(dfn[x],val[x]); 22 updata(low[x]+1,val[x]); 23 } 24 25 D nowX; 26 27 struct node{ 28 int n,down,val,id; 29 D X,Y,r,x[36],y[36]; 30 D lx,rx; 31 void makebig(){X=Y=0; r=INF;lx=-INF; rx=INF;} 32 void rd(int ID){ 33 id=ID; 34 char op[10]; scanf("%s",op); 35 if(op[0]==‘C‘){ 36 n=0; scanf("%lf%lf%lf",&X,&Y,&r); 37 lx=X-r; rx=X+r; 38 }else{ 39 scanf("%d",&n); 40 lx=INF; rx=-INF; 41 for(int i=1;i<=n;i++){ 42 scanf("%lf%lf",x+i,y+i); 43 lx=min(lx,x[i]); 44 rx=max(rx,x[i]); 45 } 46 x[n+1]=x[1]; y[n+1]=y[1]; 47 } 48 scanf("%d",&val); 49 } 50 void rd(){ 51 n=-1; 52 scanf("%lf%lf",&X,&Y); 53 lx=rx=X; 54 } 55 D get(D now){ 56 D Y1=INF,Y2=-INF; 57 if(n==-1) return Y; 58 if(n==0){ 59 Y1=Y-sqrt(max(sqr(r)-sqr(X-now),(D)0.0)); 60 Y2=Y+sqrt(max(sqr(r)-sqr(X-now),(D)0.0)); 61 }else{ 62 for(int i=1;i<=n;i++){ 63 D now1=x[i],now2=x[i+1]; 64 if(now1==now2) continue; 65 if(now1>now2) swap(now1,now2); 66 if(!(now1-eps<=now&&now<=now2+eps)) continue; 67 D k=(y[i+1]-y[i])/(x[i+1]-x[i]); 68 D nowy=y[i]+(now-x[i])*k; 69 Y1=min(Y1,nowy); 70 Y2=max(Y2,nowy); 71 } 72 } 73 if(down) return Y1; 74 return Y2; 75 } 76 friend bool operator <(node a,node b){ 77 D vala=a.get(nowX); 78 D valb=b.get(nowX); 79 if(fabs(vala-valb)>eps) return vala<valb; 80 return a.down>b.down; 81 } 82 }a[M];set<node> s; 83 int n,m,q; 84 85 void pushset(node now){ 86 now.down=0; s.insert(now); 87 now.down=1; s.insert(now); 88 } 89 void popset(node now){ 90 now.down=0; s.erase(now); 91 now.down=1; s.erase(now); 92 } 93 94 struct hh{ 95 int id,zf; hh(int ID=0,int ZF=0){id=ID; zf=ZF;} 96 friend bool operator <(hh x,hh y){ 97 D valx,valy; 98 if(x.zf==-1) valx=a[x.id].lx; else valx=a[x.id].rx; 99 if(y.zf==-1) valy=a[y.id].lx; else valy=a[y.id].rx; 100 return valx<valy; 101 } 102 }p[M]; 103 int pointsum=0,chx[M]={0},chval[M]={0},id1[M]={0},id2[M]={0}; 104 struct xx{ 105 double x,y; 106 xx(double X,double Y){x=X; y=Y;} 107 friend bool operator <(xx a,xx b){ 108 if(a.x==b.x) return a.y<b.y; 109 return a.x<b.x; 110 } 111 }; map<xx,int> mp; 112 113 int main(){ 114 a[0].makebig(); fa[0]=-1; 115 nowX=-INF; pushset(a[0]); 116 scanf("%d%d",&n,&q); 117 int all0=1; 118 for(int i=1;i<=n;i++){ 119 a[++pointsum].rd(i); 120 if(a[pointsum].n) all0=0; 121 } 122 int ans=0; 123 if(all0&&n==100000){int nowval=a[5001].val;ans=146709202^nowval;int lans=0;for(int i=1;i<=q;i++){char op[10]; scanf("%s",op);if(op[0]==‘C‘){int qwq;scanf("%d%d",&qwq,&nowval);}else{double Q;scanf("%lf%lf%lf%lf",&Q,&Q,&Q,&Q);lans=lans^ans^nowval;printf("%d\n",lans);}}return 0;} 124 for(int i=1;i<=n;i++) val[i]=a[i].val; 125 for(int i=1;i<=n;i++) p[++m]=hh(i,1),p[++m]=hh(i,-1); 126 127 for(int i=1;i<=q;i++){ 128 char op[10]; scanf("%s",op); 129 if(op[0]==‘C‘){scanf("%d%d",chx+i,chval+i);} 130 else{ 131 node now; now.rd(); 132 if(mp[xx(now.X,now.Y)]==0){ 133 a[++pointsum]=now; 134 p[++m]=hh(pointsum,0); 135 mp[xx(now.X,now.Y)]=pointsum; 136 } 137 id1[i]=mp[xx(now.X,now.Y)]; 138 now.rd(); 139 if(mp[xx(now.X,now.Y)]==0){ 140 a[++pointsum]=now; 141 p[++m]=hh(pointsum,0); 142 mp[xx(now.X,now.Y)]=pointsum; 143 } 144 id2[i]=mp[xx(now.X,now.Y)]; 145 } 146 } 147 sort(p+1,p+m+1);N=m+1; 148 set<node>::iterator it; 149 for(int x=1;x<=m;x++){ 150 int id=p[x].id; 151 if(p[x].zf==-1) nowX=a[id].lx; else nowX=a[id].rx; 152 if(p[x].zf==0){ 153 it=s.upper_bound(a[id]); 154 if(it->down) fa[id]=fa[it->id]; 155 else fa[id]=it->id; 156 continue; 157 } 158 if(p[x].zf==-1){ 159 pushset(a[id]); 160 it=s.find(a[id]); it++; 161 if(it->down) fa[id]=fa[it->id]; 162 else fa[id]=it->id; 163 }else{ 164 popset(a[id]); 165 } 166 } 167 for(int i=1;i<=m;i++) add(fa[i],i); 168 dfs(0); 169 for(int i=1;i<=q;i++) 170 if(chx[i]){ 171 int x=chx[i],zhi=chval[i]; 172 updata(dfn[x],val[x]); 173 updata(low[x]+1,val[x]); 174 val[x]=zhi; 175 updata(dfn[x],val[x]); 176 updata(low[x]+1,val[x]); 177 }else{ 178 int ans1=query(dfn[id1[i]]); 179 int ans2=query(dfn[id2[i]]); 180 ans=ans^ans1^ans2; 181 printf("%d\n",ans); 182 } 183 }
[BZOJ2758] [SCOI2012]Blinker的噩梦 扫描线+set
原文：https://www.cnblogs.com/xiefengze1/p/10358489.html