出言不逊王子 @ 2021-05-05 09:39:15
#include<bits/stdc++.h>
#define HCL_AK_IOI 114514
#define fs(i,x,y,z) for(register int i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(register int i=x;i>=y;i+=z)
#define int long long
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int N=1000003,inf=0x3f3f3f3f;
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
int o,n,org[N],k,trs[N],add[N],q,s,l[N],r[N],bl[N];
inline void upd(int lll,int rrr,int w){
fs(i,(l[bl[lll]]==lll?bl[lll]:bl[lll]+1),(r[bl[rrr]]==rrr?bl[rrr]:bl[rrr]-1),1) add[i]+=w;//是不是整块,如果是的话只要加整的
/*o--- xxxx xxxx -ooo
那么我们只能对x所在的块进行修改*/
if(l[bl[lll]]!=lll){//左边的在org单独修改
int b=bl[lll];
fs(i,lll,r[b],1) org[i]+=w,trs[i]=org[i];
sort(trs+l[b]+1,trs+r[b]+1);
}
if(r[bl[rrr]]!=rrr){
int b=bl[rrr];
fs(i,l[b],rrr,1) org[i]+=w,trs[i]=org[i];
sort(trs+l[b]+1,trs+r[b]+1);
}
}
inline int query(int lll,int rrr,int c){
int ans=0;
if(l[bl[lll]]!=lll){//左边的在org单独查询
int b=bl[lll];
fs(i,lll,r[b],1) if(org[i]>=c) ans++;
}
//printf("!1!%d\n",ans);
if(r[bl[rrr]]!=rrr){
int b=bl[rrr];
fs(i,l[b],rrr,1) if(org[i]>=c) ans++;
}
//printf("!2!%d\n",ans);
fs(i,(l[bl[lll]]==lll?bl[lll]:bl[lll]+1),(r[bl[rrr]]==rrr?bl[rrr]:bl[rrr]-1),1){
int pp=lower_bound(trs+l[i],trs+r[i]+1,c-add[i])-trs;
if(pp>r[i]) continue;//一个没有啊
ans+=r[i]-pp+1;
//printf("!!%d!!%d %d\n",i,ans,pp);
}
printf("%lld\n",ans);
}
signed main(){
n=read(),q=read();
k=sqrt(n);
o=n-k*k;
fs(i,1,n,1) trs[i]=org[i]=read();
s=n/k;
if(o) s++;
fs(i,1,k,1) sort(trs+(i-1)*k+1,trs+i*k+1);
fs(i,1,s,1) l[i]=(i-1)*k+1,r[i]=i*k;
// printf("sample thing:\nk=%d\ns=%d\neach l&r:\n",k,s);
// fs(i,1,s,1) printf("%d %d\n",l[i],r[i]);
r[s]=n;
fs(i,1,n,1) bl[i]=(i-1)/k+1;//,printf("%d ",bl[i]);
while(q--){
char op='\0';
/*do{*/op=getchar();/*}while(op!='A'||op!='M');*/
int a=read(),b=read(),c=read();
if(op=='A') query(a,b,c);
else upd(a,b,c);
}
return 0;
}
by 出言不逊王子 @ 2021-05-05 09:39:48
校内OJ原题是WA,70分