题解 P4509 【[CTSC2015]葱】
对于平面上的判交问题，我们可以很容易得想到利用KD-tree来解决。如果我们按照顺序构出一颗平衡树，并且同时每个节点包含了一个矩形。之后我们发现，对于所有的线段点对就是一个点和他的前驱所组成的所有线段。但是我们发现对每个点都找一次前驱会相当的复杂。但是我们发现对于这样一个点对，对于深度较浅的那个点来说就是要么是右儿子的最左点和或者是左儿子的最右点，如果对每个点都这样考虑之后，我们发现不重不漏的考虑完了所有线段对。
那么对于原题的查询，一条直线，我们只需要判断直线是否与点代表矩形判交，以及搜到某个点的时候，判定一下上面所说的两个点对代表线段与直线是否有交，而对于插入就是简单的平衡树插入，而可持久化，我们写一颗可持久化替罪羊树就OK了。
由于答案总和不超过10^6，插入操作的次数不会超过5*10^4，所以不会被卡掉。
欢迎来newuser小站看看owo
#include<stdio.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
typedef long long ll;
const int maxn = 100005;
int n,m,type;
struct node{
node *ls,*rs,*lmax,*rmax; int siz;
int x,y; int sx[2],sy[2];int xds;
}z[maxn*60],*nul,*tl,*rt[maxn],**RT;
int ZX,ZY,FX,FY;
ll A,B,C;
ll calc(int x,int y) {
return 1ll*A*x + 1ll*B*y + C;
}
bool che(int ax,int ay,int bx,int by) {
ll f1 = calc(ax,ay) ,f2 = calc(bx,by);
if(f1>f2) swap(f1,f2);
return (f1<=0&&f2>=0);
}
struct dd {
int x,y;
}oo[maxn]; int top;
node* nwnode(dd &tt) {
node* p = ++tl;
p->ls = p->rs = nul; p->siz = 1;
p->x = p->sx[0] = p->sx[1] = tt.x;
p->y = p->sy[0] = p->sy[1] = tt.y;
p->lmax = p->rmax = p; p->xds = 0;
return p;
}
void upd(node *&p) {
p->siz = 1; p->xds = 0;
if(p->ls!=nul) {
p->sx[0] = min(p->sx[0],p->ls->sx[0]);
p->sx[1] = max(p->sx[1],p->ls->sx[1]);
p->sy[0] = min(p->sy[0],p->ls->sy[0]);
p->sy[1] = max(p->sy[1],p->ls->sy[1]);
p->lmax = p->ls->lmax;
p->xds += p->ls->xds + 1;
p->siz += p->ls->siz;
}
if(p->rs!=nul) {
p->sx[0] = min(p->sx[0],p->rs->sx[0]);
p->sx[1] = max(p->sx[1],p->rs->sx[1]);
p->sy[0] = min(p->sy[0],p->rs->sy[0]);
p->sy[1] = max(p->sy[1],p->rs->sy[1]);
p->rmax = p->rs->rmax;
p->xds += p->rs->xds + 1;
p->siz += p->rs->siz;
}
}
void makekd(node *&p,int l,int r) {
int mid = (l+r)>>1;
p = nwnode(oo[mid]);
if(l<mid) makekd(p->ls,l,mid-1);
if(mid<r) makekd(p->rs,mid+1,r);
upd(p);
}
bool isbad(node *&p) {
if(p->ls->siz*5 > p->siz*4 || p->rs->siz*5 > p->siz*4 ) return 1;
return 0;
}
void tra(node *&p) {
if(p==nul) return;
tra(p->ls);
oo[++top] = (dd) {p->x,p->y};
tra(p->rs);
}
void rebuild() {
if(*RT==nul) return;
top = 0;
tra(*RT);
if(top>0)makekd(*RT,1,top);
else *RT = nul;
RT = &nul;
}
void init() {
nul = tl = z;
nul->ls = nul->rs = nul;
for(int i=0;i<=m;i++) {
rt[i] = nul;
}
RT = &nul;
}
void ins(node *&p,node *&las,int orz,int X,int Y) {
if(las==nul){
dd owo = (dd){X,Y};
p = nwnode((owo));
return;
}
p = ++tl; *p = *las;
if(p->ls->siz>=orz) ins(p->ls,las->ls,orz,X,Y);
else {
orz -= p->ls->siz+1;
ins(p->rs,las->rs,orz,X,Y);
}
upd(p);
if(isbad(p)) RT = &p;
}
int query(node *&p) {
if(p==nul) return 0;
int sm = 0;
if(p->ls!=nul)
sm += che(p->x,p->y,p->ls->rmax->x,p->ls->rmax->y);
if(p->rs!=nul)
sm += che(p->x,p->y,p->rs->lmax->x,p->rs->lmax->y);
int f0 = calc(p->sx[0],p->sy[0]);
int f1 = calc(p->sx[0],p->sy[1]);
int f2 = calc(p->sx[1],p->sy[0]);
int f3 = calc(p->sx[1],p->sy[1]);
if( (f0<0&&f1<0&&f2<0&&f3<0)||(f0>0&&f1>0&&f2>0&&f3>0) ) return sm;
return query(p->ls) + query(p->rs) + sm;
}
main() {
init();
scanf("%lld%lld%lld",&n,&m,&type);
for(int i=1;i<=n;i++) {
scanf("%lld%lld",&oo[i].x,&oo[i].y);
}
makekd(rt[0],1,n);
int lastans = 0;
char ss[2];
for(int i=1;i<=m;i++) {
scanf("%s",&ss[0]);
if(ss[0]=='H') {
int T;
scanf("%lld%lld%lld%lld%lld",&T,&ZX,&ZY,&FX,&FY);
if(type) {
ZX^=lastans; ZY^=lastans;
FX^=lastans; FY^=lastans;
}
A = -FY; B = FX;
C = - 1ll*A*ZX - 1ll*ZY*B;
rt[i] = rt[T];
lastans = query(rt[i]);
printf("%lld\n",lastans);
} else {
int T,orz,X,Y;
scanf("%lld%lld%lld%lld",&T,&orz,&X,&Y);
if(type)X^=lastans,Y^=lastans;
ins(rt[i],rt[T],orz,X,Y);
if(*RT!=nul) rebuild();
}
}
}