分析
大力分块。
对于修改，边块直接暴力，整块打标记。
对于查询，边块暴力查询，整块可以块内排序+块内二分。
但是每次查询都sort一遍极慢，可以先将每块排序后的数组存下来，当有一部分被修改时再重排一次。这样子就快了很多。
然后，块大小取$\sqrt{\frac{n+2}{3}}$，飞快。
代码
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int MAXN=1000000+10;
int h[MAXN],g[MAXN];
int add[MAXN],belong[MAXN],L[MAXN],R[MAXN];
inline void copy(int x) {
x=belong[x];
for (re int i=L[x];i<=R[x];++i) g[i]=h[i];
stable_sort(g+L[x],g+R[x]+1);
}
inline int find(int x,int v) { //在第x块中查询大于等于v的数量
int left=L[x],right=R[x];
while (left<=right) {
int mid=(left+right)>>1;
if (g[mid]<v) left=mid+1;
else right=mid-1;
}
return R[x]-left+1;
}
int main() {
int n=read(),q=read(),block=sqrt((n+2)/3.0);
for (re int i=1;i<=n;++i) {
h[i]=g[i]=read();
belong[i]=(i-1)/block+1;
}
int cnt=0;
for (re int i=1;i<=n;++i)
if (belong[i]!=belong[i-1]) R[cnt]=i-1,L[++cnt]=i;
R[cnt]=n;
for (re int i=1;i<=cnt;++i) stable_sort(g+L[i],g+R[i]+1);
while (q--) {
char op[2]; scanf("%s",op);
int l=read(),r=read(),x=read();
if (op[0]=='M') { //修改
if (belong[l]==belong[r]) {
for (re int i=l;i<=r;++i) h[i]+=x; copy(l);
} else {
for (re int i=l;i<=R[belong[l]];++i) h[i]+=x; copy(l);
for (re int i=L[belong[r]];i<=r;++i) h[i]+=x; copy(r);
for (re int i=belong[l]+1;i<belong[r];++i) add[i]+=x;
}
} else { //查询
int cnt=0;
if (belong[l]==belong[r]) {
for (re int i=l;i<=r;++i)
if (h[i]+add[belong[i]]>=x) ++cnt;
} else {
for (re int i=l;i<=R[belong[l]];++i)
if (h[i]+add[belong[i]]>=x) ++cnt;
for (re int i=L[belong[r]];i<=r;++i)
if (h[i]+add[belong[i]]>=x) ++cnt;
for (re int i=belong[l]+1;i<belong[r];++i) {
cnt+=find(i,x-add[i]);
}
}
printf("%d\n",cnt);
}
}
return 0;
}
stO
蒟蒻求问：为什么块的大小是这个数呢？
这个是试出来实际上跑得比较快的，而不是理论上跑得比较快的
大概是数据问题，理论上这个不是最优的