算是补充一下另一篇题解。

Link

题目大意

给定一个长度为 $n$ 的二维点对序列，相邻点对间连着一条线段，$m$ 个操作，修改操作是在任意位置插入一个点，并相应地修改线段，查询操作给定一个点向法表示的直线，问有多少个线段与之相交。要求能够进行可持久化。

$1\leq n,m \leq 10^5$。

线段可能相交，坐标绝对值不超过 $10^8$，保证插入次数不超过 $5\times 10^4$，保证所有询问的答案总和不超过 $10^6$。

题目分析

考虑点向法判交，其实就相当于将这条线段的两个端点垂直到与查询直线垂直的直线上，这两个垂足是否分别在这条直线的两侧。

这部分我借鉴了另一篇题解，因为作者计算几何实在太菜了，然后这样就有了一个雏形，考虑每次 $O(n)$ 枚举线段，$O(1)$ 判交即可。

先考虑如何处理可持久化，不难发现是一个序列插入的形式，维护一个可持久化 fhq treap 即可，不太建议像另一篇题解一样维护替罪羊树，均摊数据结构总归还是不适合可持久化的。

如何维护当前节点的前驱后继，不难发现在平衡树上等价于维护当前节点左儿子最靠右的节点以及右儿子最靠左的节点，这个直接平衡树上传的时候一并维护即可。

那么现在就有了一个支持插入，能够进行可持久化操作的数据结构了，但是回到最初的问题，查询的复杂度不够优秀。

考虑如何优化，我们运用 KDT 的思想，考虑对查询进行剪枝。

回溯到线段判交，我们发现需要让两个端点一大一小，这就启发了我们维护最值，所以我们对于当前节点维护最大值和最小值即可，考虑一个合法的线段只会贡献一次，而由于保证答案总和不超过 $10^6$，并且每个有贡献的点会对应到平衡树上 $O(\log n)$ 个节点，所以这部分复杂度是正确的。

但是查询是变的，如何维护最值呢？我们将求距离的式子拿出来仔细观察一下。

ll val(int x,int y) {
    return 1ll*A*x+1ll*B*y+C;
}

令 $x,y$ 表示当前线段的端点，$A,B$ 表示垂直线段的方向，考虑分类讨论，若 $A>0,B>0$，那么最大值在 $x,y$ 都最大时取到，若$A>0,B<0$，那么最大值在 $x$ 最大，$y$ 最小时取到，对于另外两种情况，以及最小值同理。

然后就会发现，只要维护 $x,y$ 的最小值和最大值，就能够确定当前区间是否存在线段能够与直线相交，直接在平衡树上维护即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;
int read(){
	int x=0,f=1;char ch = getchar();
	while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch = getchar();}
	while(ch>='0'&&ch<='9'){x = x*10+ch-'0';ch = getchar();}
	return x*f;
}
const int N = 2e5+5;
int n,m,c;
ll A,B,C;
struct poi{
	int x[2];
}p[N];
struct aa{
	int lc,rc,siz,rnd,lx,rx;
	int L[2],R[2];
	poi P;
}node[N*60];
void pushup(int u){
	node[u].siz = node[node[u].lc].siz+node[node[u].rc].siz+1;
	node[u].lx = u;node[u].rx = u;
	if(node[u].lc){
		node[u].lx = node[node[u].lc].lx;
	}
	if(node[u].rc){
		node[u].rx = node[node[u].rc].rx;
	}
	for(int i=0;i<=1;i++){
		node[u].L[i] = node[u].P.x[i];node[u].R[i] = node[u].P.x[i];
		if(node[u].lc){
			node[u].L[i] = min(node[u].L[i],node[node[u].lc].L[i]);
			node[u].R[i] = max(node[u].R[i],node[node[u].lc].R[i]);
		}
		if(node[u].rc){
			node[u].L[i] = min(node[u].L[i],node[node[u].rc].L[i]);
			node[u].R[i] = max(node[u].R[i],node[node[u].rc].R[i]);
		}
	}
}
int tot,rt[N];
int newnode(poi P){
	tot++;
	node[tot].P = P;
	node[tot].rnd = rand();
	node[tot].siz = 1;
	pushup(tot); 
	return tot;
}
int cpy(int u){
	int res = ++tot;
	node[res] = node[u];
	return res;
}
int merge(int u,int v){
	if(!u||!v){
		return u+v;
	}
	if(node[u].rnd>node[v].rnd){
		node[u].rc = merge(node[u].rc,v);
		pushup(u);
		return u;
	}else{
		node[v].lc = merge(u,node[v].lc);
		pushup(v);
		return v;
	}
}
void split(int u,int val,int &x,int &y){
	if(!u){
		x = 0;y = 0;
		return;
	}
	if(node[node[u].lc].siz<val){
		x = cpy(u);
		split(node[x].rc,val-node[node[u].lc].siz-1,node[x].rc,y);
		pushup(x);
	}else{
		y = cpy(u);
		split(node[y].lc,val,x,node[y].lc);
		pushup(y);
	}
}
int x,y;
void ins(int pla,poi P,int v,int now){
	split(rt[v],pla,x,y);
	rt[now] = merge(merge(x,newnode(P)),y);
}
void build(int &u,int l,int r){
	if(l>r){
		return;
	}
	int mid = (l+r)/2;
	u = newnode(p[mid]);
	build(node[u].lc,l,mid-1);
	build(node[u].rc,mid+1,r);
	pushup(u);
}
ll val(int x,int y) {
    return 1ll*A*x+1ll*B*y+C;
}
int ans;char op[5];
bool check(int a,int b,int c,int d){
	ll v1 = val(a,b),v2 = val(c,d);
	if(v1>v2){
		swap(v1,v2); 
	}
	return (v1<=0&&v2>=0);
}
void query(int u){
	if(!u){
		return;
	}
//	cout<<"U:"<<node[u].P.x[0]<<"\n";
	if(node[u].lc){
		int v = node[node[u].lc].rx;
		ans+=check(node[u].P.x[0],node[u].P.x[1],node[v].P.x[0],node[v].P.x[1]);
	}
	if(node[u].rc){
		int v = node[node[u].rc].lx;
		ans+=check(node[u].P.x[0],node[u].P.x[1],node[v].P.x[0],node[v].P.x[1]);
	}
	auto v = node[u];
	ll f1 = val(v.L[0],v.L[1]);
	ll f2 = val(v.L[0],v.R[1]);
	ll f3 = val(v.R[0],v.L[1]);
	ll f4 = val(v.R[0],v.R[1]);
	if((f1>0&&f2>0&&f3>0&&f4>0)||(f1<0&&f2<0&&f3<0&&f4<0)){
		return;
	}
	query(node[u].lc);
	query(node[u].rc);
}
signed main(){
	n = read();m = read();c = read();
	for(int i=1;i<=n;i++){
		p[i].x[0] = read();p[i].x[1] = read();
	}
	build(rt[0],1,n);
	int v,k,X,Y;
	for(int i=1;i<=m;i++){
		scanf("%s",op);
		if(op[0]=='Z'){
			v = read();k = read();X = read()^(ans*c);Y = read()^(ans*c);
			ins(k,(poi){X,Y},v,i);
		}else{
			v = read();X = read()^(ans*c);Y = read()^(ans*c);A = read()^(ans*c);B = read()^(ans*c);
			swap(A,B);
			A = A*(-1);
			C = -1ll*A*X-1ll*B*Y;
			ans = 0;
			rt[i] = rt[v];
			query(rt[v]);
			cout<<ans<<"\n";
		}
	}
	return 0;
}
/*
2 1 0
0 0
1 1
H 0 1 0 -1 1
*/

再次叠个甲，我做法中有关几何的都是抄的另一篇题解，作者几何实在太差了，所以这篇仅供解释说明。