数列分块入门（套题）（loj6277,loj6278,loj6279,loj6280,loj6281,loj6282,loj6283,loj6284,loj6285）_loj79-程序员宅基地

技术标签： OI 分块

前言

zjoi考差了，码一些分块题缓解一下心情

壹

数列分块入门 1[loj6277]
题目大意：区间加，单点查
直接分块，区间加时完全覆盖的块打tag，边界块暴力重构
块大小设为 $\sqrt n$ ，复杂度 $\mathcal O(n\sqrt n)$
code

#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#define rg register
namespace fast_IO
{
    
	const int IN_LEN=1000000,OUT_LEN=1000000;
	char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;
	inline char getchar_(){
    return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}
	inline void putchar_(const char x){
    if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}
	inline void flush(){
    fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){
    char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){
    if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){
    if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){
    if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=50001,sq=1001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],tag[sq];
void clean(const int P)
{
    
	for(rg int i=L[P];i<=R[P];i++)a[i]+=tag[P];
	tag[P]=0;
}
int main()
{
    
	read(n),part=sqrt(n);
	for(rg int i=1;i<=n;i++)
	{
    
		read(a[i]);
		const int P=i/part;
		belo[i]=P;
		if(!L[P])L[P]=i;
		R[P]=i;
	}
	for(rg int q=1;q<=n;q++)
	{
    
		int opt,l,r,c;read(opt),read(l),read(r),read(c);
		if(opt==0)
		{
    
			if(belo[l]==belo[r])
			{
    
				clean(belo[l]);
				for(rg int i=l;i<=r;i++)a[i]+=c;
			}
			else
			{
    
				for(rg int i=belo[l]+1;i<belo[r];i++)tag[i]+=c;
				clean(belo[l]),clean(belo[r]);
				for(rg int i=l;i<=R[belo[l]];i++)a[i]+=c;
				for(rg int i=r;i>=L[belo[r]];i--)a[i]+=c;
			}
		}
		else print(a[r]+tag[belo[r]]),putchar('\n');
	}
	return flush(),0;
}

贰

数列分块入门 2[loj6278]
题目大意：区间加，区间查询小于某个数的个数
直接分块，区间加时完全覆盖的块打tag，边界块暴力重构
额外维护块内有序数组/平衡树，查询用lower_bound即可
块大小设为 $\sqrt n$ ，复杂度 $\mathcal O(n\sqrt{n}logn)$
注意别忘了tag的影响
~~事实证明，写分块要注重常数，随便多点常数就会T~~
code

#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#define rg register
namespace fast_IO
{
    
	const int IN_LEN=1000000,OUT_LEN=1000000;
	char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;
	inline char getchar_(){
    return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}
	inline void putchar_(const char x){
    if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}
	inline void flush(){
    fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){
    char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){
    if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){
    if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){
    if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=50001,sq=1001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],tag[sq],size[sq];
int v[sq][sq];
void clean(const int P)
{
    
	for(rg int i=L[P];i<=R[P];i++)a[i]+=tag[P];
	tag[P]=0;
}
void rebuild(const int P)
{
    
	int top=0;
	for(rg int i=L[P];i<=R[P];i++)v[P][++top]=a[i];
	std::sort(v[P]+1,v[P]+top+1);
}
int main()
{
    
	read(n),part=sqrt(n);
	for(rg int i=1;i<=n;i++)
	{
    
		read(a[i]);
		const int P=i/part;
		belo[i]=P;
		if(!L[P])L[P]=i;
		R[P]=i;
	}
	for(rg int i=0;i<=belo[n];i++)size[i]=R[i]-L[i]+1,rebuild(i);
	for(rg int q=1;q<=n;q++)
	{
    
		int opt,l,r,c;read(opt),read(l),read(r),read(c);
		if(opt==0)
		{
    
			if(belo[l]==belo[r])
			{
    
				clean(belo[l]);
				for(rg int i=l;i<=r;i++)a[i]+=c;
				rebuild(belo[l]); 
			}
			else
			{
    
				for(rg int i=belo[l]+1;i<belo[r];i++)tag[i]+=c;
				clean(belo[l]),clean(belo[r]);
				for(rg int i=l;i<=R[belo[l]];i++)a[i]+=c;
				for(rg int i=r;i>=L[belo[r]];i--)a[i]+=c;
				rebuild(belo[l]),rebuild(belo[r]);
			}
		}
		else
		{
    
			c*=c;
			int ans=0;
			if(belo[l]==belo[r])
			{
    
				for(rg int i=l;i<=r;i++)ans+=(a[i]+tag[belo[l]])<c;
			}
			else
			{
    
				for(rg int i=belo[l]+1;i<belo[r];i++)ans+=std::lower_bound(v[i]+1,v[i]+size[i]+1,c-tag[i])-v[i]-1;
				for(rg int i=l;i<=R[belo[l]];i++)ans+=(a[i]+tag[belo[l]])<c;
				for(rg int i=r;i>=L[belo[r]];i--)ans+=(a[i]+tag[belo[r]])<c;
			}
			print(ans),putchar('\n');
		}
	}
	return flush(),0;
}

叁

数列分块入门 3[loj6279]
题目大意：区间加，区间查询小于某个数的最大数
与贰相似，只是这题取max而不是计数
块大小设为 $\sqrt n$ ，复杂度 $\mathcal O(n\sqrt{nlogn})$
~~这个垃圾数据范围比前两题多一倍，要复制的话记得改数组大小~~
注意一下lower_bound出来可能元素只有0个，此时应特判，否则加上tag的值可能会出错
code

#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#define rg register
namespace fast_IO
{
    
	const int IN_LEN=1000000,OUT_LEN=1000000;
	char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;
	inline char getchar_(){
    return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}
	inline void putchar_(const char x){
    if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}
	inline void flush(){
    fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){
    char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){
    if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){
    if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){
    if(x<0)putchar('-'),printe(-x);else printe(x);}
template <typename T> inline void maxd(T&a,const T b){
    a=a>b?a:b;}
const int maxn=100001,sq=1001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],tag[sq],size[sq];
int v[sq][sq];
void clean(const int P)
{
    
	for(rg int i=L[P];i<=R[P];i++)a[i]+=tag[P];
	tag[P]=0;
}
void rebuild(const int P)
{
    
	int top=0;
	for(rg int i=L[P];i<=R[P];i++)v[P][++top]=a[i];
	std::sort(v[P]+1,v[P]+top+1);
}
int main()
{
    
	read(n),part=sqrt(n);
	for(rg int i=1;i<=n;i++)
	{
    
		read(a[i]);
		const int P=i/part;
		belo[i]=P;
		if(!L[P])L[P]=i;
		R[P]=i;
	}
	for(rg int i=0;i<=belo[n];i++)size[i]=R[i]-L[i]+1,rebuild(i),v[i][0]=-1;
	for(rg int q=1;q<=n;q++)
	{
    
		int opt,l,r,c;read(opt),read(l),read(r),read(c);
		if(opt==0)
		{
    
			if(belo[l]==belo[r])
			{
    
				clean(belo[l]);
				for(rg int i=l;i<=r;i++)a[i]+=c;
				rebuild(belo[l]); 
			}
			else 
			{
    
				for(rg int i=belo[l]+1;i<belo[r];i++)tag[i]+=c;
				clean(belo[l]),clean(belo[r]);
				for(rg int i=l;i<=R[belo[l]];i++)a[i]+=c;
				for(rg int i=r;i>=L[belo[r]];i--)a[i]+=c;
				rebuild(belo[l]),rebuild(belo[r]);
			}
		}
		else
		{
    
			int ans=-1;
			if(belo[l]==belo[r])
			{
    
				for(rg int i=l;i<=r;i++)if((a[i]+tag[belo[l]])<c)maxd(ans,a[i]+tag[belo[l]]);
			}
			else
			{
    
				for(rg int i=belo[l]+1;i<belo[r];i++)
				{
    
					const int val=v[i][std::lower_bound(v[i]+1,v[i]+size[i]+1,c-tag[i])-v[i]-1];
					if(val!=-1)maxd(ans,val+tag[i]);
				}
				for(rg int i=l;i<=R[belo[l]];i++)if((a[i]+tag[belo[l]])<c)maxd(ans,a[i]+tag[belo[l]]);
				for(rg int i=r;i>=L[belo[r]];i--)if((a[i]+tag[belo[r]])<c)maxd(ans,a[i]+tag[belo[r]]);
			}
			print(ans),putchar('\n');
		}
	}
	return flush(),0;
}

肆

数列分块入门 4[loj6280]
题目大意：区间加，区间求和
同壹，多记录一下块内和即可
块大小设为 $\sqrt n$ ，复杂度 $\mathcal O(n\sqrt n)$
~~由于蜜汁数据范围，所以一些变量要开long long~~
code

#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#define rg register
namespace fast_IO
{
    
	const int IN_LEN=1000000,OUT_LEN=1000000;
	char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;
	inline char getchar_(){
    return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}
	inline void putchar_(const char x){
    if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}
	inline void flush(){
    fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){
    char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){
    if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){
    if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){
    if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=50001,sq=1001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],tag[sq],size[sq];ll ans[sq];
void clean(const int P)
{
    
	for(rg int i=L[P];i<=R[P];i++)a[i]+=tag[P];
	tag[P]=0;
}
int main()
{
    
	read(n),part=sqrt(n);
	for(rg int i=1;i<=n;i++)
	{
    
		read(a[i]);
		const int P=i/part;
		belo[i]=P;
		if(!L[P])L[P]=i;
		R[P]=i;
	}
	for(rg int i=1;i<=n;i++)
	{
    
		size[belo[i]]++;
		ans[belo[i]]+=a[i];
	}
	for(rg int q=1;q<=n;q++)
	{
    
		int opt,l,r,c;read(opt),read(l),read(r),read(c);
		if(opt==0)
		{
    
			if(belo[l]==belo[r])
			{
    
				clean(belo[l]);
				for(rg int i=l;i<=r;i++)a[i]+=c;
				ans[belo[l]]+=(r-l+1)*c;
			}
			else
			{
    
				for(rg int i=belo[l]+1;i<belo[r];i++)tag[i]+=c,ans[i]+=size[i]*c;
				clean(belo[l]),clean(belo[r]);
				for(rg int i=l;i<=R[belo[l]];i++)a[i]+=c;
				for(rg int i=r;i>=L[belo[r]];i--)a[i]+=c;
				ans[belo[l]]+=(R[belo[l]]-l+1)*c;
				ans[belo[r]]+=(r-L[belo[r]]+1)*c;
			}
		}
		else
		{
    
			ll res=0;
			if(belo[l]==belo[r])
			{
    
				for(rg int i=l;i<=r;i++)res+=a[i];
				res+=(r-l+1)*tag[belo[l]];
			}
			else
			{
    
				for(rg int i=belo[l]+1;i<belo[r];i++)res+=ans[i];
				for(rg int i=l;i<=R[belo[l]];i++)res+=a[i];
				for(rg int i=r;i>=L[belo[r]];i--)res+=a[i];
				res+=(R[belo[l]]-l+1)*tag[belo[l]];
				res+=(r-L[belo[r]]+1)*tag[belo[r]];
			}
			print(res%(c+1)),putchar('\n');
		}
	}
	return flush(),0;
}

伍

数列分块入门 5[loj6281]
题目大意：区间开根，区间求和
容易发现，一个 $2^{32}$ 级别的数开 $6$ 次根就是 $1$ 了，那么直接维护块内是否都是 $1$ 即可，如果都是 $1$ 就不用做了
块大小设为 $\sqrt {\frac n6}$ ，复杂度 $\mathcal O(n\sqrt{6n})$
~~调整块大小能优化一点复杂度~~
好像6本质上是loglogS（S是值域）
所以复杂度也可以写成 $\mathcal O(n\sqrt{nloglogS})$
code

#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#define rg register
namespace fast_IO
{
    
	const int IN_LEN=1000000,OUT_LEN=1000000;
	char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;
	inline char getchar_(){
    return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}
	inline void putchar_(const char x){
    if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}
	inline void flush(){
    fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){
    char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){
    if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){
    if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){
    if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=50001,sq=1001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],tag[sq],size[sq],ans[sq];
void clean(const int P)
{
    
	if(tag[P])return;
	tag[P]=1;
	ans[P]=0;
	for(rg int i=L[P];i<=R[P];i++)
	{
    
		a[i]=sqrt(a[i]);
		ans[P]+=a[i];
		if(a[i]!=1)tag[P]=0;
	}
}
int main()
{
    
	read(n),part=sqrt(n/6)+1;
	for(rg int i=1;i<=n;i++)
	{
    
		read(a[i]);
		const int P=i/part;
		belo[i]=P;
		if(!L[P])L[P]=i;
		R[P]=i;
		size[belo[i]]++,ans[belo[i]]+=a[i];
	}
	for(rg int q=1;q<=n;q++)
	{
    
		int opt,l,r,c;read(opt),read(l),read(r),read(c);
		if(opt==0)
		{
    
			if(belo[l]==belo[r])
			{
    
				for(rg int i=l;i<=r;i++)ans[belo[l]]-=a[i],a[i]=sqrt(a[i]),ans[belo[l]]+=a[i];
			}
			else
			{
    
				for(rg int i=belo[l]+1;i<belo[r];i++)clean(i);
				for(rg int i=l;i<=R[belo[l]];i++)ans[belo[l]]-=a[i],a[i]=sqrt(a[i]),ans[belo[l]]+=a[i];
				for(rg int i=r;i>=L[belo[r]];i--)ans[belo[r]]-=a[i],a[i]=sqrt(a[i]),ans[belo[r]]+=a[i];
			}
		}
		else
		{
    
			int res=0;
			if(belo[l]==belo[r])
			{
    
				for(rg int i=l;i<=r;i++)res+=a[i];
			}
			else
			{
    
				for(rg int i=belo[l]+1;i<belo[r];i++)res+=ans[i];
				for(rg int i=l;i<=R[belo[l]];i++)res+=a[i];
				for(rg int i=r;i>=L[belo[r]];i--)res+=a[i];
			}
			print(res),putchar('\n');
		}
	}
	return flush(),0;
}

陆

数列分块入门 6[loj6282]
题目大意：单点添加数，单点查询
分块之后对于单点加数就直接在块内插入即可，复杂度 $\mathcal O(\sqrt n)$
我们发现，这样一来，访问一个位置也是 $\mathcal O(\sqrt n)$ 的复杂度
本题数据随机，到这里就做完了
实际不随机的时候有可能有些块过大使得复杂度退化到 $\mathcal O(n^2)$
考虑重构
每插入 $\sqrt n$ 个数就对整个数组进行重构、重新分块，此处复杂度 $\mathcal O(n\sqrt n)$
这样就保证了块大小始终是 $\sqrt n$ 级别的
块大小设为 $\sqrt n$ ，复杂度 $\mathcal O(n\sqrt n)$
code

#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#define rg register
namespace fast_IO
{
    
	const int IN_LEN=1000000,OUT_LEN=1000000;
	char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;
	inline char getchar_(){
    return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}
	inline void putchar_(const char x){
    if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}
	inline void flush(){
    fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){
    char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){
    if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){
    if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){
    if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=200001,sq=1001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],tot,val[sq][sq];
void ins(const int P,const int p,const int v)
{
    
	val[P][0]++;
	for(rg int i=val[P][0];i>p;i--)val[P][i]=val[P][i-1];
	val[P][p]=v;
}
void remake()
{
    
	int top=0;
	for(rg int i=0;val[i][0];i++)
	{
    
		for(rg int j=1;j<=val[i][0];j++)a[++top]=val[i][j];
		val[i][0]=0;
	}
	for(rg int i=1;i<=top;i++)
	{
    
		const int P=i/part;
		val[P][++val[P][0]]=a[i];
	}
}
int main()
{
    
	read(n),part=sqrt(n);
	for(rg int i=1;i<=n;i++)
	{
    
		read(a[i]);
		const int P=i/part;
		val[P][++val[P][0]]=a[i];
	}
	for(rg int q=1;q<=n;q++)
	{
    
		int opt,l,r,c;read(opt),read(l),read(r),read(c);
		if(opt==0)
		{
    
			int his=0;
			for(rg int i=0;;i++)
				if(his+val[i][0]>=l)
				{
    
					ins(i,l-his,r);
					break;
				}
				else his+=val[i][0];
			if(++tot==part)remake(),tot=0;
		}
		else
		{
    
			int his=0;
			for(rg int i=0;;i++)
				if(his+val[i][0]>=r)
				{
    
					print(val[i][r-his]),putchar('\n');
					break;
				}
				else his+=val[i][0];
		}
	}
	return flush(),0;
}

柒

数列分块入门 7[loj6283]
题目大意：区间加，区间乘，单点查
同壹，额外维护乘的标记即可，可以把标记维护成x*a+b的形式，即要乘时需要将乘法、加法标记同时乘
块大小设为 $\sqrt n$ ，复杂度 $\mathcal O(n\sqrt n)$
code

#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#define rg register
namespace fast_IO
{
    
	const int IN_LEN=1000000,OUT_LEN=1000000;
	char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;
	inline char getchar_(){
    return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}
	inline void putchar_(const char x){
    if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}
	inline void flush(){
    fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){
    char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){
    if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){
    if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){
    if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=100001,sq=1001,mod=10007;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],tag[sq],cheng[sq];
void clean(const int P)
{
    
	for(rg int i=L[P];i<=R[P];i++)a[i]=(a[i]*cheng[P]+tag[P])%mod;
	tag[P]=0,cheng[P]=1;
}
int main()
{
    
	read(n),part=sqrt(n);
	for(rg int i=1;i<=n;i++)
	{
    
		read(a[i]),a[i]%=mod;
		const int P=i/part;
		belo[i]=P;
		if(!L[P])L[P]=i;
		R[P]=i;
		cheng[P]=1;
	}
	for(rg int q=1;q<=n;q++)
	{
    
		int opt,l,r,c;read(opt),read(l),read(r),read(c);
		if(opt==0)
		{
    
			c%=mod;
			if(belo[l]==belo[r])
			{
    
				clean(belo[l]);
				for(rg int i=l;i<=r;i++)a[i]=(a[i]+c)%mod;
			}
			else
			{
    
				for(rg int i=belo[l]+1;i<belo[r];i++)tag[i]=(tag[i]+c)%mod;
				clean(belo[l]),clean(belo[r]);
				for(rg int i=l;i<=R[belo[l]];i++)a[i]=(a[i]+c)%mod;
				for(rg int i=r;i>=L[belo[r]];i--)a[i]=(a[i]+c)%mod;
			}
		}
		else if(opt==1)
		{
    
			c%=mod;
			if(belo[l]==belo[r])
			{
    
				clean(belo[l]);
				for(rg int i=l;i<=r;i++)a[i]=a[i]*c%mod;
			}
			else
			{
    
				for(rg int i=belo[l]+1;i<belo[r];i++)tag[i]=tag[i]*c%mod,cheng[i]=cheng[i]*c%mod;
				clean(belo[l]),clean(belo[r]);
				for(rg int i=l;i<=R[belo[l]];i++)a[i]=a[i]*c%mod;
				for(rg int i=r;i>=L[belo[r]];i--)a[i]=a[i]*c%mod;
			}
		}
		else print((a[r]*cheng[belo[r]]+tag[belo[r]])%mod),putchar('\n');
	}
	return flush(),0;
}

捌

数列分块入门 8[loj6284]
题目大意：区间查询等于某个数的数量，并将这个区间赋值成这个数
分块，直接维护一个块里是否为同一个数、以及数的值即可，和伍很相似
块大小设为 $\sqrt n$ ，复杂度 $\mathcal O(n\sqrt{nlogn})$
code

#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#define rg register
namespace fast_IO
{
    
	const int IN_LEN=1000000,OUT_LEN=1000000;
	char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;
	inline char getchar_(){
    return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}
	inline void putchar_(const char x){
    if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}
	inline void flush(){
    fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){
    char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){
    if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){
    if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){
    if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=100001,sq=1001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],yes[sq],tag[sq],size[sq];
void clean(const int P)
{
    
	if(!yes[P])return;
	for(rg int i=L[P];i<=R[P];i++)a[i]=tag[P];
	yes[P]=0;
}
int main()
{
    
	read(n),part=sqrt(n);
	for(rg int i=1;i<=n;i++)
	{
    
		read(a[i]);
		const int P=i/part;
		belo[i]=P;
		if(!L[P])L[P]=i;
		R[P]=i;
		size[belo[i]]++;
	}
	for(rg int q=1;q<=n;q++)
	{
    
		int l,r,c,ans=0;read(l),read(r),read(c);
		if(belo[l]==belo[r])
		{
    
			clean(belo[l]);
			for(rg int i=l;i<=r;i++)
				if(a[i]==c)ans++;
				else a[i]=c;
		}
		else
		{
    
			for(rg int i=belo[l]+1;i<belo[r];i++)
				if(yes[i])
				{
    
					if(tag[i]==c)ans+=size[i];
					else tag[i]=c;
				}
				else
				{
    
					for(rg int j=L[i];j<=R[i];j++)ans+=a[j]==c;
					yes[i]=1,tag[i]=c;
				}
			clean(belo[l]),clean(belo[r]);
			for(rg int i=l;i<=R[belo[l]];i++)
				if(a[i]==c)ans++;
				else a[i]=c;
			for(rg int i=r;i>=L[belo[r]];i--)
				if(a[i]==c)ans++;
				else a[i]=c;
		}
		print(ans),putchar('\n');
	}
	return flush(),0;
}

玖

数列分块入门 9[loj6285]
题目大意：询问区间最小众数
直接分块，考虑维护出第 $i$ 个块到第 $j$ 个块的答案
此处复杂度为 $\mathcal O(n\sqrt n)$
对于一个询问
如果两个端点在同一块内直接暴力即可
否则答案一定在两个端点所在块内或者是中间块的答案
我们发现，中间的块的答案已经预处理好了
那么现在相当于有 $\sqrt n$ 个数，分别求出所有数在区间内的出现次数即可
可以预处理（可能还要个离散化）每种数的出现位置情况，二分即即可
我们观察复杂度，设块大小为P
复杂度为 $\mathcal O(\frac{n^2}{P}+nPlogn)$
块大小设为 $\sqrt {\frac n{logn}}$ ，复杂度 $\mathcal O(n\sqrt{nlogn})$
update：
这里给出的做法是空间复杂度 $\mathcal O(n)$ ，时间复杂度 $\mathcal O(n\sqrt{nlogn})$ 的
离线做法（莫队）可以做到空间复杂度 $\mathcal O(n)$ ，时间复杂度 $\mathcal O(n\sqrt{n})$
这个在线做法用分块代替二分可以做到空间复杂度 $\mathcal O(n\sqrt n)$ ，时间复杂度 $\mathcal O(n\sqrt n)$
code

#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#define rg register
namespace fast_IO
{
    
	const int IN_LEN=1000000,OUT_LEN=1000000;
	char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;
	inline char getchar_(){
    return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}
	inline void putchar_(const char x){
    if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}
	inline void flush(){
    fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
typedef long long ll;
template <typename T> inline void read(T&x){
    char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){
    if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;}
template <typename T> inline void printe(const T x){
    if(x>=10)printe(x/10);putchar(x%10+'0');}
template <typename T> inline void print(const T x){
    if(x<0)putchar('-'),printe(-x);else printe(x);}
const int maxn=100001,sq=10001;
int n,part,L[sq],R[sq],a[maxn],belo[maxn],ans[sq][sq];
int lsh[maxn],tot;
std::vector<int>p[maxn];
int tim[maxn];
int find(const int x)
{
    
	return std::lower_bound(lsh+1,lsh+tot+1,x)-lsh;
}
int count(const int l,const int r,const int x)
{
    
	int LL,RR,FI=-1,SE=-1;
	LL=0,RR=p[x].size()-1;
	while(LL<=RR)
	{
    
		const int mid=(LL+RR)>>1;
		if(p[x][mid]<=r)FI=mid,LL=mid+1;
		else RR=mid-1;
	}
	LL=0,RR=p[x].size()-1;
	while(LL<=RR)
	{
    
		const int mid=(LL+RR)>>1;
		if(p[x][mid]<l)SE=mid,LL=mid+1;
		else RR=mid-1;
	}
	return FI-SE;
}
int main()
{
    
	read(n),part=80;
	for(rg int i=1;i<=n;i++)
	{
    
		read(a[i]),lsh[i]=a[i];
		const int P=i/part;
		belo[i]=P;
		if(!L[P])L[P]=i;
		R[P]=i;
	}
	std::sort(lsh+1,lsh+n+1);
	tot=std::unique(lsh+1,lsh+n+1)-lsh-1;
	for(rg int i=1;i<=n;i++)p[a[i]=find(a[i])].push_back(i);
	for(rg int i=0;i<=belo[n];i++)
	{
    
		int res=0,mx=0;
		for(rg int j=i;j<=belo[n];j++)
		{
    
			for(rg int k=L[j];k<=R[j];k++)
			{
    
				tim[a[k]]++;
				if(tim[a[k]]>mx||tim[a[k]]==mx&&a[k]<res)mx=tim[a[k]],res=a[k];
			}
			ans[i][j]=res;
		}
		memset(tim,0,sizeof(tim));
	}
	for(rg int q=1;q<=n;q++)
	{
    
		int l,r,mx=0,res=0;read(l),read(r);
		if(belo[r]-belo[l]<=1)
		{
    
			for(rg int i=l;i<=r;i++)
			{
    
				tim[a[i]]++;
				if(tim[a[i]]>mx||tim[a[i]]==mx&&a[i]<res)mx=tim[a[i]],res=a[i];
			}
			for(rg int i=l;i<=r;i++)tim[a[i]]--;
		}
		else
		{
    
			mx=count(l,r,ans[belo[l]+1][belo[r]-1]),res=ans[belo[l]+1][belo[r]-1];
			for(rg int i=l;i<=R[belo[l]];i++)
			{
    
				const int T=count(l,r,a[i]);
				if(T>mx||T==mx&&a[i]<res)mx=T,res=a[i];
			}
			for(rg int i=r;i>=L[belo[r]];i--)
			{
    
				const int T=count(l,r,a[i]);
				if(T>mx||T==mx&&a[i]<res)mx=T,res=a[i];
			}
		}
		print(lsh[res]),putchar('\n');
	}
	return flush(),0;
}

总结

有些题有细节写的不对就会被卡，写这9题也算提升一下代码能力了吧
~~同时对分块的印象更深刻了~~

本文链接：https://blog.csdn.net/zhouyuheng2003/article/details/88893641

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

JAVA获取中文名字的首字母_java 获取名称对应小写首字母-程序员宅基地

文章浏览阅读2.1k次。转自http://blog.csdn.net/leayefang/article/details/90822551、调用FirstLetterUtil类的getFirstLetter()方法，获取姓名的首字母。如：“阿鲁卓玛”获取首字母是“alzm”。 String firstLetter = FirstLetterUtil.getFirstLetter(“阿鲁卓玛”_java 获取名称对应小写首字母

不能将 “const char “ 类型的值分配到 “char “ 类型的实体_qt 不能将 "const char " 类型的值分配到 "char " 类型的实体-程序员宅基地

文章浏览阅读2.4k次，点赞4次，收藏2次。解决方案打开项目–>属性–>c/c+±->语言–>符合模式–>否_qt 不能将 "const char *" 类型的值分配到 "char *" 类型的实体

Fatal error: Call to a member function fetch_row() on a non-object in C:\wamp\www\baicaotang\admin\m_fatal error: call to a member function fetchrow() -程序员宅基地

文章浏览阅读1.9k次。昨晚在做测试的时候，输出数据测试的时候一直出现这个问题，_fatal error: call to a member function fetchrow() on a non-object in d:\xamp

http请求详解-程序员宅基地

文章浏览阅读1.1w次，点赞10次，收藏36次。1. 简介HTTP(HyperText Transfer Protocol，超文本传输协议)是一套计算机通过网络进行通信的规则。计算机专家设计出HTTP，使HTTP客户（如Web浏览器）能够从HTTP服务器(Web服务器)请求信息和服务，HTTP目前协议的版本是1.1。HTTP遵循请求(Request)/应答(Response)模型。Web浏览器向Web服务器发送请求，Web服务器处理请求并返回适当_http请求

纯国产环境（银河麒麟 + 飞腾）JAVA程序（Springboot + Mybatis + 达梦数据库）部署_国产化 java 部署-程序员宅基地

文章浏览阅读7.4k次，点赞6次，收藏32次。目录JAVA程序部署前言项目打包银河麒麟jdk安装银河麒麟系统达梦数据库安装JAVA程序部署前言运行环境：银河麒麟 + 飞腾CPU项目框架：Springboot + Mybatis + 达梦数据库 JDK1.8上一篇写了该项目的源码，这篇主要写该项目在国产操作系统上部署以及达梦数据库在国产操作系统上安装，创建。查看项目源码请点链接纯国产环境JAVA程序搭建（Springboot + Mybatis + 达梦数据库）一项目打包修改pom文件：（注释generator插件，放开打包需要_国产化 java 部署

大尺度衰落与小尺度衰落_衰落与损耗可以相加嘛-程序员宅基地

文章浏览阅读4.5k次，点赞5次，收藏31次。无线电磁波信号在收发天线长距离（远大于传输波长）或长时间范围发生的功率变化，称为大尺度衰落，一般可以用路径损耗模型来描述，路径损耗是由发射功率在空间中的辐射扩散造成的，根据功率传输Friss公式可计算出接收信号功率为：：发射信号功率：发射天线增益：接收天线增益：电磁波的波长：收发端距离：系统的损耗因子，与传播特性无关通过对接收功率与发射功率作比值，可以把路径损耗定义为：假设通信系统是理想的（L=1)，除去收发端天线的增益（），可得理想传播环境下路径损耗与收发端距离、传输频率的关系为：因此理想环境下，路径损耗_衰落与损耗可以相加嘛

随便推点

HBase Windows 安装_windows安装hbase-程序员宅基地

文章浏览阅读4.3k次，点赞3次，收藏32次。在安装HBase之前，我们需要先安装JDK和Hadoop，具体JDK和Hadoop的安装我前面已经做过了，需要的话，请看我的另一篇博客：Hadoop Windows 安装还是那句话，在安装HBase之前，我们需要搞清楚HBase、Hadoop和Java之间版本的对应关系：我们具体可以看Apache官网：HBase、Hadoop和Java之间版本关系由于我的JDK版本为1.8和Hadoop版本为3.2.2，所以我这里下载HBase-2.4.10，现在给出Apache中Hbase所有版本下载：Hbas_windows安装hbase