hdu 4217 線段樹

題目大意： t 組測試，每組測試有 n 個數（1～n），有 k 次循環，每次取出第k小的數，求所有取出的數字之和。

[cpp]
#include<iostream>  
#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
#include<algorithm>  
#define SIZE 262145  
using namespace std; 
int array[SIZE<<1]; 
void creat(int left,int right,int root) 
{ 
    int m; 
    array[root] = right-left+1;//每個節點記錄包含的數字個數  
    if(left == right){ 
        return; 
    } 
    m=(right+left)/2; 
    creat(left,m,root<<1);      //array[root]的左孩子為array[2*root]  
    creat(m+1,right,root<<1|1); //array[root]的右孩子為array[2*root+1]  
} 
int Del(int left,int right,int root,int key) 
{ 
    int m,flag; 
    array[root]--; 
    if(left == right){ 
        return right; 
    } 
    m=(right+left)/2; 
    if(key<=array[root<<1]){//左子樹的葉子節點數大於key  
        flag=Del(left,m,root<<1,key); 
    } 
    else{ 
        key-=array[root<<1];//在右子樹中找，key要減去左子樹包含的葉子節點數  
        flag=Del(m+1,right,root<<1|1,key); 
    } 
    return flag; 
} 
int main() 
{ 
    int t,n,k,kk,i,j; 
    long long sum; 
    scanf("%d",&t); 
    for(i=1;i<=t;i++){ 
        sum=0; 
        scanf("%d%d",&n,&k); 
        creat(1,n,1); 
        for(j=0;j<k;j++){ 
            scanf("%d",&kk); 
            sum+=Del(1,n,1,kk); 
        } 
        printf("Case %d: %lld\n",i,sum); 
    } 
    return 0; 
} 

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#define SIZE 262145
using namespace std;
int array[SIZE<<1];
void creat(int left,int right,int root)
{
    int m;
    array[root] = right-left+1;//每個節點記錄包含的數字個數
    if(left == right){
        return;
    }
    m=(right+left)/2;
    creat(left,m,root<<1);      //array[root]的左孩子為array[2*root]
    creat(m+1,right,root<<1|1); //array[root]的右孩子為array[2*root+1]
}
int Del(int left,int right,int root,int key)
{
    int m,flag;
    array[root]--;
    if(left == right){
        return right;
    }
    m=(right+left)/2;
    if(key<=array[root<<1]){//左子樹的葉子節點數大於key
        flag=Del(left,m,root<<1,key);
    }
    else{
        key-=array[root<<1];//在右子樹中找，key要減去左子樹包含的葉子節點數
        flag=Del(m+1,right,root<<1|1,key);
    }
    return flag;
}
int main()
{
    int t,n,k,kk,i,j;
    long long sum;
    scanf("%d",&t);
    for(i=1;i<=t;i++){
        sum=0;
        scanf("%d%d",&n,&k);
        creat(1,n,1);
        for(j=0;j<k;j++){
            scanf("%d",&kk);
            sum+=Del(1,n,1,kk);
        }
        printf("Case %d: %lld\n",i,sum);
    }
    return 0;
}