hdu 4417 区间内比h小的数 划分树

时间：2022-12-15 20:20:04

二分查找最近一个比h小的数

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 using namespace std;

 #define for0n for(i=0;i<n;i++)

 #define for1n for(i=1;i<=n;i++)

 #define for0m for(i=0;i<m;i++)

 #define for1m for(i=1;i<=m;i++)

 #define cl(a) memset(a,0,sizeof(a))

 #define w12 while(scanf("%d%d",&n,&m)!=EOF)

 #define s12 scanf("%d%d",&n,&m);

 #define sa scanf("%d",a[i]);

 #define sb scanf("%d",b[i]);

 #define qq printf("*****\n");

 const int maxn=;

 int n,m,tt;

 const int MAXN = ;

 int tree[][MAXN];//表示每层每个位置的值

 int sorted[MAXN];//已经排序好的数

 int toleft[][MAXN];//toleft[p][i]表示第i层从1到i有数分入左边

 void build(int l,int r,int dep)

 {

     if(l == r)return;

     int mid = (l+r)>>;

     int same = mid - l + ;//表示等于中间值而且被分入左边的个数

     for(int i = l; i <= r; i++) //注意是l,不是one

     if(tree[dep][i] < sorted[mid])

     same--;

     int lpos = l;

     int rpos = mid+;

     for(int i = l;i <= r;i++)

     {

         if(tree[dep][i] < sorted[mid])

         tree[dep+][lpos++] = tree[dep][i];

         else if(tree[dep][i] == sorted[mid] && same > )

         {

             tree[dep+][lpos++] = tree[dep][i];

             same--;

         }

         else

         tree[dep+][rpos++] = tree[dep][i];

         toleft[dep][i] = toleft[dep][l-] + lpos - l;

     }

     build(l,mid,dep+);

     build(mid+,r,dep+);

 }

 //查询区间第k大的数,[L,R]是大区间，[l,r]是要查询的小区间

 int query(int L,int R,int l,int r,int dep,int k)

 {

     if(l == r)return tree[dep][l];

     int mid = (L+R)>>;

     int cnt = toleft[dep][r] - toleft[dep][l-];

     if(cnt >= k)

     {

         int newl = L + toleft[dep][l-] - toleft[dep][L-];

         int newr = newl + cnt - ;

         return query(L,mid,newl,newr,dep+,k);

     }

     else

     {

         int newr = r + toleft[dep][R] - toleft[dep][r];

         int newl = newr - (r-l-cnt);

         return query(mid+,R,newl,newr,dep+,k-cnt);

     }

 }

 int solve(int n,int s,int t,int h)

 {

     int l=;

     int r=(t-s)+;

     int ans=;

     while(l<=r)

     {

         int mid=((l+r)>>);

         int tp=query(,n,s,t,,mid);

         if(tp<=h)

         {

             ans=mid;

             l=mid+;

         }

         else r=mid-;

     }

     return ans;

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

     int i,j,k,h;

     scanf("%d",&tt);

     int ca=;

     while(tt--)

     {

         ca++;

         s12;

         memset(tree,,sizeof(tree));

         for(i = ;i <= n;i++)

         {

             scanf("%d",&tree[][i]);

             sorted[i] = tree[][i];

         }

         sort(sorted+,sorted+n+);

         build(,n,);

         int s,t,k;

         printf("Case %d:\n",ca);

         while(m--)

         {

             scanf("%d%d%d",&s,&t,&h);

             s++;

             t++;

             printf("%d\n",solve(n,s,t,h));

         }

     }

     return ;

 }

相关文章