are you ok?

题目描述
一个长度为n的数组a，数组下标从0开始。现在要求你查询从左到右第一个不小于k的数字a[i], 输出i，并且马上把a[i-1]++；如果你找到的a[i]中的i等于0，那么a[0-1]是非法的，因此只要输出i就行了，不进行a[i-1]++；如果你在数组中找不到一个数字不小于k，则输出”are you ok ”

输入描述:
多组输入，输入直到遇到EOF为止；

第一行输入两个整数n和q，表示数组a中有n个整数，q表示q次查询；

第二行输入n个整数；

第三行到后2+q行，每行输入一个数字k，表示要求你查询从左到右第一个不小于k的数字并马上输出。

注意：1 < n, q <= 1e6, a[i]和k是一个int型的整数
输出描述:
见输入。
示例1

输入
复制
3 4
1 2 8
2
2
8
9

输出
复制
1
0
2
are you ok

本来以为要写一个线段树套主席树，突然一想，其实我们维护最大值即可。为什么呢，我们每次考虑大区间的最大值，如果最大值大于等于k，那么这个区间肯定存在一个合法的值，然后我们递归考虑左区间，如果左区间的最大值大于等于k，那么我们递归考虑左区间，不然递归考虑右区间。而且因为我们优先考虑左区间，所以找到的必然是最左边的值。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e6+10;
int n,q,a[N];
struct node{
	int l,r,max;
}t[N<<2];
inline void push_up(int p){
	t[p].max=max(t[p<<1].max,t[p<<1|1].max);
}
void build(int p,int l,int r){
	t[p].l=l;	t[p].r=r;	
	if(l==r){
		t[p].max=a[l];	return ;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);
	push_up(p);
}
void change(int p,int x){
	if(t[p].l==t[p].r){
		t[p].max++;	return ;
	}
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid)	change(p<<1,x);
	else	change(p<<1|1,x);
	push_up(p);
}
int ask(int p,int x){
	if(t[p].l==t[p].r){
		return t[p].l;
	}
	int mid=t[p].l+t[p].r>>1;
	if(t[p<<1].max>=x)	return ask(p<<1,x);
	else	return ask(p<<1|1,x);
}
signed main(){
	while(~scanf("%d %d",&n,&q)){
		for(int i=1;i<=n;i++)	scanf("%d",&a[i]);	build(1,1,n);	
		while(q--){
			int x;	scanf("%d",&x);
			if(t[1].max<x){
				puts("are you ok");	continue;
			}
			int id=ask(1,x);	printf("%d\n",id-1);
			if(id!=1)	change(1,id-1);
		}
	}
	return 0;
}