Persistent Point Tree

persistent_point_tree.cpp

/* Sweetdumplings<[email protected]>
   This file is in public domain.
*/
#include <cstdio>
#include <cstring>
#define SIZE 500000
#define TREESIZE 4000
struct Node{
	 int sl,sr,data; //for data
	 int l,r;    //for pointer
};
class PointTree{
public:
	Node d[SIZE];
	int TreeHead[TREESIZE],tot,Treetot,n;
	int buildtree(int l,int r){
		//for building the first(0) tree
		int now=++tot;
		d[now].sl=l;
		d[now].sr=r;
		if (l==r) return now;
		int mid=(l+r)>>1;
		d[now].l=buildtree(l,mid);
		d[now].r=buildtree(mid+1,r);
		return now;
	}
	void init(int n)
	{
		this->n=n;
		memset(TreeHead,0,sizeof(TreeHead));
		tot=0;
		TreeHead[0]=buildtree(1,n);
		Treetot=0;
	}
	void _mark(int now,int pos_in_last_tree,int num,int l,int r){
		d[now].sl=l;d[now].sr=r;
		d[now].data=d[pos_in_last_tree].data+1;//marked
		if (l!=r){
			int mid=(l+r)>>1;
			if (num<=mid){
				//left
				d[now].l=++tot;
				_mark(d[now].l,d[pos_in_last_tree].l,num,l,mid);
				d[now].r=d[pos_in_last_tree].r;
			}else {
				//right
				d[now].r=++tot;
				_mark(d[now].r,d[pos_in_last_tree].r,num,mid+1,r);
				d[now].l=d[pos_in_last_tree].l;
			}
		}
	}
	void mark(int num){
		TreeHead[++Treetot]=++tot;
		_mark(tot,TreeHead[Treetot-1],num,1,n);
	}
	int _findKth(int ltpos,int rtpos,int K){
		if (d[rtpos].sl==d[rtpos].sr) return d[rtpos].sl;

		int data=d[rtpos].data-d[ltpos].data;
		if (data<K){
			//Not Found!
			return -1;
		}
		int ldata=d[d[rtpos].l].data-d[d[ltpos].l].data;
		if (K<=ldata){
			//in left
			return _findKth(d[ltpos].l,d[rtpos].l,K);
		}else {
			//in right
			return _findKth(d[ltpos].r,d[rtpos].r,K-ldata);
		}
	}
	int findKth(int l,int r,int K){
		//find K in (l,r]
		return _findKth(TreeHead[l],TreeHead[r],K);
	}
}t;
int n,m;
int main(){
	scanf("%d%d",&n,&m);
	t.init(m);
	for (int i=1;i<=n;++i){
		int d;
		scanf("%d",&d);
		t.mark(d);
	}
	int q;
	scanf("%d",&q);
	for (int i=1;i<=q;++i){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",t.findKth(l,r,k));
	}
	return 0;
}