写一篇不用 vector 的分块题解

我们可以用一个b数组来代替a数组，然后使用分块的思想达到局部有序

如果是修改操作，单点修改后对一整个块进行重构

如果是查询，则整块使用lower_bound，散块暴力统计

复杂度是\(O(m\sqrt{n}\log \sqrt{n})\)

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int a[N],b[N],pos[N],pl[N],pr[N],n,m,t,q;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
void upd(int p,int val){
    a[p]=val;
    int P=pos[p];
    for(int i=pl[P];i<=pr[P];i++)
	b[i]=a[i];
    sort(b+pl[P],b+1+pr[P]);
}
int query(int l,int r,int c){
    int L=pos[l],R=pos[r],res=0;
    if(L==R){
	for(int i=l;i<=r;i++)
	    if(a[i]>=c) res++;
	return res;
    }
    for(int i=l;i<=pr[L];i++)
	if(a[i]>=c) res++;
    for(int i=pl[R];i<=r;i++)
	if(a[i]>=c) res++;
    for(int i=L+1;i<R;i++){
	int tot=lower_bound(b+pl[i],b+1+pr[i],c)-b-pl[i];
	res+=pr[i]-pl[i]-tot+1;
    }
    return res;
}
signed main(){
    n=read();
    t=sqrt(n);
    for(int i=1;i<=n;i++){
	b[i]=a[i]=read();
	pos[i]=(i-1)/t+1;
    }
    for(int i=1;i<=pos[n];i++){
	pl[i]=pr[i-1]+1,pr[i]=min(n,pl[i]+t-1);
	sort(b+pl[i],b+1+pr[i]);
    }
    q=read();
    for(int i=1;i<=q;i++){
	int c;
	cin>>c;
	if(c==0){
	    int x=read(),y=read(),z=read();
	    cout<<query(x,y,z)<<endl;
	}
	else{
	    int a=read(),b=read();
	    upd(a,b);
	}
    }
    return 0;
}