思路：虽然n很大，但是查询次数Q有限，只有3000,左右，因此我们可以用分块算法解决该题，通过vector将每一块变成一个有序的块，在每次更新操作，直接暴力更新即可。
#include<set> #include<queue> #include<vector> #include<string> #include<math.h> #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; #define maxn 1000050 #define SQ 1005 #define ll long long int mark[SQ],size[SQ]; int n,m,a[maxn],sq; int st[SQ],ed[SQ],bel[maxn]; vector<int> arr[SQ]; int read() { int ans = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)) { ans = ans * 10 + c - '0'; c = getchar(); } return ans; } void init(int n){ sq=sqrt(n); for(int i=1;i<=sq;i++){ st[i]=n/sq*(i-1)+1; ed[i]=n/sq*i; } ed[sq]=n; for(int i=1;i<=sq;i++){ for(int j=st[i];j<=ed[i];j++) bel[j]=i; size[i]=ed[i]-st[i]+1; } } void update(int index){ for(int i=0;i<size[index];i++) arr[index][i]=a[st[index]+i]; sort(arr[index].begin(),arr[index].end()); } int main(void){ int x,y,z; n=read(); m=read(); init(n); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=sq;i++) for(int j=st[i];j<=ed[i];j++) arr[i].push_back(a[j]); for(int i=1;i<=sq;i++) sort(arr[i].begin(),arr[i].end()); while(m--){ char c; scanf(" %c",&c); x=read(); y=read(); z=read(); if(c=='M'){ if(bel[x]==bel[y]){ for(int i=x;i<=y;i++) a[i]+=z; update(bel[x]); continue; } for(int i=x;i<=ed[bel[x]];i++) a[i]+=z; for(int i=st[bel[y]];i<=y;i++) a[i]+=z; update(bel[x]); update(bel[y]); for(int i=bel[x]+1;i<bel[y];i++) mark[i]+=z; } else{ int tot=0; if(bel[x]==bel[y]){ for(int i=x;i<=y;i++){ if(a[i]+mark[bel[x]]>=z) tot++; } printf("%d\n",tot); continue; } for(int i=x;i<=ed[bel[x]];i++) if(a[i]+mark[bel[x]]>=z) tot++; for(int i=st[bel[y]];i<=y;i++) if(a[i]+mark[bel[y]]>=z) tot++; for(int i=bel[x]+1;i<bel[y];i++) tot+=arr[i].end()-lower_bound(arr[i].begin(),arr[i].end(),z-mark[i]); printf("%d\n",tot); } } return 0; }
