P2801 教主的魔法

P2801 教主的魔法

分块裸题，作为初学者用来练手。

题意

维护长度为 $n$ 序列，有两种操作：

1. 区间加法。
2. 求区间中大于 $k$ 的数的个数。

Sol

考虑对于分成 $\sqrt{n}$ 块，每块 $\sqrt{n}$ 个数，初始化每块从小到大排序。

每次修改时对于整块整体加 $k$，相对大小不变；散块暴力修改，暴力排序。

每次查询时对于整块二分查找找到第一个大于 $k-lz$ 的数的位置，其中 $lz$ 表示整体加法标记；散块暴力查询。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=1e6+1e1,SqrtMAXN=1e3+1e1;
const lint INF=1e18+1e9;

int n,q;

struct Block{
	int a[MAXN],to[MAXN],sl[SqrtMAXN],sr[SqrtMAXN],lz[SqrtMAXN],sq,sn;

	int Read(){
		char c=getchar();
		while(c!='A' && c!='M') c=getchar();
		return (c=='A');
	}

	void Init(){
		memset(lz,0,sizeof(lz));
		sq=sqrt(n)+1,sn=n/sq+(n%sq ? 1 : 0);
		for(int i=1;i<=n;i++) to[i]=((i-1)/sq)+1;
		for(int i=1;i<=sn;i++) sl[i]=(i-1)*sq+1;
		for(int i=1;i<=sn;i++) sr[i]=min(i*sq,n);
		for(int i=1;i<=n;i++) a[i]=readint;
		for(int i=1;i<=sn;i++) sort(a+sl[i],a+sr[i]+1);
		return;
	}

	void Modify(int ql,int qr,int k){
		int tl=to[ql],tr=to[qr];
		if(tl==tr){
			for(int i=ql;i<=qr;i++) a[i]+=k;
			sort(a+ql,a+qr+1);
		}
		else{
			for(int i=ql;i<=sr[tl];i++) a[i]+=k;
			for(int i=sl[tr];i<=qr;i++) a[i]+=k;
			sort(a+sl[tl],a+sr[tl]+1),sort(a+sl[tr],a+sr[tr]+1);
			for(int i=tl+1;i<tr;i++) lz[i]+=k;
		}
		return;
	}

	int Query(int ql,int qr,int k){
		int tl=to[ql],tr=to[qr],res=0;
		if(tl==tr){
			for(int i=ql;i<=qr;i++) if(lz[to[i]]+a[i]>=k) ++res;
		}
		else{
			for(int i=ql;i<=sr[tl];i++) if(lz[to[i]]+a[i]>=k) ++res;
			for(int i=sl[tr];i<=qr;i++) if(lz[to[i]]+a[i]>=k) ++res;
			for(int i=tl+1;i<tr;i++){
				int pos=lower_bound(a+sl[i],a+sr[i]+1,k-lz[i])-a;
				res+=sr[i]-pos+1;
			}
		}
		return res;
	}
}st;

int main(void){

	scanf("%d%d",&n,&q),st.Init();
	while(q--){
		int op=st.Read();
		int l=readint,r=readint,k=readint;
		if(!op) st.Modify(l,r,k);
		else printf("%d\n",st.Query(l,r,k));
	}

	return 0;
}