rt

解释一下几个数组：$st_i$ 是第 i 个块的起点，$ed_i$ 则是终点，$a_i$ 是原数组，$id_i$ 是第 i 个数所在块的编号，$delta_i$ 是第 i 个块的延迟标记，$t_i$ 是用来排序的数组。

预言一波感觉又是犯了很nt的错误

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int N=1e6+5;
int n,q,num;
int st[N],ed[N],a[N],id[N],delta[N],t[N],size[N];
inline void write(int x);
inline int read();
void init();
void add(int l,int r,int c);
int query(int l,int r,int c);
int main(){
	n=read(),q=read();
	getchar();
	for(int i=1;i<=n;i++) a[i]=read();
	getchar();
	while(q--){
		char ch=getchar();
		int L=read(),R=read(),X=read(); 
		if(ch=='M'){
			add(L,R,X);
		}else if(ch=='A'){
			int ans=query(L,R,X);
			write(ans); 
			printf("\n");
		}
		if(q) getchar();
	}
	return 0;
}
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
inline void write(int x){if(x<0)x=~x+1,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');}
void init(){
	num=sqrt(n); 
	for(int i=1;i<=num;i++) st[i]=n/num*(i-1)+1,ed[i]=n/num*i;
	ed[num]=n;
	for(int i=1;i<=num;i++){
		for(int j=st[i];j<=ed[i];j++) id[j]=i;
		size[i]=ed[i]-st[i]+1;
	} 
}
void Sort(int x){
	for(int i=st[x];i<=ed[x];i++) t[i]=a[i];
	sort(t+st[x],t+ed[x]+1);
}
void add(int l,int r,int c){
	int sid=id[l],eid=id[r];
	if(sid==eid){
		for(int i=l;i<=r;i++) a[i]+=c;
		Sort(sid);
		return ;
	}
	for(int i=l;i<=ed[sid];i++) a[i]+=c;
	for(int i=sid+1;i<eid;i++) delta[i]+=c;
	for(int i=st[eid];i<=r;i++) a[i]+=c;
	Sort(sid);
	Sort(eid);
	return ;
}
int query(int l,int r,int c){
	int sid=id[l],eid=id[r],ans=0;
	if(sid==eid){
		for(int i=l;i<=r;i++) ans+=(a[i]+delta[sid]>=c?1:0);
		return ans;
	}
	for(int i=l;i<=ed[sid];i++) ans+=(a[i]+delta[sid]>=c?1:0);
	for(int i=sid+1;i<eid;i++) ans+=(ed[i]-(lower_bound(t+st[i],t+ed[i]+1,c-delta[i])-t)+1);
	for(int i=st[eid];i<=r;i++) ans+=(a[i]+delta[eid]>=c?1:0);
	return ans;
}