如果值域到 1e9 这样的大数，不离散化的情况下，判断操作序列中是否还有询问这样的方法复杂度还对吗。这样写了几个题都能过的样子。

P2617 的代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read(){
	register int x=0,v=0,ch=getchar();
	while('0'>ch || ch>'9'){
		if(ch=='-')v=1;
		ch=getchar();
	}
	while('0'<=ch && ch<='9'){
		x=x*10+(ch^'0');
		ch=getchar();
	}
	return v?-x:x;
}
const int MAX=1e5+5;
int n,a[MAX],m;
struct OPT{
	int opt,l,r,v,id;
}q[MAX+MAX+MAX],q1[MAX+MAX+MAX],q2[MAX+MAX+MAX];
int ans[MAX];

int C[MAX];
inline void add(int x,int v){
	for(register int i=x;i<=n;i+=(i&-i))C[i] += v; 
}
inline int query(int x){
	int ret=0;
	for(register int i=x;i;i-=(i&-i))ret += C[i];
	return ret;
}
void solve(int l,int r,int L,int R){
	if(l>r || L>R)return ;
	if(l==r){
		for(register int i=L;i<=R;++i)if(q[i].opt == 1) ans[q[i].id] = l;
		return ;
	}
	int mid=l+r>>1,top1=0,top2=0,c1=0,c2=0;
	for(register int i=L;i<=R;++i){
		if(q[i].opt == 1){ 
			int ret = query(q[i].r) - query(q[i].l - 1);
			if(q[i].v <= ret){
				q1[++top1] = q[i];
				++c1;
			}else {
				q2[++top2] = q[i];
				q2[top2].v -= ret;
				++c2;
			}
		}else {
			if(q[i].v <= mid){
				add(q[i].l,q[i].id);
				q1[++top1] = q[i];
			}else q2[++top2] = q[i];
		}
	}
	for(register int i=1;i<=top1;++i)
		if(q1[i].opt == 2) add(q1[i].l,-q1[i].id);
	for(register int i=1;i<=top1;++i)q[L+i-1] = q1[i];
	for(register int i=1;i<=top2;++i)q[L+i+top1-1] = q2[i];
	if(c1)solve(l,mid,L,L+top1-1); // 就在这里判断一下
	if(c2)solve(mid+1,r,L+top1,R);
}
signed main(){
	n=read(),m=read();
	int top=0,tim=0;
	for(register int i=1;i<=n;++i)a[i]=read(),q[++top] = (OPT){2,i,-1,a[i],1};
	char s[3];
	for(register int i=1;i<=m;++i){
		int l,r,k;scanf("%s",s);
		if(s[0]=='Q')l=read(),r=read(),k=read(),q[++top] = (OPT){1,l,r,k,++tim};
		else {
			l=read(),k=read();
			q[++top] = (OPT){2,l,-1,a[l],-1};
			q[++top] = (OPT){2,l,-1,k,1};
			a[l] = k;
		}
	}
	solve(0,1e9,1,top);
	for(register int i=1;i<=tim;++i)printf("%d\n",ans[i]);
	return 0;
}