题解 SP18185 GIVEAWAY - Give Away

写一篇不用 vector 的分块题解

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

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

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

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

代码

#include 
#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>c;
	if(c==0){
	    int x=read(),y=read(),z=read();
	    cout<