1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

const int MAXN = 1100000,MAXQ = 50000;

void read(int &x){scanf("%d",&x);}
void read(char *x){scanf("%s",x);}

int n,m,a[MAXN],Q;
int add[MAXN];
int num[MAXN];

bool cmp(int a,int b){return a > b;}
void cpy(int q){memcpy(num+q*Q,a+q*Q,sizeof(int)*Q);}
void sort(int q){sort(num+q*Q,num+min(n,(q+1)*Q),cmp);}

int query(int q,int c){
  int t = upper_bound(num+q*Q,num+min(n,(q+1)*Q),c,cmp) - (num+q*Q);
  // printf("q:%d c:%d t:%d\n",q,c,t);
  return t;
}

void init(){
  read(n),read(m);Q = sqrt(n)+1;
  for(int i = 0;i<n;i++){
    read(a[i]);
    if(i/Q != (i+1)/Q || i == n-1)
      cpy(i/Q),sort(i/Q);
  }
}

void modify(int l,int r,int w){
  int lq = l/Q,rq = r/Q;
  if(lq == rq || lq + 1 == rq){
    for(int i = l;i<=r;i++)
      a[i] += w;
    cpy(lq),sort(lq);
    cpy(rq),sort(rq);
  }
  else{
    for(int i = lq+1;i<=rq-1;i++) add[i] += w;
    for(int i = l;i<(lq+1)*Q;i++) a[i] += w;
    for(int i = rq*Q;i<=r;i++)    a[i] += w;
    cpy(lq),sort(lq);
    cpy(rq),sort(rq);
  }
}

int query(int l,int r,int c){
  int lq = l/Q,rq = r/Q,ans = 0;
  if(lq == rq || lq + 1 == rq){
    for(int i = l;i<=r;i++)
      if(a[i] + add[i/Q] >= c) ans ++;
    return ans;
  }
  else{
    for(int i = lq+1;i<=rq-1;i++)
      ans += query(i,c-add[i]);
    for(int i = l;i<(lq+1)*Q;i++)
      if(a[i] + add[i/Q] >= c) ans ++;
    for(int i = rq*Q;i<=r;i++)
      if(a[i] + add[i/Q] >= c) ans ++;
    return ans; 
  }  
}


void solve(){
  char op[10];
  int l,r,c;
  for(int i = 1;i<=m;i++){
    read(op),read(l),read(r),read(c);
    if(op[0] == 'M')
      modify(l-1,r-1,c);
    if(op[0] == 'A')
      printf("%d\n",query(l-1,r-1,c));
  }
}

int main(){
  init();
  solve();
  return 0;
}