划分树POJ2104,POJ2761,HDU2665,HDU3743

　　做了几道划分树的题目，划分树的效率很高，用来求区间第K小值和区间小于K小值的和，每次动态询问的复杂度为O(logn)。
其中POJ2104,POJ2761,HDU2665为典型的求区间第K小值，HDU3743还加上了求和的操作，推荐去做一做。
　　下面是HUD3743的代码：
  1 //STATUS:C++_AC_343MS_30048KB
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 #include<math.h>
  6 #include<iostream>
  7 #include<string>
  8 #include<algorithm>
  9 #include<vector>
 10 #include<queue>
 11 #include<stack>
 12 #include<map>
 13 using namespace std;
 14 #define LL __int64
 15 #define pii pair<int,int>
 16 #define mem(a,b) memset(a,b,sizeof(a))
 17 #define lson l,mid,rt<<1
 18 #define rson mid+1,r,rt<<1|1
 19 #define PI acos(-1.0)
 20 const int N=100010,INF=0x3f3f3f3f,MOD=10000,STA=8000010;
 21 //const LL LNF=0x3f3f3f3f3f3f3f3f;
 22 const double DNF=1e13;
 23 //
 24 inline int Max(int a,int b){return a>b?a:b;}
 25 inline int Min(int a,int b){return a<b?a:b;}
 26 void swap(int& a,int& b){int t=a;a=b;b=t;}
 27 void swap(LL& a,LL& b){LL t=a;a=b;b=t;}
 28 //
 29 
 30 int val[N],num[20][N],cnt[20][N];
 31 LL sum[20][N],s[N];
 32 int T,n,m,knum;
 33 LL ksum;
 34 
 35 void build(int u,int l,int r)
 36 {
 37     if(l==r){
 38         sum[u][l]=num[u][l];
 39         return;
 40     }
 41     int i,mid,midnum,kl,kr,lsame;
 42     LL s=0;
 43     mid=(l+r)>>1;
 44     kl=l;kr=mid+1;lsame=mid-l+1;
 45     midnum=val[mid];
 46     for(i=l;i<=mid;i++)   //注意这里需要统计等于中位数放在左儿子区间的个数
 47         if(val[i]<midnum)lsame--;
 48     for(i=l;i<=r;i++){
 49         if(num[u][i]<midnum || (num[u][i]==midnum && lsame)){  //注意等于中位数情况
 50             if(num[u][i]==midnum)lsame--;
 51             num[u+1][kl++]=num[u][i];
 52             sum[u][i]=s+(LL)num[u][i];
 53             s=sum[u][i];
 54         }
 55         else {
 56             num[u+1][kr++]=num[u][i];
 57             sum[u][i]=s;
 58         }
 59         cnt[u][i]=kl-l;
 60     }
 61     build(u+1,l,mid);
 62     build(u+1,mid+1,r);
 63 }
 64 
 65 void query(int u,int l,int r,int a,int b,int k)
 66 {
 67     if(a==b){   //注意这里可能l<r啦
 68         knum=num[u][a];   
 69         ksum+=num[u][a];
 70         return;
 71     }
 72     int i,t,mid,cnta;
 73     mid=(l+r)>>1;
 74     cnta=(a>l?cnt[u][a-1]:0);   //注意l==a
 75     t=cnt[u][b]-cnta;
 76     if(k<=t){
 77         query(u+1,l,mid,l+cnta,l+cnt[u][b]-1,k);
 78     }
 79     else{
 80         ksum+=sum[u][b]-(a>l?sum[u][a-1]:0);
 81         query(u+1,mid+1,r,mid+a-l-cnta+1,mid+b-l-cnt[u][b]+1,k-t);
 82     }
 83 }
 84 
 85 int main()
 86 {
 87   //  freopen("in.txt","r",stdin);
 88     int i,j,sz=1,a,b,k;
 89     LL ans;
 90     scanf("%d",&T);
 91     while(T--)
 92     {
 93         mem(num,0);
 94         scanf("%d",&n);
 95         s[0]=0;
 96         for(i=1;i<=n;i++){
 97             scanf("%d",&val[i]);
 98             num[0][i]=val[i];
 99             s[i]=s[i-1]+val[i];
100         }
101         sort(val+1,val+n+1);
102         build(0,1,n);
103 
104         scanf("%d",&m);
105         printf("Case #%d:\n",sz++);
106         while(m--){
107             scanf("%d%d",&a,&b);
108             a++,b++;
109             k=(b-a)/2+1;
110             ksum=0;
111             query(0,1,n,a,b,k);
112             ans=(LL)knum*k-ksum;
113             ans+=s[b]-s[a-1]-ksum-(LL)knum*(b-a+1-k);
114             printf("%I64d\n",ans);
115         }
116         putchar('\n');
117     }
118     return 0;
119 }