自动搬运

查看原文

来自洛谷，原作者为

	hsfzLZH1 我永远喜欢珂朵莉

搬运于2025-08-24 22:14:53，当前版本为作者最后更新于2020-09-17 22:02:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道很好的提高组数据结构综合题。（强烈推荐！）

平衡树维护扫描线+线段树或树状数组维护树链剖分

题目大意

给定 $n$ 个 互不相交 的圆或凸多边形，每个图形还有一个权值 $v$ ， $m$ 次操作：

Q x0 y0 x1 y1 ： 查询从 $(x0,y0)$ 到 $(x1,y1)$ 的线段所经过的图形的边界的异或和。这个答案要异或上一个询问的答案。保证 $(x0,y0)$ 和 $(x1,y1)$ 均不在图形的边界上。

C i v ： 将第 $i$ 个给出的图形的权值改为 $v$ 。

$1\le n\le 10^5,1\le m\le 10^5$ ，单个凸多边形的点数 $\le 34$ 。

凸多边形的顶点坐标按顺时针顺序给出。

树链剖分部分

优先考虑这一部分有助于我们明晰扫描线部分要维护哪些值。

由于异或的性质，题目所求等价于求任意一条从 $(x0,y0)$ 到 $(x1,y1)$ 的任意曲线经过的图形边界的权值和。将这条直线特殊化为从 $(x0,y0)$ 走到平面内不在任何一个图形内的地方，再从这个地方走到 $(x1,y1)$ 的权值和。这样可以 将一对点的询问拆成两个对单点的询问 。

由于给出的图形互不相交，则两个图形只有相离和包含两种情况，则它们之间的相互包含关系构成了一棵 树 （若一个图形 $A$ 完全包含另一个图形 $B$ ，则 $A$ 在树上为 $B$ 的祖先，再设一个超级根节点表示整个平面）。

假设我们已经通过扫描线预处理出了这棵树，和包含每个询问中的点的最小图形。令树上一个点的权值为该点对应图形的权值。一个点走到平面内不在任何一个图形内的区域的权值异或和，为该点所在最小图形对应点到根的路径异或和。

树上单点修改，树上查询路径异或和，这一部分可以用线段树或树状数组维护树链剖分实现。参考代码中用的是线段树实现。

扫描线部分

由上一部分可知，扫描线部分要求出图形包含关系的树，和每个点最小被包含在哪个图形内。

考虑以 $x$ 坐标为时间进行扫描线。每个图形有贡献的时间段就是该图形的最左和最右顶点的 $x$ 坐标之间的区间。我们在左顶点 $x$ 坐标插入这个图形的上下边界，在右顶点 $x$ 坐标删除这个图形的上下边界。

在插入一个图形 $a$ 时，求出在它 下方且最近 的图形边界。设下方的边界属于图形 $b$ 。若这个边界是 $b$ 的上边界，则恰好包含 $a$ 的最小图形应是恰好包含 $b$ 的最小图形；若是下边界，则恰好包含 $a$ 的最小图形应是 $b$ 。恰好包含 $a$ 的最小图形在树上就是 $a$ 的父亲。

对于一个点，我们也可以求出它下方的最近的图形边界，用相同的方法求出包含该点的最小图形。

我们发现在时间变化后，每个边界的 $y$ 坐标都发生了变化，这个变化不可维护。但是，由于图形互不相交，边界之间的排列顺序不会发生变化。我们可以用平衡树来维护边界的排列顺序，在查询时只需求出当前结点对应的边界的 $y$ 坐标值，来确定是向左还是向右走。

总的时间复杂度为 $O((n+m)\log (n+m))$ ，空间复杂度为 $O(n+m)$ 。

参考代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
const int maxn=400010;
const double inf=1e18;
const double eps=1e-9;
bool eq(double x,double y){return fabs(x-y)<=eps;}
int n,m,tid,nm[maxn][3],lst;
char op;
struct Query
{
	char op;
	double xa,ya,xb,yb;
	int aid,bid,id,v;
}s[maxn];
struct Node
{
	double x,y;int col;
}a[maxn];
struct Poly
{
	char op;
	int v,l;
	double x[36],y[36],r;
	double upper(double t)
	{
		if(op=='C')return y[0]+sqrt(max(0.0,r*r-(x[0]-t)*(x[0]-t)));
		double ret=-inf;
		for(int i=1;i<l;i++)
		{
			if(eq(x[i],x[i+1])&&eq(x[i],t))ret=max(ret,max(y[i],y[i+1])); 
			else if(x[i]<=t&&t<=x[i+1])ret=max(ret,y[i]+(t-x[i])/(x[i+1]-x[i])*(y[i+1]-y[i]));
			else if(x[i+1]<=t&&t<=x[i])ret=max(ret,y[i+1]+(t-x[i+1])/(x[i]-x[i+1])*(y[i]-y[i+1]));
		}
		if(eq(x[1],x[l])&&eq(x[1],t))ret=max(ret,max(y[1],y[l]));
		else if(x[l]<=t&&t<=x[1])ret=max(ret,y[l]+(t-x[l])/(x[1]-x[l])*(y[1]-y[l]));
		else if(x[1]<=t&&t<=x[l])ret=max(ret,y[1]+(t-x[1])/(x[l]-x[1])*(y[l]-y[1]));
		return ret;
	}
	double lower(double t)
	{
		if(op=='C')return y[0]-sqrt(max(0.0,r*r-(x[0]-t)*(x[0]-t)));
		double ret=inf;
		for(int i=1;i<l;i++)
		{
			if(eq(x[i],x[i+1])&&eq(x[i],t))ret=min(ret,min(y[i],y[i+1])); 
			else if(x[i]<=t&&t<=x[i+1])ret=min(ret,y[i]+(t-x[i])/(x[i+1]-x[i])*(y[i+1]-y[i]));
			else if(x[i+1]<=t&&t<=x[i])ret=min(ret,y[i+1]+(t-x[i+1])/(x[i]-x[i+1])*(y[i]-y[i+1]));
		}
		if(eq(x[1],x[l])&&eq(x[1],t))ret=min(ret,min(y[1],y[l]));
		else if(x[l]<=t&&t<=x[1])ret=min(ret,y[l]+(t-x[l])/(x[1]-x[l])*(y[1]-y[l]));
		else if(x[1]<=t&&t<=x[l])ret=min(ret,y[1]+(t-x[1])/(x[l]-x[1])*(y[l]-y[1]));
		return ret;
	}
}po[maxn];
int cur;
struct Oper
{
	int op,id;double t;
	bool operator<(Oper x)const{return t==x.t?op<x.op:t<x.t;}
}q[maxn];
struct FHQ
{
	int rt,cur,siz[maxn],fa[maxn],lc[maxn],rc[maxn],id[maxn],op[maxn];
	int newnode(int i,int o){cur++;siz[cur]=1;id[cur]=i;op[cur]=o;return cur;}
	void maintain(int o){siz[o]=siz[lc[o]]+siz[rc[o]]+1;}
	int merge(int x,int y)
	{
		if((!x)||(!y))return x+y;
		if(rand()%(siz[x]+siz[y])<siz[x]){rc[x]=merge(rc[x],y);fa[rc[x]]=x;maintain(x);return x;}
		else{lc[y]=merge(x,lc[y]);fa[lc[y]]=y;maintain(y);return y;}
	}
	void split_siz(int o,int k,int&x,int&y)
	{
		if(!o){x=y=0;return;}
		if(k<=siz[lc[o]]){y=o;fa[lc[y]]=0;split_siz(lc[y],k,x,lc[y]);fa[lc[y]]=y;maintain(y);}
		else{x=o;fa[rc[x]]=0;split_siz(rc[x],k-siz[lc[o]]-1,rc[x],y);fa[rc[x]]=x;maintain(x);}
	}
	void split(int o,double t,double v,int&x,int&y)
	{
		if(!o){x=y=0;return;}
		double u;if(op[o]==1)u=po[id[o]].upper(t);else u=po[id[o]].lower(t);
		if(u>v){x=o;fa[rc[x]]=0;split(rc[x],t,v,rc[x],y);fa[rc[x]]=x;maintain(x);}
		else{y=o;fa[lc[y]]=0;split(lc[y],t,v,x,lc[y]);fa[lc[y]]=y;maintain(y);}
	}
	int rnk(int o)
	{
		int ret=siz[lc[o]]+1;
		while(fa[o]){if(o==rc[fa[o]])ret+=siz[lc[fa[o]]]+1;o=fa[o];}
		return ret;
	}
	int leftist(int o){while(lc[o])o=lc[o];return o;}
}st;
int cnt,h[maxn],nxt[maxn],p[maxn];
void add_edge(int x,int y)
{
	cnt++;
	nxt[cnt]=h[x];
	h[x]=cnt;
	p[cnt]=y;
}
int fa[maxn],dep[maxn],siz[maxn],son[maxn],top[maxn],clk,dfn[maxn],rnk[maxn];
void dfs1(int x,int f)
{
	siz[x]=1;
	for(int j=h[x];j;j=nxt[j])if(p[j]!=f)
	{
		fa[p[j]]=x;
		dep[p[j]]=dep[x]+1;
		dfs1(p[j],x);
		siz[x]+=siz[p[j]];
		if((!son[x])||(siz[p[j]]>siz[son[x]]))son[x]=p[j];
	}
}
void dfs2(int x,int t)
{
	top[x]=t;
	dfn[x]=++clk;rnk[clk]=x;
	if(son[x])dfs2(son[x],t);
	for(int j=h[x];j;j=nxt[j])if(p[j]!=fa[x]&&p[j]!=son[x])dfs2(p[j],p[j]);
}
int sum[maxn];
#define lc (o<<1)
#define rc (o<<1|1)
void update(int o,int l,int r,int x,int v)
{
	if(l==r){sum[o]=v;return;}
	int mid=(l+r)>>1;
	if(x<=mid)update(lc,l,mid,x,v);
	else update(rc,mid+1,r,x,v);
	sum[o]=sum[lc]^sum[rc];
}
int query(int o,int l,int r,int ql,int qr)
{
	if(r<ql||l>qr)return 0;
	if(ql<=l&&r<=qr)return sum[o];
	int mid=(l+r)>>1;
	return query(lc,l,mid,ql,qr)^query(rc,mid+1,r,ql,qr); 
}
int qdist(int x)
{
	int ret=0;
	while(x)
	{
		ret^=query(1,1,n+1,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	return ret;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf(" %c",&op);po[i].op=op;
		if(op=='C')scanf("%lf%lf%lf%d",&po[i].x[0],&po[i].y[0],&po[i].r,&po[i].v),q[++cur]={1,i,po[i].x[0]-po[i].r},q[++cur]={2,i,po[i].x[0]+po[i].r};
		if(op=='P')
		{
			scanf("%d",&po[i].l);
			double minx=inf,maxx=-inf;
			for(int j=1;j<=po[i].l;j++)scanf("%lf%lf",po[i].x+j,po[i].y+j),minx=min(minx,po[i].x[j]),maxx=max(maxx,po[i].x[j]);
			q[++cur]={1,i,minx};q[++cur]={2,i,maxx};
			scanf("%d",&po[i].v);
		}
	}
	tid=0;
	for(int i=1;i<=m;i++)
	{
		scanf(" %c",&s[i].op);
		if(s[i].op=='Q')
		{
			scanf("%lf%lf%lf%lf",&s[i].xa,&s[i].ya,&s[i].xb,&s[i].yb);
			s[i].aid=++tid;q[++cur]={3,tid,s[i].xa};a[tid]={s[i].xa,s[i].ya};
			s[i].bid=++tid;q[++cur]={3,tid,s[i].xb};a[tid]={s[i].xb,s[i].yb};
		}
		else scanf("%d%d",&s[i].id,&s[i].v);
	}
	sort(q+1,q+cur+1);
	for(int i=1;i<=cur;i++)
	{
		if(q[i].op==1)
		{
			double v=po[q[i].id].upper(q[i].t);
			int a,b,c,d;
			st.split(st.rt,q[i].t,v,a,c);
			if(!st.siz[c])fa[q[i].id]=n+1;
			else
			{
				d=st.leftist(c);
				if(st.op[d]==1)fa[q[i].id]=fa[st.id[d]];
				else fa[q[i].id]=st.id[d];
			}
			add_edge(q[i].id,fa[q[i].id]);add_edge(fa[q[i].id],q[i].id);
			b=st.merge(st.newnode(q[i].id,1),st.newnode(q[i].id,2));
			nm[q[i].id][1]=st.cur-1;nm[q[i].id][2]=st.cur;
			st.rt=st.merge(st.merge(a,b),c);
		}
		else if(q[i].op==2)
		{
			int a,b,c,d;
			d=st.rnk(nm[q[i].id][1]);
			st.split_siz(st.rt,d-1,a,b);
			st.split_siz(b,1,b,c);
			st.rt=st.merge(a,c);
			d=st.rnk(nm[q[i].id][2]);
			st.split_siz(st.rt,d-1,a,b);
			st.split_siz(b,1,b,c);
			st.rt=st.merge(a,c);
		}
		else
		{
			double v=a[q[i].id].y;
			int A,B,C;
			st.split(st.rt,q[i].t,v,A,B);
			if(!st.siz[B])a[q[i].id].col=n+1;
			else
			{
				C=st.leftist(B);
				if(st.op[C]==1)a[q[i].id].col=fa[st.id[C]];
				else a[q[i].id].col=st.id[C];
			}
			st.rt=st.merge(A,B);
		}
	}
	dep[n+1]=1;dfs1(n+1,0);dfs2(n+1,n+1);
	for(int i=1;i<=n;i++)update(1,1,n+1,dfn[i],po[i].v);
	for(int i=1;i<=m;i++)
	{
		if(s[i].op=='Q')printf("%d\n",lst^=(qdist(a[s[i].aid].col)^qdist(a[s[i].bid].col)));
		else update(1,1,n+1,dfn[s[i].id],s[i].v);
	}
	return 0;
}