首页 > 其他分享 >分块

分块

时间：2024-02-23 16:33:56浏览次数：23  
标签：分块 int sq tot 区间 op 碎块

分块

前言

在了解过树状数组和线段数之后，我们已经能处理许多区间的信息修改和查询的题目。但当信息不具有区间可加性时，用树状数组和线段树就不好处理了，这时候就可以用到一种优雅的暴力——分块。

简介

分块是一种思想，通过适当的划分，预处理一部分信息并保留，用空间换时间达到时空平衡，来完成对数列一些区间操作和区间查询的操作。效率比不上线段树和树状数组，大概是根号级别的，但它更加通用，容易实现，可以维护更复杂的信息。

具体操作

建块

首先要明确我们需要什么：

  1. 块的大小
  2. 块的数量
  3. 块的左右边界
  4. 每个元素所属的块

首先是块的大小，块的大小具体要依据实际，使时间复杂度最小。一般情况下大小为 \(\sqrt{n}\)。

sq=sqrt(n);

接下来是块的数量，要注意 \(n\) 不一定是个完全平方数，最后剩下的一些元素组成一个组。

tot=n/sq;
if(n%sq) tot++;

确定块的左右边界，直接找规律。\(L_1=1,R_1=sq,L_2=sq+1,R_2=2 \times sq , \cdots\)

得到规律：

\[L_i=(x-1) \times sq+1,R_x=x \times sq \]

还要注意 \(R_{tot}=n\)

for(int i=1;i<=tot;i++)
{
	L[i]=(i-1)*block+1;
    R[i]=i*block;
}
R[tot]=n;

确定每个元素所属的块，还是找规律。

for(int i=1;i<=n;i++) b[i]=(i-1)/sq+1;

总体代码：

sq=sqrt(n);
tot=n/sq;
if(n%sq) tot++;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
    b[i]=(i-1)/sq+1;
}
for(int i=1;i<=tot;i++)
{
    L[i]=(i-1)*sq+1;
    R[i]=i*sq;
}
R[tot]=n;

修改

以维护区间和为例。

修改区间为 \([l,r]\)，这个区间覆盖的不一定都是整块，会出现只有块中几个元素的碎块，如图：
img
共有左碎块，整块，右碎块三个部分，分别处理。

设 \(x\),\(y\) 为左碎块和右碎块的块编号。

在整块中，不必具体维护每个元素，使用和线段树类似的懒标记，将修改的信息存在里面，又类似于标记永久化，不必去修改原数组中的元素，在使用的时候加上就可以了。也就是说\(a_i\) 实际上是 \(a_i+lazy_i\)。由图可知，整块的块编号为 \([x+1,y-1]\)。

对于碎块，碎块的元素个数最多不超过两倍的块的大小，可以直接暴力修改。由图可知，左碎块的区间为 \([l,R_x]\)，右碎块的区间为 \([L_y,r]\)。

需要特判一下 \(x=y\) 的情况。

void update(int l,int r,int k)
{
    int x=b[l],y=b[r];
    if(x==y)
    {
        for(int i=l;i<=r;i++) a[i]+=k,v[x]+=k;//v为区间和
    }
    else 
    {
        for(int i=l;i<=R[x];i++) a[i]+=k,v[x]+=k;//左碎块
        for(int i=L[y];i<=r;i++) a[i]+=k,v[y]+=k;//右碎块
        for(int i=x+1;i<=y-1;i++) lazy[i]+=k,v[i]+=k*sq;//整块
    }
}

查询

同样以维护区间和为例。

与修改类似，对于整块，直接加和。对于碎块，暴力加答案。

int query(int l,int r,int k)
{
    int ans=0;
    int x=b[l],y=b[r];
    if(x==y)
    {
        for(int i=l;i<=r;i++) ans+=a[i]+lazy[x];
    }
    else 
    {
        for(int i=l;i<=R[x];i++) ans+=a[i]+lazy[x];
        for(int i=L[y];i<=r;i++) ans+=a[i]+lazy[y];
        for(int i=x+1;i<=y-1;i++) ans+=v[i];
    }
    return ans;
}

接下来就可以来做一些简单的例题了。

P2357 守墓人

https://www.luogu.com.cn/problem/P2357

分析

简单的板子题，将上述的一些操作结合就好，维护区间和。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;

ll n,m,sq,tot,a[N],b[N],v[N],L[N],R[N],lazy[N];
void add(int l,int r,int k)
{
    int x=b[l],y=b[r];
    if(x==y)
    {
        for(int i=l;i<=r;i++) a[i]+=k,v[x]+=k;//v为区间和
    }
    else 
    {
        for(int i=l;i<=R[x];i++) a[i]+=k,v[x]+=k;//左碎块
        for(int i=L[y];i<=r;i++) a[i]+=k,v[y]+=k;//右碎块
        for(int i=x+1;i<=y-1;i++) lazy[i]+=k,v[i]+=k*sq;//整块
    }
}
ll query(int l,int r)
{
    ll ans=0;
    ll x=b[l],y=b[r];
    if(x==y)
    {
        for(int i=l;i<=r;i++) ans+=a[i]+lazy[x];
    }
    else 
    {
        for(int i=l;i<=R[x];i++) ans+=a[i]+lazy[x];
        for(int i=L[y];i<=r;i++) ans+=a[i]+lazy[y];
        for(int i=x+1;i<=y-1;i++) ans+=v[i];
    }
    return ans;
}
int main ()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    sq=sqrt(n);
    tot=n/sq;
    if(n%sq) tot++;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=(i-1)/sq+1;
        v[b[i]]+=a[i];
    }
    for(int i=1;i<=tot;i++)
    {
        L[i]=(i-1)*sq+1;
        R[i]=i*sq;
    }
    R[tot]=n;
    ll op,l,r,k;
    while(m--)
    {
        cin>>op;
        if(op==1) 
        {
            cin>>l>>r>>k;
            add(l,r,k);
        }
        else if(op==2)
        {
            cin>>k;
            add(1,1,k);
        }
        else if(op==3) 
        {
            cin>>k;
            add(1,1,-k);
        }
        else if(op==4)
        {
            cin>>l>>r;
            cout<<query(l,r)<<"\n";
        }
        else cout<<query(1,1)<<"\n";
    }
    return 0;
}

P3870 [TJOI2009] 开关

https://www.luogu.com.cn/problem/P3870

分析

也是类似于板子题，不过操作变成了区间取反。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;

int a[N],b[N],lazy[N],v[N],m,n,sq;
void change(int i)
{
    v[b[i]]-=a[i]^lazy[b[i]],a[i]^=1,v[b[i]]+=a[i]^lazy[b[i]];
}
void update(int l,int r)
{
    int x=b[l],y=b[r];
    if(x==y) for(int i=l;i<=r;i++) change(i);
    else 
    {
        for(int i=l;i<=x*sq;i++) change(i);
        for(int i=(y-1)*sq+1;i<=r;i++) change(i);
        for(int i=x+1;i<=y-1;i++) lazy[i]^=1,v[i]=sq-v[i];
    }

}
int query(int l,int r)
{
    int x=b[l],y=b[r],ans=0;
    if(x==y) for(int i=l;i<=r;i++) ans+=a[i]^lazy[b[i]];
    else 
    {
        for(int i=l;i<=x*sq;i++) ans+=a[i]^lazy[b[i]];
        for(int i=(y-1)*sq+1;i<=r;i++) ans+=a[i]^lazy[b[i]];
        for(int i=x+1;i<=y-1;i++) ans+=v[i];
    }
    return ans;
}
int main ()
{
    cin>>n>>m;
    sq=sqrt(n);
    for(int i=1;i<=n;i++) b[i]=(i-1)/sq+1;
    while(m--)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==0) update(x,y);
        else cout<<query(x,y)<<"\n";
    }
    return 0;
}

P2801 教主的魔法

https://www.luogu.com.cn/problem/P2801

分析

求区间中大于等于 \(c\) 的个数。可以将每个块分别排序。

对于整块来说，因为已经排好了序，所以可以二分查找。对于碎块来说，也是暴力统计。注意修改时要重新排序碎块，整块不用排序。

时间复杂度为 \(O(n \log{n})\)。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;

int n,m,tot,sq,R[N],L[N],lazy[N],a[N],b[N],c[N];
void update(int l,int r,int k)
{
    int x=b[l],y=b[r];
    if(x==y)
    {
        for(int i=l;i<=r;i++) a[i]+=k;
        for(int i=L[x];i<=R[y];i++) c[i]=a[i];
        sort(c+L[x],c+R[y]+1);
    }
    else 
    {
        for(int i=l;i<=R[x];i++) a[i]+=k;
        for(int i=L[x];i<=R[x];i++) c[i]=a[i];
        sort(c+L[x],c+R[x]+1);
        for(int i=L[y];i<=r;i++) a[i]+=k;
        for(int i=L[y];i<=R[y];i++) c[i]=a[i];
        sort(c+L[y],c+R[y]+1);
        for(int i=x+1;i<=y-1;i++) lazy[i]+=k;
    }
}
int query(int l,int r,int k)
{
    int ans=0,x=b[l],y=b[r];
    if(x==y) 
    {
        //这里不能写成一行QAQ，不然else会与后面的if相关
        for(int i=l;i<=r;i++) 
            if(lazy[x]+a[i]>=k) 
                ans++;
    }
    else 
    {
        for(int i=l;i<=R[x];i++) if(lazy[x]+a[i]>=k) ans++;
        for(int i=L[y];i<=r;i++) if(lazy[y]+a[i]>=k) ans++;
        for(int i=x+1;i<=y-1;i++) 
        {
            int ll=L[i],rr=R[i],cnt=0,mid;
            while(ll<=rr)
            {
                mid=(ll+rr)>>1;
                if(c[mid]+lazy[i]>=k) rr=mid-1,cnt=R[i]-mid+1;
                else ll=mid+1;
            }
            ans+=cnt;
        }
    }
    return ans;
}
int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    sq=sqrt(n);
    tot=n/sq;
    if(n%sq) tot++;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=(i-1)/sq+1;
        c[i]=a[i];
    }
    for(int i=1;i<=tot;i++)
    {
        L[i]=(i-1)*sq+1;
        R[i]=i*sq;
    }
    R[tot]=n;
    for(int i=1;i<=tot;i++) sort(c+L[i],c+R[i]+1);
    char op;
    int l,r,k;
    while(m--)
    {
        cin>>op>>l>>r>>k;
        if(op=='M') update(l,r,k);
        else cout<<query(l,r,k)<<"\n";
    }
    return 0;
}

标签：分块,int,sq,tot,区间,op,碎块
From： https://www.cnblogs.com/zhouruoheng/p/18025432

相关文章

  • 数论分块性质优化DP状态
    6311.mobitel给定一个r行s列的矩阵，每个格子里都有一个正整数。问如果从左上角走到右下角，且每次只能向右或向下走到相邻格子，那么使得路径上所有数的乘积不小于n的路径有多少条？对于100%的数据，1<=r,s<=300,1<=n<=10^6，矩阵中的数不超过10^6。so，一个普通的思想就是设f[......
  • P3870 分块题解
    这篇题解有点问题（分块标记处），但现在不想修，等有空修吧link分块是一种很神奇的暴力，学了它就会觉得什么都可以用分块做。分块的主要思想就是整块快速查询，散块暴力查询。比如说，分块可以在\(O(q\sqrt{n}+n)\)的时间复杂度内解决线段树模板题。回到本题，显然我们可以用每个块维护......
  • #根号分治，分块，dfs序#洛谷 7710 [Ynoi2077] stdmxeypz
    题目传送门分析首先把距离变成深度，用dfs序转成区间问题，考虑分块，散块直接改问题是整块，如果模数比较大，可以以深度为第一维下标差分标记，这样查询时就可以前缀和知道答案如果模数比较小，那么给该块打标记，查询时枚举模数即可，然后块长取1000，模数阈值取300，就能尽量减少时间代码#in......
  • #根号分治，分块#洛谷 5309 [Ynoi2011] 初始化
    题目传送门分析如果\(x\)比较大那么可以暴力修改，\(x\)比较小的话可以用数组打标记查询的时候对于暴力修改的部分可以分块，暴力修改的同时需要给块打标记如果\(x\)比较小的情况，一段区间相当于是中间很多段周期加上前后缀（当然可以直接区间减但是我被卡常了）我调的块长是160......
  • 莫队与分块
    【根号分治】例题：等差数列加给定一个长度\(n\)的数列，初始全都是0。（\(n\leq2\times10^5\)）要求支持两种操作：\(1\;x\;y\;d\)，表示把所有下标模\(x\)等于\(y\)的位置全部加上\(d\)；\(2\;x\)，表示查询\(a_x\)当前值。做法：对于所有\(x>\sqrtn\)，我们直接暴力循环......
  • 分块
    分块的思想就是将一大段数据分成若干个整段来达到快速维护和查询的效果。运用了懒标记的思想。最简单的例子如题一个简单的整数问题#include<cstdio>#include<cmath>#defineorz(i,a,b)for(inti=a;i<=b;i++)#definesto(i,a,b)for(inti=a;i>=b;i--)using......
  • 分块与莫队算法
    1.分块分块的思想分块是把一个长度为\(N\)的数列分为\(\sqrt{N}\)个块，每个块的长度为\(\sqrt{N}\)。这样在区间操作的时候，对于每个涉及到的块，如果涉及到半个块，就直接操作；如果涉及到整个块，就整体操作。下面通过例题来了解一下分块。例1洛谷-P3372这道题可以用分块来做......
  • [算法学习笔记02]分块应用
    #[算法学习笔记02]分块应用###每日蒟蒻小故事（1/1）蒟蒻考完CSP回到S1，开始（和S2一起）新一轮的S组学习。第一周，学校学习的内容是分块应用。蒟蒻尝试听懂，并听懂了$\huge\frac{1}{3}$的内容。被五年级小朋友吊打的蒟蒻想学懂分块应用。“所以……什么是分块应用呢？”###什......
  • 整除分块
    常搭配莫反食用。莫比乌斯反演笔记P2261余数求和求\(\displaystyle\sum_{i=1}^nk\bmodi\)，\(n,k\le1e9\)。第一步：\(k\bmodi=k-i\cdot\lfloor\dfrac{k}{i}\rfloor\)，\(\text{原式}=\displaystyle\sum_{i=1}^nk-i\cdot[\frac{k}{i}]\).第二步：\(\text{原式}=nk-\displayst......
  • 数论分块
    将O（n)优化成o（根号n）[CQOI2007]余数求和题目描述给出正整数\(n\)和\(k\)，请计算\[G(n,k)=\sum_{i=1}^nk\bmodi\]对于\(100\%\)的数据，保证\(1\leqn,k\leq10^9\)voidsolve(){ intn,k;cin>>n>>k; intans=n*k; //注意推导公式字母不要弄混 for(int......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99