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; }
|
近期评论