Calanosay @ 2021-07-21 15:37:49
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int maxn = 1e6+5;
const int maxq = 1e3+5;
int st[maxn],ed[maxn],be[maxn],sizee[maxn],tag[maxn];
int a[maxn];
vector<int> g[maxq];
int n,m,sq;
void updateg(int x){
for (int i = 0; i < sizee[i] ; ++i) {
g[x].push_back(a[st[x]+i]);
}
sort(g[x].begin(),g[x].end());
}
void init(){
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 <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= sq; ++i) {
for (int j = st[i]; j <= ed[i]; ++j) {
g[i].push_back(a[j]);
}
}
for (int i = 1; i <= sq; ++i) {
sort(g[i].begin(),g[i].end());
}
for (int i = 1; i <= sq; ++i) {
for (int j = be[i]; j <= ed[i]; ++j) {
be[j] = i;
}
}
for (int i = 1; i <= sq; ++i) {
sizee[i] = ed[i] - st[i] + 1;
}
}
void update(int x,int y,int k){
if(be[x]==be[y]){
for (int i = x; i <= y; ++i) {
a[i] += k;
}
updateg(be[x]);
}
else{
for (int i = x; i <= ed[be[x]]; ++i) {
a[i] += k;
}
updateg(be[x]);
for (int i = st[be[y]]; i <= y; ++i) {
a[i] += k;
}
updateg(be[y]);
for (int i = be[x]+1; i < be[y]; ++i) {
tag[i] += k;
}
}
}
int query(int x,int y,int k){
int ans = 0;
if(be[x]==be[y]){
for (int i = x; i <= y; ++i) {
if(a[i]+tag[be[x]]>=k) ans++;
}
return ans;
}
else{
for (int i = x; i <= ed[be[x]]; ++i) {
if(a[i]+tag[be[x]]>=k) ans++;
}
for (int i = st[be[y]]; i <= y; ++i) {
if(a[i]+tag[be[y]]>=k) ans++;
}
for (int i = be[x]+1; i < be[y]; ++i) {
ans += g[i].end()-lower_bound(g[i].begin(),g[i].end(),k-tag[i]);
}
return ans;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
init();
while (m--){
char c;
int l,r,x;
cin>>c>>l>>r>>x;
if(c=='A'){
cout<<query(l,r,x)<<endl;
}
else{
update(l,r,x);
}
}
}
by _z_z_h @ 2021-07-21 16:48:03
写快读