划分树

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <string.h>
  5 using namespace std;
  6 const int MAXN = 1010;
  7 int tree[20][MAXN];
  8 int sorted[MAXN];
  9 int toleft[20][MAXN];
 10 long long sum[20][MAXN];
 11 
 12 void build(int l,int r,int dep)
 13 {
 14     if(l == r)
 15     {
 16         sum[dep][l] = sum[dep][l-1]+tree[dep][l];
 17         return;
 18     }
 19     int mid = (l+r)>>1;
 20     int same = mid - l + 1;
 21     for(int i = l; i <= r; i++)
 22     {
 23         if(tree[dep][i] < sorted[mid])
 24             same--;
 25         sum[dep][i] += sum[dep][i-1]+tree[dep][i];
 26     }
 27     int lpos = l;
 28     int rpos = mid+1;
 29     for(int i = l; i <= r; i++)
 30     {
 31         if(tree[dep][i] < sorted[mid])
 32             tree[dep+1][lpos++] = tree[dep][i];
 33         else if(tree[dep][i] == sorted[mid] && same > 0)
 34         {
 35             tree[dep+1][lpos++] = tree[dep][i];
 36             same--;
 37         }
 38         else
 39             tree[dep+1][rpos++] = tree[dep][i];
 40         toleft[dep][i] = toleft[dep][l-1] + lpos - l;
 41     }
 42     build(l,mid,dep+1);
 43     build(mid+1,r,dep+1);
 44 }
 45 long long ans;
 46 int query(int L,int R,int l,int r,int dep,int k)
 47 {
 48     if(l == r)return tree[dep][l];
 49     int mid = (L+R)>>1;
 50     int cnt = toleft[dep][r] - toleft[dep][l-1];
 51     if(cnt >= k)
 52     {
 53         int ee = r-L+1-(toleft[dep][r]-toleft[dep][L-1])+mid;
 54         int ss = l-L-(toleft[dep][l-1]-toleft[dep][L-1])+mid;
 55         ans += sum[dep+1][ee]-sum[dep+1][ss];
 56         int newl = L + toleft[dep][l-1]-toleft[dep][L-1];
 57         int newr = newl + cnt -1;
 58         return query(L,mid,newl,newr,dep+1,k);
 59     }
 60     else
 61     {
 62         int s = L + toleft[dep][l-1] - toleft[dep][L-1];
 63         int e = s + cnt - 1;
 64         ans -= sum[dep+1][e] - sum[dep+1][s-1];
 65         int newr = r + toleft[dep][R] - toleft[dep][r];
 66         int newl = newr - (r-l+1-cnt) + 1;
 67         return query(mid+1,R,newl,newr,dep+1,k-cnt);
 68     }
 69 }
 70 int main()
 71 {
 72     int T;
 73     int n;
 74     scanf("%d",&T);
 75     int iCase = 0;
 76     while(T--)
 77     {
 78         iCase++;
 79         scanf("%d",&n);
 80         memset(tree,0,sizeof(tree));
 81         memset(sum,0,sizeof(sum));
 82         for(int i = 1; i <= n; i++)
 83         {
 84             scanf("%d",&tree[0][i]);
 85             sorted[i] = tree[0][i];
 86         }
 87         sort(sorted+1,sorted+n+1);
 88         build(1,n,0);
 89         printf("Case #%d:
",iCase);
 90         int m,l,r;
 91         scanf("%d",&m);
 92         while(m--)
 93         {
 94             scanf("%d%d",&l,&r);
 95             l++;
 96             r++;
 97             ans = 0;
 98             int tmp = query(1,n,l,r,0,(l+r)/2-l+1);
 99             if((l+r)%2)ans-=tmp;
100             printf("%lld
",ans);
101         }
102         printf("
");
103     }
104     return 0;
105 }