数列分块入门 3

用lower_bound求前驱一直WA 代码求调 awa

#include<bits/stdc++.h>
#define int long long
#define mx 100010
using namespace std;
int n,q,sz,cnt,l,r,v,op;
int a[mx],f[mx],bk[mx];
int read(){
	int now=0,nev=1; char c=getchar();
	while(c<'0' || c>'9') { if(c=='-') nev=-1; c=getchar();}
	while(c>='0' && c<='9') { now=(now<<1)+(now<<3)+(c&15); c=getchar(); }
	return now*nev;
}
struct trk{
	int l,r;
	int lt;
	bool fg;
}b[400];
void bd(){
	sz=sqrt(n);
	cnt=ceil(1.0*n/sz);
	for(int i=1;i<=n;i++){
		a[i]=read();
		bk[i]=(i-1)/sz+1;
	}
	int now=0;
	for(int i=1;i<=cnt;i++){
		now++;
		b[i].l=now;
		now+=sz-1;
		b[i].r=now;
		b[i].fg=1;
	}
	b[cnt].r=n;
}
void add(int l,int r,int v){
	int ll=bk[l],rr=bk[r];
	if(ll==rr){
		for(int i=l;i<=r;i++){
			a[i]+=v;
		}
		b[ll].fg=1;
	}else{
		for(int i=l;i<=b[ll].r;i++){
			a[i]+=v;
		}
		for(int i=b[rr].l;i<=r;i++){
			a[i]+=v;
		}
		b[ll].fg=1;
		b[rr].fg=1;
		for(int i=ll+1;i<rr;i++){
			b[i].lt+=v;
		}
	}
}
int ask(int l,int r,int v){
	int ll=bk[l],rr=bk[r];
	int ans=-1;
	if(ll==rr){
		for(int i=l;i<=r;i++){
			if(a[i]+b[ll].lt<v){
				ans=max(ans,a[i]+b[ll].lt);
			}
		}
	}else{
		for(int i=l;i<=b[ll].r;i++){
			if(a[i]+b[ll].lt<v){
				ans=max(ans,a[i]+b[ll].lt);
			}
		}
		for(int i=b[rr].l;i<=r;i++){
			if(a[i]+b[rr].lt<v){
				ans=max(ans,a[i]+b[rr].lt);
			}
		}
		for(int i=ll+1;i<rr;i++){
			int tmp=v-b[i].lt;
			if(b[i].fg){
				b[i].fg=0;
				for(int j=b[i].l;j<=b[i].r;j++){
					f[j]=a[j];
				}
				sort(f+b[i].l,f+b[i].r+1);
			}
			int tt=lower_bound(f+b[i].l,f+b[i].r+1,tmp)-f;
			if(tt!=b[i].l&&a[tt]>=tmp){
				tt--;
			}
			if(a[tt]<tmp){
				ans=max(ans,a[tt]+b[i].lt);
			}
		}
	}
	return ans;
}
signed main(){
	n=read();
	q=n;
	bd();
	while(q--){
		op=read();
		l=read();
		r=read();
		v=read();
		if(op==0){
			add(l,r,v);
		}else{
			printf("%lld\n",ask(l,r,v));
		}
	}
	return 0;
}

另外 如果有插入操作是不是就不能用结构体实现了？（主流好像都是用vector来做分块）