sdut 2610:Boring Counting（第四届山东省省赛原题，划分树 + 二分）

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <algorithm>
  4 using namespace std;
  5 #define MAXN 100005
  6 struct Divide_tree{
  7     int arr[MAXN];  //原数组
  8     int sorted[MAXN];   //排序后数组
  9     int sum[20][MAXN];  //记录第i层1~j划分到左子树的元素个数(包括j）
 10     int dat[20][MAXN];  //记录第i层元素序列
 11     void build(int c,int L,int R)   //建树，主要是建立sum[][]和dat[][]数组
 12     {
 13         int mid = (L+R)>>1;
 14         int lsame = mid-L+1;    //lsame用来记录和中间值val_mid相等的，且可以分到左孩子的数的个数
 15                                 //简单来说就是可以放入左孩子的,与中间值val_mid相等的数的个数
 16         int lp=L,rp=mid+1;  //当前节点的左孩子和右孩子存数的起点
 17         for(int i=L;i<mid;i++)  //获得一开始的lsame
 18             if(sorted[i]<sorted[mid])
 19                 lsame--;
 20         for(int i=L;i<=R;i++){  //从前往后遍历一遍，
 21                                 //确定当前节点区间内的所有元素的归属（放在左孩子或者放在右孩子）
 22             if(i==L) sum[c][i]=0;
 23             else sum[c][i]=sum[c][i-1];
 24             if(dat[c][i]<sorted[mid]){  //当前元素比中间值val_mid小，放入左孩子
 25                 dat[c+1][lp++] = dat[c][i];
 26                 sum[c][i]++;
 27             }
 28             else if(dat[c][i]>sorted[mid])  //当前元素比中间值val_mid大，放入右孩子
 29                 dat[c+1][rp++] = dat[c][i];
 30             else{  //当前元素值与中间值val_mid相等，根据lsame数判断放入左孩子还是右孩子
 31                 if(lsame){
 32                     lsame--;
 33                     sum[c][i]++;
 34                     dat[c+1][lp++]=sorted[mid];
 35                 }
 36                 else{
 37                     dat[c+1][rp++]=sorted[mid];
 38                 }
 39             }
 40         }
 41         if(L==R) return ;   //递归出口，遇到叶子节点
 42         build(c+1,L,mid);   //递归进入左孩子区间
 43         build(c+1,mid+1,R); //递归进入右孩子区间
 44     }
 45     int query(int c,int L,int R,int ql,int qr,int k)
 46     {
 47         //c为树的层数，L,R为当前节点的区间范围，ql,qr为查询的区间范围，k为查询范围内第k大的数
 48         if(L==R)    //递归出口，返回第k大的数
 49             return dat[c][L];
 50         int s;  //记录[L,ql-1]中进入左孩子的元素的个数
 51         int ss; //记录[ql,qr]中进入左孩子的元素的个数
 52         int mid=(L+R)>>1;
 53         if(L==ql){  //端点重合的情况，单独考虑
 54             s=0;
 55             ss=sum[c][qr];
 56         }
 57         else {
 58             s=sum[c][ql-1];
 59             ss=sum[c][qr]-s;
 60         }
 61         if(k<=ss)   //左孩子的元素个数大于k个，说明第k大的元素一定在左孩子区间中，到左孩子中查询
 62             return query(c+1,L,mid,L+s,L+s+ss-1,k);
 63         else
 64             return query(c+1,mid+1,R,mid+1+ql-s-L,mid+1+qr-s-ss-L,k-ss);
 65     }
 66 };
 67 Divide_tree tree;
 68 int L,R,A,B;
 69 int N,M;
 70 int downbearch(int low,int high)    //找到第一个比B小的数是 第几大的数（用划分树）
 71 {
 72     int mid = (low+high+1)>>1;
 73     while(low<high){
 74         if( tree.query(0,1,N,L,R,mid)<=B )  //查询第mid大的数是否比下界B小。
 75                                 //如果mid比B小，说明要找的位置在mid右边，low应该右移，即
 76             low = mid;
 77         else //否则，说明要找的位置应该在mid左边，即
 78             high = mid-1;
 79         mid = (low+high+1)>>1;
 80     }
 81     if( tree.query(0,1,N,L,R,mid)<=B )    //找到了
 82         return mid;
 83     else
 84         return -1;
 85 }
 86 int upbearch(int low,int high)  //找到第一个比A大的数是 第几大的数（用划分树）
 87 {
 88     int mid = (low+high+1)>>1;
 89     while(low<high){
 90         if( tree.query(0,1,N,L,R,mid)>=A )  //查询第mid大的数是否比上界A大。
 91                                 //如果mid比A大，说明要找的位置在mid左边，high应该左移，即
 92             high = mid;
 93         else //否则，说明要找的位置应该在mid右边，即
 94             low = mid+1;
 95         mid = (low+high)>>1;
 96     }
 97     if(tree.query(0,1,N,L,R,mid)>=A )    //找到了
 98         return mid;
 99     else
100         return -1;
101 }
102 int main()
103 {
104     int i,Case,T;
105     scanf("%d",&T);
106     for(Case=1;Case<=T;Case++){
107         scanf("%d%d",&N,&M);
108         for(i=1;i<=N;i++){   //输入
109             scanf("%d",&tree.arr[i]);
110             tree.sorted[i]=tree.dat[0][i]=tree.arr[i];
111         }
112         sort(tree.sorted+1,tree.sorted+N+1);
113         tree.build(0,1,N);
114         printf("Case #%d:\n",Case);
115         for(i=1;i<=M;i++){
116             scanf("%d%d%d%d",&L,&R,&A,&B);
117             int up = downbearch(1,R-L+1);
118             int down = upbearch(1,R-L+1);
119             if(up==-1||down==-1||A>B||L>R)
120                 printf("0\n");
121             else printf("%d\n",up-down+1);
122         }
123     }
124     return 0;
125 }