区间第k小值logn方法---划分树模板---HDOJ 4417 Super Mario

75 阅读 0 评论 50 点赞

我是靠谱客的博主慈祥鞋子，最近开发中收集的这篇文章主要介绍区间第k小值logn方法---划分树模板---HDOJ 4417 Super Mario，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

http://acm.hdu.edu.cn/showproblem.php?pid=4417

------ 划分树 + 二分

划分树模板求区间第k小数，那么我们每次询问时就二分查找当前H算第几小数，那么显然答案就出来了~需要注意的就是区间全包括和全不包括需要特判一下，不然会RE。。。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <vector>
  6 #include <stack>
  7 #include <queue>
  8 #include <map>
  9 #include <algorithm>
 10 #include <string>
 11 #include <cstring>
 12 #define MID(x,y) ((x+y)>>1)
 13 
 14 using namespace std;
 15 #define M 100010
 16 struct Seg_Tree
 17 {
 18     int left,right;
 19     int mid()
 20     {
 21         return (left + right) >> 1;
 22     }
 23 }tt[M<<2];
 24 int len;
 25 int sorted[M];
 26 int toLeft[40][M];
 27 int val[40][M];
 28 
 29 void build(int l,int r,int d,int idx)
 30 {
 31     tt[idx].left = l;
 32     tt[idx].right = r;
 33     if(tt[idx].left == tt[idx].right)    return ;
 34     int mid = tt[idx].mid();
 35     int lsame = mid - l + 1;//lsame表示和val_mid相等且分到左边的
 36     for(int i = l ; i <= r ; i ++)
 37     {
 38         if(val[d][i] < sorted[mid])
 39         {
 40             lsame --;//先假设左边的数(mid - l + 1)个都等于val_mid,然后把实际上小于val_mid的减去
 41         }
 42     }
 43     int lpos = l;
 44     int rpos = mid + 1;
 45     int same = 0;
 46     for(int i = l ; i <= r ; i ++)
 47     {
 48         if(i == l)
 49         {
 50             toLeft[d][i] = 0;//toLeft[i]表示[ tt[idx].left , i ]区域里有多少个数分到左边
 51         }
 52         else
 53         {
 54             toLeft[d][i] = toLeft[d][i-1];
 55         }
 56         if(val[d][i] < sorted[mid])
 57         {
 58             toLeft[d][i] ++;
 59             val[d+1][lpos++] = val[d][i];
 60         }
 61         else if(val[d][i] > sorted[mid])
 62         {
 63             val[d+1][rpos++] = val[d][i];
 64         }
 65         else
 66         {
 67             if(same < lsame)
 68             {//有lsame的数是分到左边的
 69                 same ++;
 70                 toLeft[d][i] ++;
 71                 val[d+1][lpos++] = val[d][i];
 72             }
 73             else
 74             {
 75                 val[d+1][rpos++] = val[d][i];
 76             }
 77         }
 78     }
 79     build(l,mid,d+1,idx<<1);
 80     build(mid+1,r,d+1,idx<<1|1);
 81 }
 82 
 83 int query(int l,int r,int k,int d,int idx) {
 84     if(l == r)
 85     {
 86         return val[d][l];
 87     }
 88     int s;//s表示[ l , r ]有多少个分到左边
 89     int ss;//ss表示 [tt[idx].left , l-1 ]有多少个分到左边
 90     if(l == tt[idx].left)
 91     {
 92         s = toLeft[d][r];
 93         ss = 0;
 94     }
 95     else
 96     {
 97         s = toLeft[d][r] - toLeft[d][l-1];
 98         ss = toLeft[d][l-1];
 99     }
100     if(s >= k)
101     {//有多于k个分到左边,显然去左儿子区间找第k个
102         int newl = tt[idx].left + ss;
103         int newr = tt[idx].left + ss + s - 1;//计算出新的映射区间
104         return query(newl,newr,k,d+1,idx<<1);
105     }
106     else
107     {
108         int mid = tt[idx].mid();
109         int bb = l - tt[idx].left - ss;//bb表示 [tt[idx].left , l-1 ]有多少个分到右边
110         int b = r - l + 1 - s;//b表示 [l , r]有多少个分到右边
111         int newl = mid + bb + 1;
112         int newr = mid + bb + b;
113         return query(newl,newr,k-s,d+1,idx<<1|1);
114     }
115 }
116 
117 int BS(int r, int h, int L, int R)
118 {
119     int l = 0;
120     while(l < r)
121     {
122         int mid = MID(l,r);
123         if (query(L,R,mid,0,1) > h)
124             r = mid;
125         else    l = mid + 1;
126     }
127     return l;
128 }
129 
130 int main()
131 {
132     //freopen("test.in","r+",stdin);
133 
134     int t,caseo = 1;
135     scanf("%d", &t);
136     while(t--)
137     {
138         printf("Case %d:n",caseo ++);
139         int n,m;
140         scanf("%d%d",&n, &m);
141         for (int i = 1;i <= n; i++)
142         {
143             scanf("%d", &val[0][i]);
144             sorted[i] = val[0][i];
145         }
146         sort(sorted+1,sorted+n+1);
147         build(1,n,0,1);
148         for (int i = 0; i < m; i++)
149         {
150             int L,R,H;
151             scanf("%d%d%d",&L, &R, &H);
152             if (query(L+1,R+1,1,0,1) > H )
153                 puts("0");
154             else if (query(L+1,R+1,R-L+1,0,1) <= H)
155                 printf("%dn",R-L+1);
156             else
157             {
158                 int res = BS(R-L+1,H,L+1,R+1);
159                 while(res != 0 && query(L+1,R+1,res,0,1) > H)
160                     res--;
161                 printf("%dn",res);
162 
163             }
164         }
165     }
166     return 0;
167 }