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
88
89
90
91
92
93
94
|
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1050;
int n,m,num,c[N][N],id[N][N],w[N],st[N],ed[N];
inline int ()
{
register int x=0,t=1;
register char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') {t=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
return x*t;
}
inline char get()
{
register char ch=getchar();
while (!(('a'<=ch&&ch<='z')||('A'<=ch&&ch<='Z'))) ch=getchar();
return ch;
}
void qsort(int k,int l,int r)
{
int i=l,j=r,mid=c[k][id[k][(l+r)>>1]];
do
{
while (c[k][id[k][i]]<mid) i++;
while (c[k][id[k][j]]>mid) j--;
if (i<=j) swap(id[k][i],id[k][j]),i++,j--;
}
while (i<=j);
if (i<r) qsort(k,i,r);
if (l<j) qsort(k,l,j);
}
int find(int k,int x)
{
int L=1,R=ed[k]-st[k]+1;
while (L<R)
{
int mid=(L+R)>>1;
if (c[k][id[k][mid]]+w[k]<x)
L=mid+1;
else
R=mid;
}
return (L+R)>>1;
}
int main()
{
n=read(),m=read();
num=sqrt(n)+1;
for(int i=0;i<=num;i++) st[i]=n;
for(int i=1,cnt=0;i<=n;i++)
{
st[i/num]=min(st[i/num],i);
ed[i/num]=max(ed[i/num],i);
}
for(int i=1;i<=n;i++)
{
c[i/num][i-st[i/num]+1]=read();
id[i/num][i-st[i/num]+1]=i-st[i/num]+1;
}
for(int i=1;i<=num;i++) qsort(i,1,ed[i]-st[i]+1);
for(int i=1;i<=m;i++)
{
char opt=get();
int ql=read(),qr=read(),x=read();
if (opt=='M')
{
for(int i=ql;i<=min(qr,ed[ql/num]);i++) c[i/num][i-st[i/num]+1]+=x;
for(int i=ql/num+1;i<qr/num;i++) w[i]+=x;
if (ql/num!=qr/num)
for(int i=st[qr/num];i<=qr;i++) c[i/num][i-st[i/num]+1]+=x;
qsort(ql/num,1,ed[ql/num]-st[ql/num]+1);
if (ql/num!=qr/num) qsort(qr/num,1,ed[qr/num]-st[qr/num]+1);
}
else
{
int ans=0;
for(int i=ql;i<=min(qr,ed[ql/num]);i++)
if (c[i/num][i-st[i/num]+1]+w[i/num]>=x) ans++;
for(int i=ql/num+1;i<qr/num;i++)
{
if (c[i][id[i][ed[i]-st[i]+1]]+w[i]<x) continue;
ans+=(ed[i]-st[i]+1)-find(i,x)+1;
}
if (ql/num!=qr/num)
for(int i=st[qr/num];i<=qr;i++)
if (c[i/num][i-st[i/num]+1]+w[i/num]>=x) ans++;
printf("%dn",ans);
}
}
return 0;
}
|
近期评论