投稿
  1. 高性能架构探索首页
  2. C/C++

分块入门

admin • • C/C++ • 阅读 173

分块

分块是一种非常暴力的做法，但是它复杂度是明显比线段树啥的要高的，因为他好理解。
分块的基本思想是：通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。

分块的核心思想就是把一些数据给分成一定数量的小块，然后在进行区间操作的时候直接对于包含在区间内的整块进行操作，然后将两头的部分进行暴力处理，可以大大节省时间复杂度。

分块的时候块长一般都是 \(\sqrt n\) ，也可以根据具体的题目规定不同的块长，但太大太小都不是很好处理。
对于每一种操作都有相似但又不同的做法。

操作

单点修改

因为分块这个东西是基于数组的，所以我们可以直接用下标进行 \(\Theta(1)\) 的修改操作

单点查询

和单点修改一样可以 \(\Theta(1)\) 查询

区间开方（下取整）

我们知道一个数开的平方次数一多就会变成 \(0\) 或者是 \(1\)，所以我们可以标记一下块内全是 \(0\) 或 \(1\) 的块，下次再需要处理的时候就不用在一个一个算了，直接跳过即可。复杂度不会算应该在 \(\Theta(1)\) 到 \(\Theta(\infty)\) 之间。

每一次的操作都是在以下三种情况内讨论的：

  • 当前 \(l\)，\(r\) 在同一个块内
  • 当前 \(l\)，\(r\) 在相邻的两个块内
  • 当前 \(l\)，\(r\) 之间隔着其他块

当然后两种可以合并到一起，也就是不用去写第二种情况的特判。

inline void check(int p)
{
	for(int i=(p-1)*kc+1;i<=p*kc;i++)
		if(a[i]>1)return ;
	vis[p]=1;
}
inline void change(int l,int r)
{
	if(pos[l]==pos[r])//pos存放当前i所在块的编号 
	{
		for(int i=l;i<=r;i++)
		{
			sum[pos[i]]-=a[i];//sum存放块内值的和 
			a[i]=sqrt(a[i]);//a是每一个点的值 
			sum[pos[i]]+=a[i];
		}
		return ;
	}
	else
	{
		for(int i=l;i<=pos[l]*kc;i++)
		{
			sum[pos[i]]-=a[i];
			a[i]=sqrt(a[i]);
			sum[pos[i]]+=a[i];
		}
		for(int i=(pos[r]-1)*kc+1;i<=r;i++)
		{
			sum[pos[i]]-=a[i];
			a[i]=sqrt(a[i]);
			sum[pos[i]]+=a[i];
		}
		if(pos[l]-pos[r]==1)
		{
			check(pos[l]);
			check(pos[r]);
			return ;
		}
		for(int i=pos[l]*kc+1;i<=(pos[r]-1)*kc;i++)
		{
			if(vis[pos[i]])
			{
				i+=kc-1;
				continue;
			}
			sum[pos[i]]-=a[i];
			a[i]=sqrt(a[i]);
			sum[pos[i]]+=a[i];
		}
		for(int i=pos[l];i<=pos[r];i++)
		  check(i);
		return ;
	}
}

区间求和

分块入门1

这个也和上面提到的三种情况一样，每一次查询的时候如果当前要查询的区间包含整块，可以直接累加整块的和。

inline void summ(int l,int r)
{
	int ans=0;
	if(pos[l]==pos[r])
	{
		for(int i=l;i<=r;i++)
			ans+=a[i];
		cout<<ans<<endl;
		return ;
	}
	else
	{
		for(int i=l;i<=pos[l]*kc;i++)
		  ans+=a[i];
		for(int i=(pos[r]-1)*kc+1;i<=r;i++)
		  ans+=a[i];
//		if(pos[r]-pos[l]==1)
//		{
//			cout<<ans<<endl;
//			return ;
//		}
		for(int i=pos[l]+1;i<=pos[r]-1;i++)
			ans+=sum[i];
		cout<<ans<<endl;
		return ;
	}
}

区间加

分块入门1
我们在对于整块进行区间加的操作的时候，我们可以直接在整块的 tag 上进行修改，然后再查询的时候直接输出即可，当区间查询的时候我们对于包含的整块直接累加当前块内的和和块长乘 tag 即可

inline void add(int l,int r,int c)
{
	if(pos[l]==pos[r])
	{
		for(int i=l;i<=r;i++)
		  a[i]+=c;
		return ;
	}
	else
	{
		for(int i=l;i<=pos[l]*kc;i++)
		  a[i]+=c;
		for(int i=(pos[r]-1)*kc+1;i<=r;i++)
		  a[i]+=c;
		for(int i=pos[l]+1;i<=pos[r]-1;i++)
		  tag[i]+=c;
		return ;
	}
}

查询区间内小于某数的数的个数

我们可以对于一个整块进行排序，然后二分查询里面的大于等于 \(C\) 的值，比如可以用 lower_bound 来查找，其次我们需要注意的是，每一次暴力修改完某个块内的值的时候，都要对于整个块重新进行排序，这个时候可以用 vector 来简化操作。

void resort(int x)
{
    a1[x].clear();
    for(int i=l[x];i<=r[x];i++)
        a1[x].push_back(a[i]);
    sort(a1[x].begin(),a1[x].end());
}
int cxk(int x,int y,int c)
{
    int ans=0;
    if(pos[x]==pos[y])
    {
        for(int i=x;i<=y;i++)
            if(a[i]+tag[pos[i]]<c)ans++;
        return ans;
    }
    for(int i=x;i<=r[pos[x]];i++)
        if(a[i]+tag[pos[i]]<c)ans++;
    for(int i=pos[x]+1;i<pos[y];i++)
        ans+=lower_bound(a1[i].begin(),a1[i].end(),c-tag[i])-a1[i].begin();
    for(int i=l[pos[y]];i<=y;i++)
        if(a[i]+tag[pos[i]]<c)ans++;
    return ans;
}

询问区间内某个值的前驱

遇到这种问题我们可以用 STL 中的 set 来解决，因为里面，自带一些好用的函数，也可以和上面一样用 vector 来解决，对于每一个整块，我们可以用 set 的 lower_bound 函数来找到下标，然后在和之前暴力求的散块的 ans 来取一个 max，达到寻找某个值的前驱的效果。

int query(int l,int r,int c)
{
    int ans=-1;
    for(int i=l;i<=min(pos[l]*kc,r);i++)
    {
        int val=v[i]+tag[pos[l]];
        if(val<c)ans=max(val,ans);
    }
    if(pos[l]!=pos[r]) 
        for(int i=(pos[r]-1)*kc+1;i<=r;i++)
        {
            int val=v[i]+tag[pos[r]];
            if(val<c)ans=max(val,ans);
        }
    for(int i=pos[l]+1;i<=pos[r]-1;i++)
    {
        int x=c-tag[i];
        set<int>::iterator it=st[i].lower_bound(x);
        if(it==st[i].begin())continue;
        --it;
        ans=max(ans,*it+tag[i]);
    }
    return ans;
}

分块入门1~9

因为上方的所有操作都是基于这九道题目给出的，所以不在进行讲解只是放出代码，也可以去看看这位的博客
http://hzwer.com/8053.html

分块入门1

#include<bits/stdc++.h>
#define int long long
#define N 1000010
using namespace std;
int a[N],tag[N],n,pos[N],kc;
inline void add(int l,int r,int c)
{
	if(pos[l]==pos[r])
	{
		for(int i=l;i<=r;i++)
		  a[i]+=c;
		return ;
	}
	else
	{
		for(int i=l;i<=pos[l]*kc;i++)
		  a[i]+=c;
		for(int i=(pos[r]-1)*kc+1;i<=r;i++)
		  a[i]+=c;
		for(int i=pos[l]+1;i<=pos[r]-1;i++)
		  tag[i]+=c;
		return ;
	}
}
signed main()
{
	cin>>n;
	kc=sqrt(n);
	for(int i=1;i<=n;i++)
	  cin>>a[i];
	for(int i=1;i<=n;i++)
	  pos[i]=(i-1)/kc+1;
	for(int i=1;i<=n;i++)
	{
		int op,l,r,c;
		cin>>op>>l>>r>>c;
		if(op==0)add(l,r,c);
		else cout<<(a[r]+tag[pos[r]])<<endl;
	}
	return 0;
}

分块入门2

#include<bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n,m,q,tot,ans,kc,num,l[N],r[N],pos[N];
int a[N],tag[N];
vector<int>a1[N>>1];
void build()
{
    kc=sqrt(n);
    num=n/kc;
	if(n%kc)num++;
    r[num]=n;
    for(int i=1;i<=n;i++)
        pos[i]=(i-1)/kc+1,a1[pos[i]].push_back(a[i]);
    for(int i=1;i<=num;i++)
        l[i]=(i-1)*kc+1,r[i]=i*kc,sort(a1[i].begin(),a1[i].end());
}
void resort(int x)
{
    a1[x].clear();
    for(int i=l[x];i<=r[x];i++)
        a1[x].push_back(a[i]);
    sort(a1[x].begin(),a1[x].end());
}
void add(int x,int y,int C)
{
    if(pos[x]==pos[y])
    {
        for(int i=x;i<=y;i++)
            a[i]+=C;
        resort(pos[x]);
        return;
    }
    for(int i=x;i<=r[pos[x]];i++)
        a[i]+=C;
    for(int i=pos[x]+1;i<pos[y];i++)
        tag[i]+=C;
    for(int i=l[pos[y]];i<=y;i++)
        a[i]+=C;
    resort(pos[x]);
    resort(pos[y]);
}
int cxk(int x,int y,int c)
{
    int ans=0;
    if(pos[x]==pos[y])
    {
        for(int i=x;i<=y;i++)
            if(a[i]+tag[pos[i]]<c)ans++;
        return ans;
    }
    for(int i=x;i<=r[pos[x]];i++)
        if(a[i]+tag[pos[i]]<c)ans++;
    for(int i=pos[x]+1;i<pos[y];i++)
        ans+=lower_bound(a1[i].begin(),a1[i].end(),c-tag[i])-a1[i].begin();
    for(int i=l[pos[y]];i<=y;i++)
        if(a[i]+tag[pos[i]]<c)ans++;
    return ans;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
	cin>>a[i];
    build();
    while(n--)
    {
        int op,x,y,c;
        cin>>op>>x>>y>>c;
        if(op==0)add(x,y,c);
        else cout<<cxk(x,y,c*c)<<endl;
    }
    return 0;
}

分块入门3

#include<bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
int n,kc,v[N],pos[N],tag[N];
set<int>st[N>>5];
void add(int a,int b,int c)
{
    for(int i=a;i<=min(pos[a]*kc,b);i++)
    {
        st[pos[a]].erase(v[i]);
        v[i]+=c;
        st[pos[a]].insert(v[i]);
    }
    if(pos[a]!=pos[b])
    {
        for(int i=(pos[b]-1)*kc+1;i<=b;i++)
        {
            st[pos[b]].erase(v[i]);
            v[i]+=c;
            st[pos[b]].insert(v[i]);
        }
    }
    for(int i=pos[a]+1;i<=pos[b]-1;i++)
        tag[i]+=c;
}
int query(int l,int r,int c)
{
    int ans=-1;
    for(int i=l;i<=min(pos[l]*kc,r);i++)
    {
        int val=v[i]+tag[pos[l]];
        if(val<c)ans=max(val,ans);
    }
    if(pos[l]!=pos[r]) 
        for(int i=(pos[r]-1)*kc+1;i<=r;i++)        
        {
            int val=v[i]+tag[pos[r]];
            if(val<c)ans=max(val,ans);
        }
    for(int i=pos[l]+1;i<=pos[r]-1;i++)
    {
        int x=c-tag[i];
        set<int>::iterator it=st[i].lower_bound(x);
        if(it==st[i].begin())continue;
        --it;
        ans=max(ans,*it+tag[i]);
    }
    return ans;
}
signed main()
{
    cin>>n;kc=1000;
    for(int i=1;i<=n;i++)
	   cin>>v[i];
    for(int i=1;i<=n;i++)
    {
        pos[i]=(i-1)/kc+1;
        st[pos[i]].insert(v[i]);
    }
    for(int i=1;i<=n;i++)
    {
    	int f,l,r,c;
        cin>>f>>l>>r>>c;
        if(f==0)add(l,r,c);
        if(f==1)printf("%d\n",query(l,r,c));
    }
    return 0;
}

分块入门4

#include<bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int a[N],pos[N],n,kc,sum[N],tag[N];
inline void add(int l,int r,int c)
{
	if(pos[l]==pos[r])
	{
		for(int i=l;i<=r;i++)
		{
			sum[pos[i]]-=a[i];
			a[i]+=c;
			sum[pos[i]]+=a[i];
		}
		return ;
	}
	for(int i=l;i<=pos[l]*kc;i++)
	{
		sum[pos[i]]-=a[i];
		a[i]+=c;
		sum[pos[i]]+=a[i];
	}
	for(int i=(pos[r]-1)*kc+1;i<=r;i++)
	{
		sum[pos[i]]-=a[i];
		a[i]+=c;
		sum[pos[i]]+=a[i];
	}
	for(int i=pos[l]+1;i<=pos[r]-1;i++)
		tag[i]+=c;
}
inline int summ(int l,int r)
{
	int ans=0;
	if(pos[l]==pos[r])
	{
		for(int i=l;i<=r;i++)
			ans=(ans+a[i]+tag[pos[i]]);
		return ans;
	}
	for(int i=l;i<=pos[l]*kc;i++)
		ans=(ans+a[i]+tag[pos[i]]);
	for(int i=(pos[r]-1)*kc+1;i<=r;i++)
	    ans=(ans+a[i]+tag[pos[i]]);
	for(int i=pos[l]+1;i<=pos[r]-1;i++)
		ans=(ans+(tag[i]*kc)+sum[i]);
	return ans;
}
signed main()
{
	cin>>n;
	kc=sqrt(n);
	for(int i=1;i<=n;i++)
	  cin>>a[i];
	for(int i=1;i<=n;i++)
	  pos[i]=(i-1)/kc+1,
	  sum[pos[i]]+=a[i];
	for(int i=1;i<=n;i++)
	{
		int op,l,r,c;
		cin>>op>>l>>r>>c;
		if(op==0)add(l,r,c);
		else if(op==1)cout<<(summ(l,r)%(c+1))<<endl;
	}
	return 0;
}

分块入门5

#include<bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
int n,m,kc,a[N],sum[N],pos[N],vis[N];
inline void check(int p)
{
	for(int i=(p-1)*kc+1;i<=p*kc;i++)
		if(a[i]>1)return ;
	vis[p]=1;
}
inline void change(int l,int r)
{
	if(pos[l]==pos[r])//pos存放当前i所在块的编号 
	{
		for(int i=l;i<=r;i++)
		{
			sum[pos[i]]-=a[i];//sum存放块内值的和 
			a[i]=sqrt(a[i]);//a是每一个点的值 
			sum[pos[i]]+=a[i];
		}
		return ;
	}
	else
	{
		for(int i=l;i<=pos[l]*kc;i++)
		{
			sum[pos[i]]-=a[i];
			a[i]=sqrt(a[i]);
			sum[pos[i]]+=a[i];
		}
		for(int i=(pos[r]-1)*kc+1;i<=r;i++)
		{
			sum[pos[i]]-=a[i];
			a[i]=sqrt(a[i]);
			sum[pos[i]]+=a[i];
		}
//		if(pos[l]-pos[r]==1)
//		{
//			check(pos[l]);
//			check(pos[r]);
//			return ;
//		}
		for(int i=pos[l]*kc+1;i<=(pos[r]-1)*kc;i++)
		{
			if(vis[pos[i]])
			{
				i+=kc-1;
				continue;
			}
			sum[pos[i]]-=a[i];
			a[i]=sqrt(a[i]);
			sum[pos[i]]+=a[i];
		}
		for(int i=pos[l];i<=pos[r];i++)
		  check(i);
		return ;
	}
}
inline void summ(int l,int r)
{
	int ans=0;
	if(pos[l]==pos[r])
	{
		for(int i=l;i<=r;i++)
			ans+=a[i];
		cout<<ans<<endl;
		return ;
	}
	else
	{
		for(int i=l;i<=pos[l]*kc;i++)
		  ans+=a[i];
		for(int i=(pos[r]-1)*kc+1;i<=r;i++)
		  ans+=a[i];
//		if(pos[r]-pos[l]==1)
//		{
//			cout<<ans<<endl;
//			return ;
//		}
		for(int i=pos[l]+1;i<=pos[r]-1;i++)
			ans+=sum[i];
		cout<<ans<<endl;
		return ;
	}
}
signed main()
{
	cin>>n;
	kc=sqrt(n);
	for(int i=1;i<=n;i++)
		cin>>a[i];
	m=n;
	for(int i=1;i<=n;i++)
		pos[i]=(i-1)/kc+1;
	for(int i=1;i<=n;i++)
		sum[pos[i]]+=a[i];
	for(int i=1;i<=m;i++)
	{
		int k,l,r,c;
		cin>>k>>l>>r>>c;
		if(l>r)swap(l,r);
		if(k==0)change(l,r);
		else summ(l,r);
	}
//	for(int i=1;i<=n;i++)
//		cout<<a[i]<<' ';
	return 0;
}

分块入门6

#include<bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n,m,kc,a[N],st[N],top;
vector<int>e[N>>5];
pair<int,int> summ(int b)
{
	int x=1;
	while(b>e[x].size())
	  b-=e[x].size(),x++;
	return make_pair(x,b-1);
}
inline void rebuild()
{
	top=0;
	for(int i=1;i<=m;i++)
	{
		for(vector<int>::iterator j=e[i].begin();j!=e[i].end();j++)
		  st[++top]=*j;
		e[i].clear();
	}
	int kc2=sqrt(top);
	for(int i=1;i<=top;i++)
	  e[(i-1)/kc2+1].push_back(st[i]);
	m=(top-1)/kc2+1;
}
inline void insert(int l,int r)
{
	pair<int,int>t=summ(l);
	e[t.first].insert(e[t.first].begin()+t.second,r);
	if(e[t.first].size()>20*kc)
	  rebuild();
}
signed main()
{
	cin>>n;
	kc=sqrt(n);
	for(int i=1;i<=n;i++)
	  cin>>a[i];
	for(int i=1;i<=n;i++)
	  e[(i-1)/kc+1].push_back(a[i]);
	m=(n-1)/kc+1;
	for(int i=1;i<=n;i++)
	{
		int op,l,r,c;
		cin>>op>>l>>r>>c;
		if(op==0)insert(l,r);
		if(op==1)
		{
			pair<int,int>t=summ(r);
			cout<<e[t.first][t.second]<<endl;
		}
	}
	return 0;
}

分块入门7

#include<bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n,kc,a[N],pos[N],tag[N],lazy[N];
inline void resort(int p)
{
	for(int i=(p-1)*kc+1;i<=min(p*kc,n);i++)
	  a[i]=(a[i]*lazy[p]+tag[p])%10007;
	tag[p]=0;lazy[p]=1;
}
inline void solve(int f,int l,int r,int c)
{
	resort(pos[l]);
	for(int i=l;i<=min(r,pos[l]*kc);i++)
	{
		if(f==0)a[i]+=c;
		else a[i]*=c;
		a[i]%=10007;
	}
	if(pos[l]!=pos[r])
	{
		resort(pos[r]);
		for(int i=(pos[r]-1)*kc+1;i<=r;i++)
		{
			if(f==0)a[i]+=c;
			else a[i]*=c;
			a[i]%=10007;
		}
	}
	for(int i=pos[l]+1;i<=pos[r]-1;i++)
	{
		if(f==0)tag[i]=(tag[i]+c)%10007;
		else
		{
			tag[i]=(tag[i]*c)%10007;
			lazy[i]=(lazy[i]*c)%10007;
		}
	}
	return ;
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	kc=sqrt(n);
	for(int i=1;i<=n;i++)
		pos[i]=(i-1)/kc+1,lazy[i]=1;
	for(int i=1;i<=n;i++)
	{
		int op,l,r,c;
		cin>>op>>l>>r>>c;
		if(op==2) cout<<(a[r]*lazy[pos[r]]+tag[pos[r]])%10007<<endl;
		else solve(op,l,r,c);
	}
	return 0;
}

分块入门8

#include<bits/stdc++.h>
#define int long long
#define N 1001000
using namespace std;
int n,kc,a[N],pos[N],tag[N];
inline void recep(int p)
{
	if(tag[p]==-1)return ;
	for(int i=(p-1)*kc+1;i<=min(n,p*kc);i++)
		a[i]=tag[p];
	tag[p]=-1;
	return ;
}
inline int cxk(int l,int r,int c)
{
	int ans=0;
	recep(pos[l]);
	for(int i=l;i<=min(pos[l]*kc,r);i++)
		if(a[i]==c)ans++;
		else a[i]=c;
	if(pos[l]!=pos[r])
	{
		recep(pos[r]);
		for(int i=(pos[r]-1)*kc+1;i<=r;i++)
		  if(a[i]==c)ans++;
		  else a[i]=c;
	}
	for(int i=pos[l]+1;i<=pos[r]-1;i++)
	{
		if(tag[i]!=-1)
		{
			if(tag[i]==c)ans+=kc;
			else tag[i]=c;
		}
		else
		{
			for(int j=(i-1)*kc+1;j<=kc*i;j++)
			  if(a[j]==c)ans++;
			  else a[j]=c;
			tag[i]=c;
		}
	}
	return ans;
}
signed main()
{
	cin>>n;
	kc=sqrt(n);
	memset(tag,-1,sizeof tag);
	for(int i=1;i<=n;i++)
	  cin>>a[i];
	for(int i=1;i<=n;i++)
	  pos[i]=(i-1)/kc+1;
	for(int i=1;i<=n;i++)
	{
		int l,r,c;
		cin>>l>>r>>c;
		cout<<cxk(l,r,c)<<endl;
	}
	return 0;
}

原文链接: https://www.cnblogs.com/Multitree/p/17054991.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

    分块入门

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/312532

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年2月16日 下午12:26
下一篇 2023年2月16日 下午12:26

相关推荐