分块需注意的问题
- 数组大小应为,因为最后一个块可能会超出的范围。
- 当操作的区间在一个块内时,要特判成暴力修改。
- 要清楚什么时候应该
+tag[t]
数列分块入门 1
给出一个长为的数列,以及个操作,操作涉及区间加法,单点查值。
//数列分块入门 1
#include <cstdio>
#include <cmath>
inline char gc()
{
static char now[1<<16],*S,*T;
if(S==T) {T=(S=now)+fread(now,1,1<<16,stdin); if(S==T) return EOF;}
return *S++;
}
inline int read()
{
int x=0,f=1; char ch=gc();
while(ch<'0'||'9'<ch) {if(ch=='-') f=-1; ch=gc();}
while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();
return x*f;
}
int const N=5e4+10;
int n,n0;
int a[N],tag[N];
int main()
{
n=read(); n0=sqrt(n);
for(int i=1;i<=n;i++) a[i]=read();
for(int owo=1;owo<=n;owo++)
{
int opt=read(),L=read(),R=read(),c=read();
if(opt==0)
{
int L0=L/n0,R0=R/n0;
if(L0==R0) {for(int i=L;i<=R;i++) a[i]+=c; continue;}
for(int i=L;i<=(L0+1)*n0-1;i++) a[i]+=c;
for(int i=L0+1;i<=R0-1;i++) tag[i]+=c;
for(int i=R0*n0;i<=R;i++) a[i]+=c;
}
else printf("%d\n",a[R]+tag[R/n0]);
}
return 0;
}
数列分块入门 2
给出一个长为的数列,以及个操作,操作涉及区间加法,询问区间内小于某个值的元素个数。
//数列分块入门 2
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
inline char gc()
{
static char now[1<<16],*S,*T;
if(S==T) {T=(S=now)+fread(now,1,1<<16,stdin); if(S==T) return EOF;}
return *S++;
}
inline int read()
{
int x=0,f=1; char ch=gc();
while(ch<'0'||'9'<ch) {if(ch=='-') f=-1; ch=gc();}
while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();
return x*f;
}
int const N=5e4+1000;
int const INF=0x7FFFFFFF;
int n,n0;
int a[N],b[N],tag[N];
void update(int t)
{
int fr=t*n0,to=fr+n0-1;
for(int i=fr;i<=to;i++) b[i]=a[i];
sort(b+t*n0,b+(t+1)*n0);
}
int query(int t,int x)
{
return lower_bound(b+t*n0,b+(t+1)*n0,x)-(b+t*n0);
}
int main()
{
n=read(); n0=sqrt(n);
for(int i=1;i<=n;i++) a[i]=b[i]=read();
b[0]=INF; for(int i=n+1;i<=(n/n0+1)*n0;i++) b[i]=INF;
for(int t=0;t<=n/n0;t++) sort(b+t*n0,b+(t+1)*n0);
for(int owo=1;owo<=n;owo++)
{
int opt=read(),L=read(),R=read(),c=read();
int L0=L/n0,R0=R/n0;
if(opt==0)
{
if(L0==R0) for(int i=L;i<=R;i++) a[i]+=c;
else
{
for(int i=L;i<=(L0+1)*n0-1;i++) a[i]+=c;
for(int t=L0+1;t<=R0-1;t++) tag[t]+=c;
for(int i=R0*n0;i<=R;i++) a[i]+=c;
}
update(L0),update(R0);
}
else
{
int res=0;
if(L0==R0) for(int i=L;i<=R;i++) res+=(a[i]+tag[L0]<c*c);
else
{
for(int i=L;i<=(L0+1)*n0-1;i++) res+=(a[i]+tag[L0]<c*c);
for(int t=L0+1;t<=R0-1;t++) res+=query(t,c*c-tag[t]);
for(int i=R0*n0;i<=R;i++) res+=(a[i]+tag[R0]<c*c);
}
printf("%d\n",res);
}
}
return 0;
}
数列分块入门 3
给出一个长为的数列,以及个操作,操作涉及区间加法,询问区间内小于某个值的前驱(比其小的最大元素)。
//数列分块入门 3
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
inline char gc()
{
static char now[1<<16],*S,*T;
if(S==T) {T=(S=now)+fread(now,1,1<<16,stdin); if(S==T) return EOF;}
return *S++;
}
inline int read()
{
int x=0,f=1; char ch=gc();
while(ch<'0'||'9'<ch) {if(ch=='-') f=-1; ch=gc();}
while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();
return x*f;
}
int const N=1e5+1000;
int const INF=0x7FFFFFFF;
int n,n0;
int a[N],b[N],tag[N];
void update(int t)
{
int fr=t*n0,to=fr+n0;
for(int i=fr;i<to;i++) b[i]=a[i];
sort(b+fr,b+to);
}
int res;
void check(int x,int x0) {if(x<x0) res=max(res,x);}
int pre(int t,int v)
{
int x=lower_bound(b+t*n0,b+t*n0+n0,v)-b;
return x==t*n0?-INF:b[x-1]+tag[t];
}
int main()
{
n=read(); n0=sqrt(n);
for(int i=1;i<=n;i++) a[i]=b[i]=read();
b[0]=INF; for(int i=n+1;i<=n/n0*n0;i++) b[i]=INF;
for(int t=0;t<=n/n0;t++) sort(b+t*n0,b+t*n0+n0);
for(int owo=1;owo<=n;owo++)
{
int opt=read(),L=read(),R=read(),c=read();
int L0=L/n0,R0=R/n0;
if(opt==0)
{
if(L0==R0) for(int i=L;i<=R;i++) a[i]+=c;
else
{
for(int i=L;i<=(L0+1)*n0-1;i++) a[i]+=c;
for(int t=L0+1;t<=R0-1;t++) tag[t]+=c;
for(int i=R0*n0;i<=R;i++) a[i]+=c;
}
update(L0),update(R0);
}
else
{
res=-INF;
if(L0==R0)
for(int i=L;i<=R;i++) check(a[i]+tag[L0],c);
else
{
for(int i=L;i<=(L0+1)*n0-1;i++) check(a[i]+tag[L0],c);
for(int t=L0+1;t<=R0-1;t++) res=max(res,pre(t,c-tag[t]));
for(int i=R0*n0;i<=R;i++) check(a[i]+tag[R0],c);
}
printf("%d\n",res>-INF?res:-1);
}
}
return 0;
}