数据结构——分块：数列分块入门

• 数列分块入门1
• • 题目
  • 算法分析
  • Code
• 数列分块入门4
• • 题目
  • 算法分析
  • Code
• 反思与总结

最近在学习分块，在这里分享一下练习的几道习题。

关于何为分块，请阅读 这篇文章

以下是分块的经典联系题。
LOJ：数列分块入门1-9

下面来分享最近完成的数列分块入门1和数列分块入门4。

数列分块入门1

题目

算法分析

详细见 数据结构——分块入门

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define rg register
using namespace std;
typedef long long ll;
inline int sread()
{
	int x=0,f=1;char c=getchar();
	while(c>'9'||c<'0') {if(f=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	return f*x; 
}

int n,sqrtn;
ll a[50010];
int opt,l,r,c;
int k[50010],lazytag[50010];
int minn(int a,int b)
{
	return a<b?a:b;
}

void add(int l,int r,int c)
{
	for(rg int i=l;i<=minn(r,k[l]*sqrtn);++i)	a[i]+=c;
	if(k[l]!=k[r])
	{
		for(rg int i=(k[r]-1)*sqrtn+1;i<=r;++i)	a[i]+=c;
		for(rg int i=k[l]+1;i<=k[r]-1;i++)		lazytag[i]+=c;	 
	}
}
int main()
{
	n=sread(); sqrtn=sqrt(n);
	for(rg int i=1;i<=n;++i) 
	{
		scanf("%lld",&a[i]);
		k[i]=(i-1)/sqrtn+1;
	}
	for(rg int i=1;i<=n;++i)
	{
		opt=sread(); l=sread();  r=sread();  c=sread();
		if(opt==0)
		{
			add(l,r,c);
		}
		else if(opt==1)
		{
			printf("%lld\n",a[r]+lazytag[k[r]]);
		}
	}
}

Tips: 关于 l , r l,r l,r 是否在一个块内的判断及循环当中的操作还有另外一种形式，详见数列分块入门4。

数列分块入门4

题目

算法分析

详细见 数据结构——分块入门

Code

下列代码中在判断 l , r l,r l,r 是否在同一个块时，和算法分析中链接里和上面数列分块入门1中的模板有所不同，个人认为下面这个比较好理解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rg register
using namespace std;
typedef long long ll; 
inline int sread()
{
	int x=0,f=1;char c=getchar();
	while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} 
	while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();} 
	return f*x;
}
int n,opt,l,r,c,ans;
int a[50050],kname[50050],ksum[50050],kasum[50050],klen;
void add(int l,int r,int c);
void sans(int l,int r,int c);
int minn(int a,int b)
{
	return a<b?a:b;
}
int main()
{
	n=sread();	klen=sqrt(n);
	for(rg int i=1;i<=n;++i) a[i]=sread();
	for(rg int i=1;i<=n;++i)
	{
		kname[i]=(i-1)/klen+1;
		kasum[kname[i]]+=a[i];
	}
	
	for(rg int i=1;i<=n;++i)
	{
		opt=sread();
		l=sread();	r=sread();	c=sread();
		if(opt==0) add(l,r,c);
		else if(opt==1)
		{
			sans(l,r,c+1);
			printf("%int d\n",ans);
		}
	}
	return 0;
}

void add(int l,int r,int c)
{
	if(kname[l]==kname[r])//l,r在同一个块内 
	{
		for(rg int i=l;i<=r;++i)
			a[i]+=c,kasum[kname[i]]+=c;
		return ;
	}
	for(rg int i=l;kname[i]==kname[l];++i)
		a[i]+=c,kasum[kname[i]]+=c;
	for(rg int i=r;kname[i]==kname[r];--i)
		a[i]+=c,kasum[kname[i]]+=c;
	for(rg int i=kname[l]+1;i<=kname[r]-1;++i)
		ksum[i]+=c,kasum[i]+=klen*c;
}
void sans(int l,int r,int p)
{
	ans=0;
	
	if(kname[l]==kname[r])
	{
		for(rg int i=l;i<=r;++i)
			ans=(ans+a[i]+ksum[kname[i]])%p;
		return;
	}
	for(rg int i=l;kname[i]==kname[l];++i)
		ans=(ans+a[i]+ksum[kname[i]])%p;
		
	for(rg int i=r;kname[i]==kname[r];--i)
		ans=(ans+a[i]+ksum[kname[i]])%p;
		
	for(rg int i=kname[l]+1;i<=kname[r]-1;++i)
		ans=(ans+kasum[i])%p;
}

反思与总结

1.板子题，要理解并掌握模板。
2.在 f o r for for循环中关于变量 i i i 判断可以多样(详见代码)。
3.要明白每个循环中的变量所代表的含义，否则会使用错误。