_TLEer_的小号 @ 2021-03-06 09:35:51
Rt. Code:
#include<iostream>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
int n,m,k,a[1000010],l,r,pos[1000010],cg[1000010],b[1000010];
char size;
int BLOCKSIZE;
struct BLOCK_T{
int le,rt,tag;
int binary_cut(int k){
return BLOCKSIZE-(lower_bound(b+le,b+rt+1,k-tag)-(b+le));
}
}block[10010];
int at_block_return(int now){
return pos[now];
}
bool at_the_same_block(int x,int y){
return at_block_return(x)==at_block_return(y);
}
void cgblock(int l,int r){
for(int i=l;i<=r;i++)b[i]=a[i];
sort(b+l,b+r+1);
}
void addblock(){
BLOCKSIZE=sqrt(n);
int blocktot=0;
for(int i=0;i<n;i++){
pos[i]=blocktot;
b[i]=a[i];
if(i>=(blocktot+1)*BLOCKSIZE-1){
block[blocktot].le=blocktot*BLOCKSIZE;
block[blocktot].rt=min(block[blocktot].le+BLOCKSIZE-1,n-1);
// system("pause");
blocktot++;
cgblock(block[blocktot].le,block[blocktot].rt);
}
}
block[blocktot].le=blocktot*BLOCKSIZE;
block[blocktot].rt=min(block[blocktot].le+BLOCKSIZE-1,n-1);
cgblock(block[blocktot].le,block[blocktot].rt);
// cout<<blocktot<<' '<<block[blocktot].le<<' '<<block[blocktot].rt<<endl;
}
void add(int le,int rt,int k){
if(at_the_same_block(le,rt)){
for(int i=le;i<=rt;i++)
a[i]+=k;
cgblock(block[at_block_return(rt)].le,block[at_block_return(rt)].rt);
return;
}
int lblock=at_block_return(le),rblock=at_block_return(rt);
add(le,block[lblock].rt,k);
add(block[rblock].le,rt,k);
lblock++;rblock--;
for(int i=lblock;i<=rblock;i++)
block[i].tag+=k;
}
int ask(int le,int rt,int k){
int ans=0;
// cout<<le<<' '<<rt<<' '<<at_the_same_block(le,rt)<<endl;
if(at_the_same_block(le,rt)){
for(int i=le;i<=rt;i++)
if(a[i]+block[at_block_return(rt)].tag>=k)
ans++;
return ans;
}
int lblock=at_block_return(le),rblock=at_block_return(rt);
ans+=ask(le,block[lblock].rt,k)+ask(block[rblock].le,rt,k);
lblock++;rblock--;
for(int i=lblock;i<=rblock;i++)
ans+=block[i].binary_cut(k);
return ans;
}
signed main(){
cin>>n>>m;
for(int i=0;i<n;i++)cin>>a[i];
addblock();
for(int i=0;i<m;i++){
cin>>size>>l>>r>>k;
l--,r--;
if(size=='M'){
add(l,r,k);
}
else{
cout<<ask(l,r,k)<<endl;
}
}
return 0;
}