线段树上的类二分查找总结

非严格二分查找：

情形一：给定序列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 ;
}