マスターツリー(持続可能なセグメントツリー)学習ノート

まず離散化し、次に現在のバージョンのセグメントツリーは、前のバージョンのセグメントツリーがlgnノードを変更して得られる
区間減算も満足
よい神

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
using namespace std;
set<int>D;
char c;
bool flag;
inline void read(int&a)
{a=0,flag=false;do c=getchar();while(c!='-'&&(c<'0'||c>'9'));if(c=='-')c=getchar(),flag=true;while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();if(flag)a=-a;}
struct Node
{
	Node *lc,*rc;
    int l,r,sum;
}*Segement_Root[10001];
struct O
{int x,z;}Line[100001];
int data[100001];
int Sorted_data[1000001];

Node*build(int l,int r)
{
	Node*tp=new Node;
	tp->lc=NULL;
	tp->rc=NULL;
	tp->l=l;
	tp->r=r;
	tp->sum=0;
   if(l^r)tp->lc=build(l,(l+r)>>1),tp->rc=build(((l+r)>>1)+1,r);	
   return tp;
}
Node *add(Node *last,int l,int r,int data)
{
	if(l^r)
	{
		Node *tp=new Node;
		*tp=*last;
		if(data<=Sorted_data[(l+r)>>1])
		    tp->lc=add(last->lc,l,(l+r)>>1,data);
		else tp->rc=add(last->rc,((l+r)>>1)+1,r,data);
	   tp->sum++;
	  return tp;
	}
    else
      {
      	Node *tp;
	    tp=new Node;
	    *tp=*last;
	    tp->sum++;
	    return tp;
	  }
}

int K_th(Node *rr,Node *lr,int l,int r,int k)
{
	if(l^r)
      {
      	if(rr->lc->sum-lr->lc->sum>=k)
      	     return K_th(rr->lc,lr->lc,l,(l+r)>>1,k);
      	return K_th(rr->rc,lr->rc,((l+r)>>1)+1,r,k-rr->lc->sum+lr->lc->sum);
	  }
	else return Sorted_data[l];
}
int main()
{
	int n,m;
	read(n);
	read(m);
	for(int i=1;i<=n;i++)
	   read(data[i]),D.insert(data[i]);
	set<int>::iterator tp;
	int con;
	for(tp=D.begin();tp!=D.end();tp++)
	    Sorted_data[++con]=*tp;
	Segement_Root[0]=build(1,con);
	for(int i=1;i<=n;i++) Segement_Root[i]=add(Segement_Root[i-1],1,con,data[i]);
	int l,r,k;
	while(m--)
	 {
	 	read(l),read(r),read(k);
	    printf("%d
",K_th(Segement_Root[r],Segement_Root[l-1],1,con,k));
	 }
	return 0;
}