题解——loj6278 数列分块入门2 (分块)

时间:2021-11-25 17:07:10

查询小于k的值

注意lower_bound一定要减去查找的起始位置得到正确的位置

调了快两天

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int a[],b[],belong[],tag[],num,sz,n;
void calbe(int n){
for(int i=;i<=n;i++){
belong[i]=(i-)/sz+;
}
}
void reset(int l,int r){
for(int i=l;i<=r;i++)
b[i]=a[i];
sort(b+l,b+r+);
}
void update(int l,int r,int w){
int xl=belong[l];
int xr=belong[r];
for(int i=l;i<=min(r,sz*xl);i++){
a[i]+=w;
}
reset((xl-)*sz+,min(xl*sz,n));
if(xl!=xr){
for(int i=(xr-)*sz+;i<=r;i++)
a[i]+=w;
reset((xr-)*sz+,min(xr*sz,n));
}
for(int i=xl+;i<=xr-;i++)
tag[i]+=w; }
int query(int l,int r,int w){
// printf("qw=%d\n",w);
int xl=belong[l];
int xr=belong[r];
// printf("ln=%d || rn=%d\n",xl,xr);
int ans=;
for(int i=l;i<=min(r,sz*xl);i++){
// printf("tag=%d || qsw=%d\n",tag[xl],w-tag[xl]);
if(a[i]<w-tag[xl]){
ans++;
// printf("a[%d] = %d || w=%d ||tag=%d\n",i,a[i],w,tag[xl]);
}
}
if(xl!=xr){
for(int i=(xr-)*sz+;i<=r;i++){
// printf("tag=%d || qsw=%d\n",tag[xr],w-tag[xr]);
if(a[i]<w-tag[xr]){
ans++;
// printf("a[%d] = %d || w=%d ||tag=%d\n",i,a[i],w,tag[xl]);
}
}
}
for(int i=xl+;i<=xr-;i++){
int pos = lower_bound(b+sz*(i-)+,b+sz*i+,w-tag[i])-(b+(i-)*sz+);
// printf("pos/%d:%d st=%d \n",i,pos,(i-1)*sz+1);
ans+=pos;
}
return ans;
}
int main(){
scanf("%d",&n);
sz=sqrt(n);
calbe(n);
num=n/sz;
if(n%sz)
num++;
// printf("sz=%d\n",sz);
// for(int i=1;i<=n;i++)
// printf("%d ",belong[i]);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=num;i++){
reset((i-)*sz+,min(sz*i,n));
}
// for(int i=1;i<=num;i++){
// printf("block:%d\nB: ",i);
// for(int j=(i-1)*sz+1;j<=i*sz;j++)
// printf("%d ",b[j]+tag[i]);
// printf("\nA: ");
// for(int j=(i-1)*sz+1;j<=i*sz;j++)
// printf("%d ",a[j]+tag[i]);
// printf("\n\n");
// }
for(int i=;i<=n;i++){
int opt,l,r,c;
scanf("%d %d %d %d",&opt,&l,&r,&c);
if(opt==){
update(l,r,c);
// for(int i=1;i<=num;i++){
// printf("block:%d tag:%d\nB: ",i,tag[i]);
// for(int j=(i-1)*sz+1;j<=i*sz;j++)
// printf("%d ",b[j]+tag[i]);
// printf("\nA: ");
// for(int j=(i-1)*sz+1;j<=i*sz;j++)
// printf("%d ",a[j]+tag[i]);
// printf("\n\n");
// }
}
else{
printf("%d\n",query(l,r,c*c));
}
}
return ;
}