分块入门

基本思想

把一个需要操作的序列分成若干块，分别处理，从而优化时间复杂度。

容易证明块长为 \(\sqrt n\) 时复杂度最优。

分块常规单次操作复杂度为 \(\mathcal{O}(\sqrt n)\)，一般可以当做 \(\mathcal{O}(\log^2n)\) 来计算复杂度。

接下来给几道例题。

T1

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间加法，单点查值。

就当模板放了。

void add(int l,int r,int c)
{
	int sid=id[l],eid=id[r];
	if(sid==eid)
	{
		for(int i=l;i<=r;i++)
		a[i]+=c;
		return ;
	}
	for(int i=l;id[i]==sid;i++)a[i]+=c;
	for(int i=sid+1;i<eid;i++)tag[i]+=c;
	for(int i=r;id[i]==eid;i--)a[i]+=c;
}

T2

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间加法，询问区间内小于某个值 \(x\) 的元素个数。

对于区间加法，类似线段树设置懒标记，对于查询操作，可以用二分解决。我们每次区间加法之后对所有涉及到的不完整区间重新排序，保证可以二分找到给定值，对于完整区间，由于顺序不变，则更新 \(tag\) 值即可。

具体的，我们对于每一个块，用一个 \(vector\) 记录值，每次排序对 \(vector\) 排序，可以证明复杂度正确。

放一下查询和更新的代码：

void work(int x)
{
	v[id[x]].clear();
	for(int i=(id[x]-1)*len+1;i<=min(n,id[x]*len);i++)
	v[id[x]].push_back(a[i]);
	sort(v[id[x]].begin(),v[id[x]].end());
}
int ask(int l,int r,int c)
{
	int sid=id[l],eid=id[r],ans=0;
	if(sid==eid)
	{
		for(int i=l;i<=r;i++)if(a[i]+tag[id[l]]<c)ans++;
		return ans;
	}
	for(int i=l;id[i]==sid;i++)if(a[i]+tag[id[l]]<c)ans++;
	for(int i=sid+1;i<eid;i++)ans+=lower_bound(v[i].begin(),v[i].end(),c-tag[i])-v[i].begin();
	for(int i=r;id[i]==eid;i--)if(a[i]+tag[id[r]]<c)ans++;
	return ans;
}

T3

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间加法，询问区间内小于某个值 \(x\) 的前驱（比其小的最大元素）。

和上一道题很类似，只是对于查询操作，我们二分找到每个块里面符合条件的最大值，取总最大值即可。

查询部分：

int sid=id[l],eid=id[r],ans=-1;
if(sid==eid)
{
	for(int i=l;i<=r;i++)if(a[i]+tag[id[l]]<c)ans=max(ans,a[i]+tag[id[l]]);
	return ans;
}
for(int i=l;id[i]==sid;i++)if(a[i]+tag[id[l]]<c)ans=max(ans,a[i]+tag[id[l]]);
for(int i=sid+1;i<eid;i++)
{
	int x=c-tag[i];
	int y=lower_bound(v[i].begin(),v[i].end(),x)-v[i].begin();
	if(--y>=0)
		ans=max(ans,v[i][y]+tag[i]);
}
for(int i=r;id[i]==eid;i--)if(a[i]+tag[id[r]]<c)ans=max(ans,a[i]+tag[id[r]]);
return ans;

T4

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间加法，区间求和。

简单，模拟线段树的思路，记录区间懒标记 \(tag\)，修改的时候对于完整区间只更新 \(tag\) 值，查询的时候对于不完整的块，让每个元素加上他所在区间的 \(tag\) 值累加，对于完整的块，则让区间和加上 \(tag\times len\)(\(len\) 为块长)后累加答案即可。

太简单，代码不放了。

T5

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间开方，区间求和。

势能分析，由于 \(\sqrt 1=1\)，所以我们用一个布尔数组 \(f\) 表示当前块是否已经全部小于等于 \(1\)，每次修改的时候对于 \(f_i\le 1\) 的块跳过，否则暴力修改即可。

整块修改部分代码：

for(int i=sid+1;i<eid;i++)
	if(!f[i]) 
	{
		f[i]=1;
		for(int j=(i-1)*len+1;j<=min(n,i*len);j++) 
		{
			tag[i]=tag[i]-a[j]+sqrt(a[j]);
			a[j]=sqrt(a[j]);
			if(a[j]!=0&&a[j]!=1)
				f[i]=0;
		}
	}

T6

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及单点插入，单点询问。

其实稍微想一想就发现，我们只需要维护每一个块的内部排列即可，对于每个修改操作，在块内正常暴力修改，对于每个查询操作，从 \(1\) 开始跑，每次减去当前块长，最后直接输出即可。

放一下代码：

void add(int x,int k)
{
	int sum=0;
	for(int i=1;i;i++)
	{
		if(x<v[i].size())
		{
			v[i].push_back(maxn);
			for(int j=v[i].size()-1;j>x;j--)
			{
				v[i][j]=v[i][j-1];	
			}
			v[i][x]=k;
			return ;
		}
		x-=v[i].size();
	}
}
void ask(int x)
{
	int sum=0;
	for(int i=1;;i++) 
	{
		if(x<v[i].size()) {cout<<v[i][x]<<'\n';return ;}
		x-=v[i].size();
	}
}

T7

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间乘法，区间加法，单点询问。

左转线段树，模拟懒标记就行了。有点难写，所以代码不放了。

T8

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间询问等于一个数 \(c\) 的元素，并将这个区间的所有元素改为 \(c\)。