二分查找最近一个比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 ;
}
05-11 17:05