LG4848 崂山白花蛇草水

崂山白花蛇草水

神犇 Aleph 在 SDOI Round2 前立了一个 flag：如果进了省队，就现场直播喝崂山白花蛇草水。凭借着神犇 Aleph 的实力，他轻松地进了山东省省队，现在便是他履行诺言的时候了。蒟蒻 Bob 特地为他准备了 999,999,999,999,999,999 瓶崂山白花蛇草水，想要灌神犇 Aleph。神犇 Aleph 求（跪着的）蒟蒻 Bob 不要灌他，由于神犇 Aleph 是神犇，蒟蒻 Bob 最终答应了他的请求，但蒟蒻 Bob 决定将计就计，也让神犇 Aleph 回答一些问题。

具体说来，蒟蒻 Bob 会在一个宽敞的广场上放置一些崂山白花蛇草水（可视为二维平面上的一些整点），然后询问神犇 Aleph 在矩形区域\(x_1\le x\le x_2,y_1\le y\le y_2\)中，崂山白花蛇草水瓶数第 \(k\) 多的是多少。为了避免麻烦，蒟蒻 Bob 不会在同一个位置放置两次或两次以上的崂山白花蛇草水，但蒟蒻 Bob 想为难一下神犇Aleph，希望他能在每次询问时立刻回 答出答案。

神犇 Aleph 不屑于做这种问题，所以把这个问题交给了你。

对于所有数据，\(n\le500000，q\le100000，1\le x, y\le n，1\le v\le 10^9，1\le x_1\le x_2\le n1，1\le y_1\le y_2\le n，1\le k\le q\)。

Claris的题解

外层维护权值线段树，内层维护kd-tree。

修改的时候只往右儿子里插入（因为只会查询右儿子的矩形内点的个数），不平衡的时候替罪羊式重构。

查询的时候在外层线段树上走，在内层kd-tree上查询矩形内点数即可。

\(Q(n)=\sqrt{n}+Q(n/2)=O(\sqrt{n})\)

\(C(n)=\log^2 n + C(n/2)=O(\log^3 n)\)

时间复杂度\(O(q\log v (\log^2 q+\sqrt{q}))\)。

代码

终于找到我梦寐以求的好的替罪羊树的写法了，记录插入进去的那条链，先判深度，可能不平衡再重构一次。

插入和重构分开进行便可去掉冗余操作。

#include<bits/stdc++.h>

#define rg register

#define il inline

#define co const

template<class T>il T read(){

	rg T data=0,w=1;

	rg char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-') w=-1;

		ch=getchar();

	}

	while(isdigit(ch))

		data=data*10+ch-'0',ch=getchar();

	return data*w;

}

template<class T>il T read(rg T&x){

	return x=read<T>();

}

typedef long long ll;

using namespace std;

co double A=0.8;

co int N=1e5+1,M=16e5;

int n,ans,cmp_d,op,X1,Y1,X2,Y2,k;

int tmp[N],deep,need[N],cnt,cur;

int T[M],l[M],r[M],tot=1;

struct node{int d[2],l,r,Max[2],Min[2],size;}t[M];

bool cmp(int a,int b){return t[a].d[cmp_d]<t[b].d[cmp_d];}

void umax(int&a,int b){if(a<b)a=b;}

void umin(int&a,int b){if(a>b)a=b;}

void up(int x){

	t[x].size=1+t[t[x].l].size+t[t[x].r].size;

	if(t[x].l){

		umax(t[x].Max[0],t[t[x].l].Max[0]),umax(t[x].Max[1],t[t[x].l].Max[1]);

		umin(t[x].Min[0],t[t[x].l].Min[0]),umin(t[x].Min[1],t[t[x].l].Min[1]);

	}

	if(t[x].r){

		umax(t[x].Max[0],t[t[x].r].Max[0]),umax(t[x].Max[1],t[t[x].r].Max[1]);

		umin(t[x].Min[0],t[t[x].r].Min[0]),umin(t[x].Min[1],t[t[x].r].Min[1]);

	}

}

int build(int l,int r,int D){

	int mid=(l+r)>>1;

	cmp_d=D;

	nth_element(need+l,need+mid,need+r+1,cmp);

	int x=need[mid];

	t[x].Max[0]=t[x].Min[0]=t[x].d[0];

	t[x].Max[1]=t[x].Min[1]=t[x].d[1];

	t[x].l=l<mid?build(l,mid-1,D^1):0;

	t[x].r=mid<r?build(mid+1,r,D^1):0;

	up(x);

	return x;

}

void dfs(int x){if(x) need[++cnt]=x,dfs(t[x].l),dfs(t[x].r);}

void ins(int&root,int now){

	if(!root) {root=now;return;}

	for(int D=deep=0,x=root;;D^=1){

		tmp[++deep]=x;

		umax(t[x].Max[0],t[now].Max[0]),umax(t[x].Max[1],t[now].Max[1]);

		umin(t[x].Min[0],t[now].Min[0]),umin(t[x].Min[1],t[now].Min[1]);

		++t[x].size;

		if(t[now].d[D]>=t[x].d[D]){

			if(!t[x].r) {t[x].r=now;break;}

			else x=t[x].r;

		}

		else{

			if(!t[x].l) {t[x].l=now;break;}

			else x=t[x].l;

		}

	}

	tmp[++deep]=now;

	if(deep<log(t[root].size)/log(1/A)) return;

	while(t[t[now].l].size<A*t[now].size&&t[t[now].r].size<A*t[now].size) now=tmp[--deep];

	if(!now) return;

	if(now==root){

		cnt=0,dfs(root);

		root=build(1,cnt,0);

		return;

	}

	int y=tmp[--deep];

	cnt=0,dfs(now);

	int k=build(1,cnt,deep&1);

	if(t[y].l==now) t[y].l=k;

	else t[y].r=k;

}

void ask(int x){

	if(!x||t[x].Max[0]<X1||t[x].Min[0]>X2||t[x].Max[1]<Y1||t[x].Min[1]>Y2||ans>=k) return;

	if(t[x].Min[0]>=X1&&t[x].Max[0]<=X2&&t[x].Min[1]>=Y1&&t[x].Max[1]<=Y2) {ans+=t[x].size;return;}

	if(t[x].d[0]>=X1&&t[x].d[0]<=X2&&t[x].d[1]>=Y1&&t[x].d[1]<=Y2) ++ans;

	ask(t[x].l),ask(t[x].r);

}

void add(){

	int x=1,a=1,b=1e9,mid,flag=1;

	while(1){

		if(flag){

			++cur;

			t[cur].Max[0]=t[cur].Min[0]=t[cur].d[0]=X1;

			t[cur].Max[1]=t[cur].Min[1]=t[cur].d[1]=Y1;

			t[cur].size=1;

			ins(T[x],cur);

		}

		if(a==b) return;

		mid=(a+b)>>1;

		if(k<=mid){

			if(!l[x]) l[x]=++tot;

			x=l[x],b=mid,flag=0;

		}

		else{

			if(!r[x]) r[x]=++tot;

			x=r[x],a=mid+1,flag=1;

		}

	}

}

void query(){

	ans=0,ask(T[1]);

	if(ans<k){

		puts("NAIVE!ORZzyz.");

		ans=0;

		return;

	}

	int x=1,a=1,b=1e9,mid;

	while(a<b){

		mid=(a+b)>>1;

		ans=0,ask(T[r[x]]);

		if(ans>=k) x=r[x],a=mid+1;

		else k-=ans,x=l[x],b=mid;

	}

	printf("%d\n",ans=a);

}

int main(){

//	freopen(".in","r",stdin);

//	freopen(".out","w",stdout);

	read(n),read(n);

	while(n--){

		read(op),read(X1),read(Y1);X1^=ans,Y1^=ans;

		if(op==1){

			read(k);k^=ans;

			add();

		}

		else{

			read(X2),read(Y2),read(k);X2^=ans,Y2^=ans,k^=ans;

			query();

		}

	}

	return 0;

}