首页 > 代码库 > BZOJ 2758 Blinker的噩梦(扫描线+熟练剖分+树状数组)
BZOJ 2758 Blinker的噩梦(扫描线+熟练剖分+树状数组)
题目链接:http://www.lydsy.com:808/JudgeOnline/problem.php?id=2758
题意:平面上有n个多边形（凸包和圆）。任意两个多边形AB只有两种关系：（1）A包含B或者B包含A；(2)AB的公共面积为0。每个多边形有一个值x。m个查询。分两种：（1）修改某个多边形的值；（2）从一点s走到另一点t。每次走出一个多边形或者进入一个多边形时，都要抑或上该多边形的值。输出走到t时的值。（由抑或的性质和本题定义可得这个值跟走的路经无关）
思路：首先我们发现，这些多边形构成了一棵树。另外设定义某一点p的值S(p)等于包含该点的所有多边形的值的抑或。那么答案为S(s)^S(t)。对应于那个树上，就是s和t到根的值的抑或和。如果我们建成了这棵树，那么分别维护：（1）修改某点的值；（2）查询某点到根的抑或值。这个可以用树链剖分，之后每个链用树状数组维护。
那么现在的问题来了，这个树怎么建？扫描线。保存多边形的最左最右。排序。按照x升序处理。维护包含当前x的所有多边形。维护的时候将要维护的多边形分成上下两部分。每个多边形的上部的标号就是自己，下部的标号为包含自己的最小多边形。每次假设从当前多边形向上有一条射线，那么第一次交到的就是包含该多边形的多边形（注意我们维护的信息是下部的标号为包含自己的最小多边形）。每次一个多边形不在当前要维护区间时删掉。
const double inf=1e20;const int N=600005;struct point{ double x,y; point(double _x=0,double _y=0) { x=_x; y=_y; }};struct Figure{ int type; vector<point> up,down; double x,y,r; int v; pair<double,double> read() { char op[5]; scanf("%s",op); if(‘C‘==op[0]) { type=0; scanf("%lf%lf%lf%d",&x,&y,&r,&v); return MP(x-r,x+r); } type=1; vector<point> tmp; double Min=inf,Max=-inf; int minId,maxId; int n=myInt(); for(int i=0;i<n;i++) { double x,y; scanf("%lf%lf",&x,&y); tmp.pb(point(x,y)); if(x>Max) Max=x,maxId=i; if(x<Min) Min=x,minId=i; } if(maxId<minId) { for(int i=minId;i>=maxId;i--) down.pb(tmp[i]); for(int i=minId;i<n;i++) up.pb(tmp[i]); for(int i=0;i<=maxId;i++) up.pb(tmp[i]); } else { for(int i=minId;i<=maxId;i++) up.pb(tmp[i]); for(int i=minId;i>=0;i--) down.pb(tmp[i]); for(int i=n-1;i>=maxId;i--) down.pb(tmp[i]); } v=myInt(); return MP(Min,Max); } int find(vector<point> a,double x) { for(int i=0;i+1<a.size();i++) { if(a[i].x<=x&&x<=a[i+1].x) return i; } } double intersect(point L,point R,double x) { return L.y+(x-L.x)/(R.x - L.x)*(R.y-L.y); } double getInterval(double xx,int dir) { if(0==type) { if(fabs(xx-(x-r))<=0.001||fabs(xx-(x+r))<=0.001) { return y; } double tmp=sqr(r)-sqr(x-xx); double d=sqrt(tmp); if(dir) return y+d; return y-d; } if(xx==up[0].x||xx==up.back().x) { double Max=-inf,Min=inf; for(int i=0;i<up.size();i++) if(xx==up[i].x) Max=max(Max,up[i].y); for(int i=0;i<down.size();i++) if(xx==down[i].x) Min=min(Min,down[i].y); if(!dir) return Min; return Max; } if(dir) { int u=find(up,xx); return intersect(up[u],up[u+1],xx); } int d=find(down,xx); return intersect(down[d],down[d+1],xx); }};struct Query{ int type,l,r;};struct sweepPoint{ double x; int id,dir; sweepPoint(double _x=0,int _id=0,int _dir=0) { x=_x; id=_id; dir=_dir; }};Figure G[N];sweepPoint Q[N];int qNum;Query query[N];point p[N];int pNum;int n,m;vector<int> g[N];void add(int x,int y){ g[x].pb(y);}double curX;struct myPair{ int id,dir,belong; myPair(double id=0,int dir=0,int belong=0) { this->id=id; this->dir=dir; this->belong=belong; } friend int operator<(const myPair &a,const myPair &b) { if(a.id==b.id&&a.dir!=2&&b.dir!=2) return a.dir<b.dir; double x=(2==a.dir)?p[a.id].y:G[a.id].getInterval(curX,a.dir); double y=(2==b.dir)?p[b.id].y:G[b.id].getInterval(curX,b.dir); return x<y; }};set<myPair> T;myPair L[N],R[N];int cmp(sweepPoint a,sweepPoint b){ if(fabs(a.x-b.x)<1e-8) return a.dir<b.dir; return a.x<b.x;}void init(){ sort(Q+1,Q+qNum+1,cmp); int K=n+pNum+1; for(int i=1;i<=qNum;i++) { curX=Q[i].x; if(0==Q[i].dir) { myPair tmp=myPair(Q[i].id,1,Q[i].id); T.insert(tmp); R[Q[i].id]=tmp; set<myPair>::iterator it=T.find(tmp); it++; int belong=it==T.end()?K:it->belong; tmp=myPair(Q[i].id,0,belong); T.insert(tmp); L[Q[i].id]=tmp; add(belong,Q[i].id); } else if(1==Q[i].dir) { T.erase(L[Q[i].id]); T.erase(R[Q[i].id]); } else if(2==Q[i].dir) { myPair tmp=myPair(Q[i].id,2,0); set<myPair>::iterator it=T.lower_bound(tmp); if(it==T.end()) add(K,Q[i].id+n); else add(it->belong,Q[i].id+n); } }}int d[N];int son[N];int fa[N];void DFS(int u){ son[u]=1; for(int i=0;i<SZ(g[u]);i++) { int v=g[u][i]; fa[v]=u; DFS(v); son[u]+=son[v]; }}int pool[N];int poolCount;int *S[N];int pos[N],root[N],id,listLen[N];void dfs(int u,int rt){ id++; root[u]=rt; pos[u]=id; listLen[rt]++; int s=0; for(int i=0;i<SZ(g[u]);i++) { int v=g[u][i]; if(son[v]>son[s]) s=v; } if(!s) return; dfs(s,rt); for(int i=0;i<SZ(g[u]);i++) { int v=g[u][i]; if(v!=s) dfs(v,v); }}void add(int rt,int x,int val){ while(x<=listLen[rt]) { S[rt][x]^=val; x+=x&-x; }}int cal(int t){ int rtPos=pos[root[t]]; int x=pos[t]-rtPos+1; int rt=root[t]; int ans=0; while(rt) { while(x) ans^=S[rt][x],x-=x&-x; int t=fa[rt]; int rtPos=pos[root[t]]; x=pos[t]-rtPos+1; rt=root[t]; } return ans;}int main(){ n=myInt(); m=myInt(); for(int i=1;i<=n;i++) { pair<double,double> tmp=G[i].read(); Q[++qNum]=sweepPoint(tmp.first,i,0); Q[++qNum]=sweepPoint(tmp.second,i,1); } for(int i=1;i<=m;i++) { char op[5]; scanf("%s",op); if(‘Q‘==op[0]) { pNum++; scanf("%lf%lf",&p[pNum].x,&p[pNum].y); pNum++; scanf("%lf%lf",&p[pNum].x,&p[pNum].y); query[i].type=1; query[i].l=pNum-1; query[i].r=pNum; Q[++qNum]=sweepPoint(p[pNum-1].x,pNum-1,2); Q[++qNum]=sweepPoint(p[pNum].x,pNum,2); } else { query[i].type=0; scanf("%d%d",&query[i].l,&query[i].r); } } init(); for(int i=1;i<=n;i++) d[i]=G[i].v; DFS(n+pNum+1); dfs(n+pNum+1,n+pNum+1); for(int i=1;i<=n+pNum+1;i++) { if(root[i]==i) { S[i]=pool+poolCount; poolCount+=listLen[i]+2; } } for(int i=1;i<=n;i++) { int rtPos=pos[root[i]]; int p=pos[i]; int x=p-rtPos+1; add(root[i],x,d[i]); } int last=0; for(int i=1;i<=m;i++) { if(0==query[i].type) { int t=query[i].l; int rtPos=pos[root[t]]; int p=pos[t]; int x=p-rtPos+1; add(root[t],x,d[t]); d[t]=query[i].r; add(root[t],x,d[t]); } else if(1==query[i].type) { int x=cal(query[i].l+n); int y=cal(query[i].r+n); last^=x^y; printf("%d\n",last); } }}
BZOJ 2758 Blinker的噩梦(扫描线+熟练剖分+树状数组)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。