非严格二分查找：
情形一：给定序列a[1]~a[N], 每次询问给定一个数v, 一个位置pos， 从a[pos+1]~a[N]中找到第一个大于v的元素的下标
考虑建立一棵普通的位置线段树， 树上节点维护当前位置区间的最大值； 每次查找时从根递归向下查找， 对于当前区间 [ l，r ]：
0. 若当前节点为叶子结点， 若结点的值满足 > v ， 返回下标即可；
1. 若pos <= mid： 若左子树最大值大于v（约束）， 则左子树可能存在解， 递归查找左子树； 若左子树查找到解，则直接返回该解（这是一个重要剪枝，可以大幅优化时间， 显然此时即使右子树存在大于v的元素，也不可能是第一个出现的了，所以没必要再查）， 否则， 若右子树最大值大于v（约束）， 递归查找右子树；
2. 若pos>mid： 若右子树最大值大于v（约束）， 递归查找右子树；
tip：不存在解的话返回个INF就行， 代表第一个大于v的元素在右侧无限远处， 也即不存在该元素
例题：HDU - 5875
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mid ((l+r)>>1)
const int maxn = 1e5+10;
const int INF = 1e9+7;
/*此题与hdu6703做法相似， 都是在线段树上查找第一个(位置最左或值最小)满足约束条件的元素！！*/
int n,val[maxn],minn[maxn<<2];
void build(int l,int r,int u){
if(l==r) {minn[u]=val[l]; return ;}
build(l,mid,u<<1); build(mid+1,r,u<<1|1);
minn[u]=min(minn[u<<1],minn[u<<1|1]);
}
int query(int p,int v,int l,int r,int u){
if(l==r) {return minn[u]<=v?l:INF;}
int res=INF;
if(p<=mid){
if(minn[u<<1]<=v) res=query(p,v,l,mid,u<<1);
if(res==INF&&minn[u<<1|1]<=v) res=query(p,v,mid+1,r,u<<1|1);
}else if(minn[u<<1|1]<=v)
res=query(p,v,mid+1,r,u<<1|1);
return res;
}
int main(){
int t,q,i,j,k,l,r,ans,cur,tmp;
while(cin>>t){
while(t--){
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",val+i);
build(1,n,1);
scanf("%d",&q);
for(;q;q--){
scanf("%d%d",&l,&r);
ans=val[l]; cur=l+1;
for(;cur<=r&&ans;cur=tmp+1){
tmp=query(cur,ans,1,n,1);
if(tmp<=r) ans%=val[tmp];
}
printf("%d\n",ans);
}
}
}
} 情形二：给定序列a[1]~a[N], 每次询问给定一个数v ( 可能需要取离散值 ) , 一个位置pos， 从a[pos+1]~a[N]中找到最小的大于v的元素的值
考虑建立一棵权值线段树， 树上节点维护当前段权值中的最右侧出现的位置（若某个权值不存在，则令其出现位置为0，这样保证了这个数永远不会被查找到）； 每次查找时从根递归向下查找， 对于当前区间 [ l，r ]：
1. 若v <= mid： 若左子树中最右位置 > pos（约束）， 则左子树可能存在解， 递归查找左子树； 若左子树查找到解，则直接返回该解（重要剪枝，原理同上）， 否则， 若右子树中最右位置 > pos（约束）， 递归查找右子树；
2. 若v > mid： 若右子树最右位置大于pos（约束）， 递归查找右子树；
tip：不存在解的话返回个INF就行， 代表第最小的大于v的元素是INF， 也即不存在对应元素
例题：HDU - 6703
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
const int MAX = 1e5;
const int INF = 1e8;
/*此题与hdu5875做法相似， 都是在线段树上查找第一个(位置最左或值最小)满足约束条件的元素*/
int a[MAX+5],maxp[(MAX+5)<<2];
set<int> ss;
void add(int p,int v,int l,int r,int u) {
if(l == r) {maxp[u]=max(maxp[u],v); return ;}
p <= mid ? add(p,v,l,mid,u<<1) : add(p,v,mid+1,r,u<<1|1);
maxp[u]=max(maxp[u<<1],maxp[u<<1|1]);
return ;
}
int query(int p,int v,int l,int r,int u) {
if(l == r) return maxp[u]>=v?l:INF;
int res=INF;
if(p<=mid){
if(maxp[u<<1]>=v) res=query(p,v,l,mid,u<<1);
if(res==INF&&maxp[u<<1|1]>=v) res=query(p,v,mid+1,r,u<<1|1);
return res;
}
else if(maxp[u<<1|1]>=v)
res=query(p,v,mid+1,r,u<<1|1);
return res;
}
int main()
{
int n,m,k,t,r,op,pos,ans;
// freopen("data.in","r",stdin);
cin>>t;
while(t--) {
scanf("%d%d",&n,&m);
ss.clear(); ss.insert(n+1); ans=0; memset(maxp,0,sizeof(maxp));
for(int i = 1; i<=n; i++)
scanf("%d",a+i), add(a[i],i,1,n,1);
while(m--) {
scanf("%d",&op);
if(op == 1) {
scanf("%d",&pos); pos^=ans;
ss.insert(a[pos]);
}
else {
scanf("%d%d",&r,&k);
r ^= ans;k ^= ans;
ans = query(k,r+1,1,n,1);
int tmp = *ss.lower_bound(k);
ans = min(ans,tmp);
printf("%d\n",ans);
}
}
}
return 0 ;
} 总结：对于这类问题， 虽然查找的过程非严格的二分， 但由于存在约束条件的限制以及左子树找到解就直接返回的操作，起到了一定程度的剪枝作用，因此仍可以接近二分查找的速度很快的找到解。此外，若找的东西与位置有关（诸如：找右侧第一个满足约束的元素）， 则考虑建立位置线段树，每次在满足约束下优先考虑左/右子树； 若找的东西与权值有关（诸如：找右侧最小的满足约束的元素）， 则考虑建立权值线段树，每次在满足约束下优先考虑左/右子树。
严格二分查找：
情形三： 给定序列a[1]~a[N], 每次查找对应区间内的小于某元素v的值的个数
建立主席树， 每次找到对应的权值线段树， 在当前权值区间 [ l , r] 下， 若v <= mid 则递归统计左子树； 若v > mid , 则递归统计右子树， 同时直接加上左子树的元素个数num即可； 若当前到达叶子结点， 应该判断当前值是否小于v（合法性判断）， 满足约束下才返回节点的num， 否则应该返回0
京公网安备 11010502036488号