Lvat_s Blog

分块

每个块维护两个数组，一个是按位置排序，另一个按大小排序

修改暴力做两块，中间搞个tag

询问两块暴力，中间二分

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

int n,q,cnt;
const int block_size=1000,block_num=1000;

struct Block{
int block1[block_size+5],block2[block_size+5];
int n,tag;
}block[block_num+5];

void Add(int l,int r,int v){
int first_block=(l-1)/block_size+1,last_block=(r-1)/block_size+1,first_pos=(l-1)%block_size+1,last_pos=(r-1)%block_size+1;
if(first_block==last_block){
    for(int i=first_pos;i<=last_pos;i++)block[first_block].block1[i]+=v;
    for(int i=1;i<=block[first_block].n;i++)block[first_block].block2[i]=block[first_block].block1[i];
    sort(block[first_block].block2+1,block[first_block].block2+block[first_block].n+1);
	return;
}
for(int i=first_block+1;i<last_block;i++)block[i].tag+=v;
for(int i=first_pos;i<=block[first_block].n;i++)block[first_block].block1[i]+=v;
for(int i=1;i<=block[first_block].n;i++)block[first_block].block2[i]=block[first_block].block1[i];
sort(block[first_block].block2+1,block[first_block].block2+block[first_block].n+1);
for(int i=1;i<=last_pos;i++)block[last_block].block1[i]+=v;
for(int i=1;i<=block[last_block].n;i++)block[last_block].block2[i]=block[last_block].block1[i];
sort(block[last_block].block2+1,block[last_block].block2+block[last_block].n+1);
}

int Div(int id,int k){
int l=1,r=block[id].n,ans=0;
while(l<=r){
	int mid=l+r>>1;
	if(block[id].block2[mid]+block[id].tag<k){l=mid+1;ans=mid;}
	else {r=mid-1;}
}
return block[id].n-ans;
}

int Query(int l,int r,int k){
int first_block=(l-1)/block_size+1,last_block=(r-1)/block_size+1,first_pos=(l-1)%block_size+1,last_pos=(r-1)%block_size+1,ans=0;
if(first_block==last_block){
    for(int i=first_pos;i<=last_pos;i++)ans+=(k<=(block[first_block].block1[i]+block[first_block].tag));
	return ans;
}
for(int i=first_block+1;i<last_block;i++)ans+=Div(i,k);
for(int i=first_pos;i<=block[first_block].n;i++)ans+=(k<=(block[first_block].block1[i]+block[first_block].tag));
for(int i=1;i<=last_pos;i++)ans+=(k<=(block[last_block].block1[i]+block[last_block].tag));
return ans;
}

int main(){
freopen("3343.in","r",stdin);
freopen("3343.out","w",stdout);
scanf("%d %d",&n,&q);
cnt=(n-1)/block_size+1;
for(int i=1;i<cnt;i++)block[i].n=block_size;
block[cnt].n=(n-1)%block_size+1;
for(int i=1;i<=n;i++){
	int pos_block=(i-1)/block_size+1,pos=(i-1)%block_size+1;
	scanf("%d",&block[pos_block].block1[pos]);
}
for(int i=1;i<=cnt;i++){
	for(int j=1;j<=block[i].n;j++)block[i].block2[j]=block[i].block1[j];
	sort(block[i].block2+1,block[i].block2+block[i].n+1);
}
for(int i=1;i<=q;i++){
	int l,r,v;
	char s[5];
    scanf("%s %d %d %d",s,&l,&r,&v);
    if(s[0]=='M')Add(l,r,v);
    if(s[0]=='A')printf("%d\n",Query(l,r,v));
}
return 0;
}