bzoj4605:崂山白花蛇草水(权值线段树套K-D tree+替罪羊树重构)

Author Avatar
Sakits 7月 26, 2018

题解

  这绝对是我写过的子程序个数最多的代码了…调了半天参终于调进了第一页…
  bzoj4604是个离线的弱化版,可以写CDQ分治+整体二分干掉,比kdt快到不知道哪里去了…但是这题要求在线就不行了…
  其实求维护在线维护矩阵也可以树套树,再加个第kk大也就是个树套树套树,但是巨难写而且常数很大的样子…
  维护矩阵信息当然是kdt大法好啦!然后因为要求第kk大所以就套个权值线段树,在树上每个节点挂一棵kdt维护矩阵里所有这个权值范围内的点即可,复杂度O(nnlogn)O(n\sqrt{n}logn)
  但是这题必须写替罪羊树重构,当插入到有一个节点满足以下条件时,必须重构其子树:

max(size[leftson],size[rightson])>size[p]facmax(size[leftson], size[rightson])>size[p]\cdot fac

  一般facfac的取值是0.650.750.65\sim 0.75,根据ccz大爷计算出来复杂度应该是n1.6n1.7n^{1.6} \sim n^{1.7},重构的复杂度为log2nlog^2n,但是kk越小重构的复杂度越高,所以这个kk还是要手动三分一下取最小的233。在卡了十来发bzoj之后测出来我这题的facfac貌似取0.80.8最优…

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define klt ktr[x].ls
#define krt ktr[x].rs
#define slt str[x].ls
#define srt str[x].rs
#define maxs(a, b) a=(a>b?a:b)
#define mins(a, b) a=(a<b?a:b)
using namespace std;
const int maxn=500010, inf=1e9;
const double A=0.8;
struct kdt{int d[2], l[2], r[2], size, ls, rs;}ktr[maxn<<2];
struct sgt{int ls, rs;}str[maxn];
struct poi{int d[2];}P;
struct que{int x, y, x2, y2;}q;
int n, ktot, dep, cmpd, cnt, stot, x, y, ans, Q, ty, sroot, k;
int tmp[maxn], np[maxn], root[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
}

inline void up(int x)
{
	ktr[x].size=ktr[klt].size+ktr[krt].size+1;
	for(int i=0;i<2;i++)
	{
		if(klt) mins(ktr[x].l[i], ktr[klt].l[i]), maxs(ktr[x].r[i], ktr[klt].r[i]);
		if(krt) mins(ktr[x].l[i], ktr[krt].l[i]), maxs(ktr[x].r[i], ktr[krt].r[i]);
	}
}

inline void newnode(int x)
{
	ktr[x].size=1;
	for(int i=0;i<2;i++) 
	ktr[x].d[i]=ktr[x].l[i]=ktr[x].r[i]=P.d[i];
}

void insert(int &x, int ty)
{
	if(!x) {x=++ktot; newnode(x); return;}
	tmp[++dep]=x;
	if(P.d[ty]<ktr[x].d[ty]) insert(klt, ty^1);
	else insert(krt, ty^1);
	up(x);
}

void dfs(int x){if(x) np[++cnt]=x, dfs(klt), dfs(krt);}

inline bool cmp(int a, int b){return ktr[a].d[cmpd]<ktr[b].d[cmpd];}

void build(int &x, int l, int r, int ty)
{
	int mid=(l+r)>>1; cmpd=ty; 
	nth_element(np+l, np+mid, np+r+1, cmp); x=np[mid]; 
	for(int i=0;i<2;i++) ktr[x].l[i]=ktr[x].r[i]=ktr[x].d[i];
	if(l<mid) build(klt, l, mid-1, ty^1); else klt=0;
	if(mid<r) build(krt, mid+1, r, ty^1); else krt=0;
	up(x);
}

inline void work(int &x)
{
	dep=0; insert(x, 0);
	int now=ktot; 
	while(max(ktr[ktr[now].ls].size, ktr[ktr[now].rs].size)<A*ktr[now].size) now=tmp[--dep];
	if(!now) return; 
	if(now==x) cnt=0, dfs(x), build(x, 1, cnt, 0);
	else
	{
		int fa=tmp[--dep];
		cnt=0; dfs(now);
		int k; build(k, 1, cnt, dep&1);
		if(ktr[fa].ls==now) ktr[fa].ls=k; else ktr[fa].rs=k;
	}
}

void update(int &x, int l, int r, int cx, bool flag)
{
	if(!x) x=++stot; if(flag) work(root[x]);
	if(l==r) return;
	int mid=(l+r)>>1;
	if(cx<=mid) update(slt, l, mid, cx, 0);
	else update(srt, mid+1, r, cx, 1);
}

inline bool cross(int x)
{
    if(!x) return 0;
    if(q.x>ktr[x].r[0]) return 0;
    if(q.y>ktr[x].r[1]) return 0;
    if(q.x2<ktr[x].l[0]) return 0;
    if(q.y2<ktr[x].l[1]) return 0;
    return 1;
}

void kquery(int x)
{
	if(q.x<=ktr[x].l[0] && q.y<=ktr[x].l[1] && ktr[x].r[0]<=q.x2 && ktr[x].r[1]<=q.y2) ans+=ktr[x].size;
	else 
	{
		if(q.x<=ktr[x].d[0] && q.y<=ktr[x].d[1] && ktr[x].d[0]<=q.x2 && ktr[x].d[1]<=q.y2) ans++;
		if(cross(klt)) kquery(klt);
		if(cross(krt)) kquery(krt);
	}
}

int squery(int x, int l, int r, int k)
{
	if(l==r) return l;
	int mid=(l+r)>>1;
	ans=0; 
	if(srt) kquery(root[srt]);
	if(ans<k) return squery(slt, l, mid, k-ans);
	return squery(srt, mid+1, r, k);
}

void queryans(int k)
{
	ans=0; kquery(root[1]);
	if(ans<k) {puts("NAIVE!ORZzyz."); ans=0; return;}
	printf("%d\n", ans=squery(1, 1, n, k));
}
 
int main()
{
	read(n); read(Q); n=1e9;
	while(Q--)
	{
		read(ty);
		if(ty==1)
		{
			read(P.d[0]); read(P.d[1]); read(x);
			P.d[0]^=ans; P.d[1]^=ans; x^=ans; 
			update(sroot, 1, n, x, 1);
		}
		else 
		{
			read(q.x); read(q.y); read(q.x2); read(q.y2); read(k);
			q.x^=ans; q.y^=ans; q.x2^=ans; q.y2^=ans; k^=ans;
			queryans(k);
		}
	}
}