주석 트 리 초보

의장 나 무 는 나 무 를 나 누 는 것 보다 효율 이 떨 어 지 는 신기 한 것 이다.
생각 에 대해 서 는 그림 으로 보 여 주세요.
poj 2104 코드 첨부:
#include
#include
#include
#include
#include
#include
#include
#define M 100000+5
using namespace std;
/*
 poj2104 [l,r] k           
*/
struct node
{
	int l,r,size;
	node(){l=r=size=0;
	}
}T[20*M];
int root[M];//   i     
int tot;//     
int m;
int a[M];//    
int t[M];//     1,5,7,9       t[1]=1 t[2]=5 t[3]=7
int pos(int x)
{
	return lower_bound(t+1,t+m+1,x)-t;//            
	/*int l=1,r=m;
	while(l=k)return query(T[i].l,T[j].l,l,mid,k);
	else return query(T[i].r,T[j].r,mid+1,r,k-cha);
}
int main()
{
	while(scanf("%d%d",&n,&q)!=EOF)
	{
		for(int i=1;i<=n;i++)
    	{
		    scanf("%d",&a[i]);
	    	t[i]=a[i];
    	}
    	sort(t+1,t+n+1,cmp);
    	m=unique(t+1,t+n+1)-t-1;
    	m++;t[m]=0x3f3f3f3f; 
    	tot=0;
    	root[0]=build(1,m);//    
    	for(int i=1;i<=n;i++)//        Logn      
	    {
		    int k=pos(a[i]);//k a[i]                
		    root[i]=updata(root[i-1],1,m,k,1);//     ,       
    	} 
	    //           
	    for(int i=1;i<=q;i++)
    	{
	    	int l,r,k;//  [l,r]     k     
		    scanf("%d%d%d",&l,&r,&k);
	    	printf("%d
",t[query(root[l-1],root[r],1,m,k)]);// [l,r] k } } return 0; }

좋은 웹페이지 즐겨찾기