BZOJ 3489 A simple rmq problem ——KD-Tree

考前写写板子。

用$(i,pre[i],nxt[i])$来描述一个点，然后就变成了区间求最值的问题。

KD-Tree 由低维转向高维的方法，可以用来敲暴力。

剩下就是KD-Tree的基本操作了。

#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define inf 0x3f3f3f3f
#define L t[o].ch[0]
#define R t[o].ch[1]
#define ll long long
#define mp make_pair
#define maxn 200005

int D,a[maxn],n,m,ans,pre[maxn],nxt[maxn],lst[maxn],rt;
int ql,qr;
struct Point{
	int d[3],mn[3],mx[3],ch[2],v,vmax;
}t[maxn];//i pre nxt

bool operator < (Point a,Point b){return a.d[D]<b.d[D];}

void pushup(int o)
{
	F(i,0,2) t[o].mx[i]=t[o].mn[i]=t[o].d[i];
	F(i,0,2)
	{
		t[o].mx[i]=max(max(t[L].mx[i],t[R].mx[i]),t[o].mx[i]);
		t[o].mn[i]=min(min(t[L].mn[i],t[R].mn[i]),t[o].mn[i]);
	}
	t[o].vmax=max(t[o].v,max(t[L].vmax,t[R].vmax));
}

void init(){F(i,0,2) t[0].mn[i]=inf,t[0].mx[i]=-inf;}

int build(int l,int r,int dir)
{
	D=dir;int mid=l+r>>1;int o=mid;
	nth_element(t+l,t+mid,t+r+1);
	L=l<mid?build(l,mid-1,(dir+1)%3):0;
	R=r>mid?build(mid+1,r,(dir+1)%3):0;
	pushup(o); return o;
}

bool in(int o)
{
	if (t[o].mx[1]>=ql||t[o].mn[2]<=qr) return 0;
	if (t[o].mx[0]>qr||t[o].mx[1]<ql) return 0;
	return 1;
}

bool pin(int o)
{
	if (t[o].d[0]>=ql&&t[o].d[0]<=qr&&t[o].d[1]<ql&&t[o].d[2]>qr) return 1;
	return 0;
}

bool check(int o)
{
	if (t[o].mx[0]<ql||t[o].mn[0]>qr) return 0;
	if (t[o].mn[1]>=ql||t[o].mx[2]<=qr) return 0;
	return 1;
}

void query(int o)
{
	if (!o) return;
	if (in(o)) {ans=max(ans,t[o].vmax);return;}
	if (pin(o)) ans=max(ans,t[o].v);
	if (t[L].vmax>t[R].vmax)
	{
		if (t[L].vmax>ans&&check(L)) query(L);
		if (t[R].vmax>ans&&check(R)) query(R);
	}
	else
	{
		if (t[R].vmax>ans&&check(R)) query(R);
		if (t[L].vmax>ans&&check(L)) query(L);
	}
}

int main()
{
	scanf("%d%d",&n,&m);init();
	F(i,1,n) scanf("%d",&a[i]);
	F(i,1,n) lst[i]=0;
	F(i,1,n) pre[i]=lst[a[i]],lst[a[i]]=i;
	F(i,1,n) lst[i]=n+1;
	D(i,n,1) nxt[i]=lst[a[i]],lst[a[i]]=i;
	F(i,1,n) t[i].d[0]=i,t[i].d[1]=pre[i],t[i].d[2]=nxt[i],t[i].v=a[i];
	rt=build(1,n,0);
	F(i,1,m)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		ql=min((x+ans)%n+1,(y+ans)%n+1);
		qr=max((x+ans)%n+1,(y+ans)%n+1);
		ans=0;query(rt);printf("%d
",ans);
	}
	return 0;
}