1. Toy模板网首页
  2. > Toy博客

分块学习笔记

8月前 作者：cppom 分类：Toy博客 阅读(22) 违法举报

这篇具有很好参考价值的文章主要介绍了分块学习笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

学了分块，感觉这玩意好难啊，怎么听起来这么简单？【】【】分块！

先推荐一个东西：loj 分块全家桶！

首先，把一整个数组劈成 \(\sqrt n\) 块是最优的！（当然如果你想写一个 \(114514\) 块的分块也没问题但他不优啊！）

长这样：

这样它的复杂度是：

  • 预处理：\(O(n\sqrt n+q)\)
  • 在线处理：\(O(q\sqrt n+n)\)

分块其实就是三层的树，每个非叶子结点的节点有 \(\sqrt n\) 个子节点。

像这样：

（第一层：整个大区间，第二层：每个块，第三层：每个位置）

然后呢？

没了。

你问咋处理？每个块的处理，两边的“散块”就暴力啊！

分块的思路很简单。

但某些毒瘤题的代码不做评价。

T1

模板。只放代码注释不放解析。

本题代码
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void write(i128 x)
{
	if(x>=10)write(x/10);
	putchar(x%10+'0');
}
LL n,a[50010],lz[50010],op,l,r,c,kc;
//kc:块长（根号n），lz:类似lazytag，给整个块的标记
LL q(LL x)
{
	return lz[x/kc]+a[x];
}
void ud(LL l,LL r,LL c)
{
	if(l/kc==r/kc)
	{
		rep(i,l,r,1)
		{
			a[i]+=c;
		}
	}
	else
	{
		rep(i,l,(l/kc+1)*kc-1,1)a[i]+=c;
		rep(i,r/kc*kc,r,1)a[i]+=c;
        //两边的散块
		repn(i,l/kc+1,r/kc,1)lz[i]+=c;
        //中间的整块
	}
}
int main()
{
	cin>>n;
	kc=sqrt(n);
	rep(i,1,n,1)cin>>a[i];
	rep(i,1,n,1)
	{
		cin>>op>>l>>r>>c;
		if(!op)
		{
			ud(l,r,c);
		}
		else
		{
			cout<<q(r)<<endl;
		}
	}
	return 0;
}

T2

这道题目的基础是咋求一个数 \(c\) 在 \(\left [l,r\right ]\) 的排名。

咋办？肯定二分啊！排个序！

void px(LL x)
{
	rep(i,max(1LL,x*kc),min(n,kc*(x+1)-1),1)b[i]=a[i];
	sort(b+max(1LL,x*kc),b+min(n+1,(x+1)*kc));
}

为什么排序用 b[i] 而不是用 a[i]？

两边的散块：你这么说，我不存在？

你排序，和原来不一样了，散块表示：你【】【】！

剩下的有手就行。

有个坑点，记得及时排序。

本题代码
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 LL
#define lowbit(x) ((x)&(-(x)))
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void write(i128 x)
{
	if(x>=10)write(x/10);
	putchar(x%10+'0');
}
LL n,a[50010],b[50010],lz[50010],op,l,r,c,kc;
LL q(LL l,LL r,LL c)
{
	LL sum=0;
	if(l/kc==r/kc)
	{
		rep(i,l,r,1)
		{
			if(a[i]+lz[i/kc]<c)sum++;
		}
	}
	else
	{
		rep(i,l,min(n,(l/kc+1)*kc-1),1)
		{
			if(a[i]+lz[i/kc]<c)sum++;
		}
		rep(i,r/kc*kc,r,1)
		{
			if(a[i]+lz[i/kc]<c)sum++;
		}
		repn(i,l/kc+1,r/kc,1)
		{
			LL l=i*kc-1,r=(i+1)*kc,mid;
			while(l+1<r)
			{
				mid=l+r>>1;
				if(b[mid]+lz[i]<c)l=mid;
				else r=mid;
			}
			sum+=l-i*kc+1;
		}
	}
	return sum;
}
void px(LL x)
{
	rep(i,max(1LL,x*kc),min(n,kc*(x+1)-1),1)b[i]=a[i];
	sort(b+max(1LL,x*kc),b+min(n+1,(x+1)*kc));
}
void ud(LL l,LL r,LL c)
{
	if(l/kc==r/kc)
	{
		rep(i,l,r,1)
		{
			a[i]+=c;
		}
		px(l/kc);
	}
	else
	{
		rep(i,l,min(n,(l/kc+1)*kc-1),1)a[i]+=c;
		rep(i,r/kc*kc,r,1)a[i]+=c;
		px(l/kc);
		px(r/kc);
		repn(i,l/kc+1,r/kc,1)lz[i]+=c;
	}
}
int main()
{
	cin>>n;
	kc=sqrt(n);
	rep(i,1,n,1)
	{
		read(a[i]);
	}
	rep(i,0,n/kc,1)
	{
		px(i);
	}
	rep(i,1,n,1)
	{
	    read(op);
	    read(l);
	    read(r);
	    read(c);
		if(!op)
		{
			ud(l,r,c);
		}
		else
		{
			write(q(l,r,c*c));
			puts("");
		}
	}
	return 0;
}

T3

和上一题几乎一样。

就是维护排好序的序列。

对了我上题写的太石山了就重新写了一遍&改了自己的模板。

本题代码
#include<stdio.h>
#include<bits/stdc++.h>
#define N 100010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 LL
#define lowbit(x) ((x)&(-(x)))
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void writing(i128 x)
{
	if(x>=10)writing(x/10);
	putchar(x%10+'0');
}
void write(i128 x)
{
	if(x<0)
	{
		cout<<'-';
		x=-x;
	}
	writing(x);
}
LL n,a[N],b[N],add[N],st[N],ed[N],pos[N],op,l,r,c,x,num;
vector<LL>sum[N];
void build()
{
    x=sqrt(n);
	num=n/x;
    if(n%x)num++;
	rep(i,1,num,1)
	{
        st[i]=(i-1)*x+1;
        ed[i]=x*i;
    }
    ed[num]=n;
    rep(i,1,n,1)
	{
        pos[i]=(i-1)/x+1;
        sum[pos[i]].push_back(a[i]);
    }
    rep(i,1,num,1)sort(sum[i].begin(),sum[i].end());
}
void change(LL l,LL r,LL k)
{
    LL p=pos[l],q=pos[r];
    if(p==q)
	{
        rep(i,l,r,1)
		{
        	a[i]+=k;
        }
        sum[p].clear();
        rep(i,st[p],ed[p],1)
		{
        	sum[p].push_back(a[i]);
        }
        sort(sum[p].begin(),sum[p].end());
        return;
    }
    repn(i,p+1,q,1)
	{
        add[i]+=k;
    }
	rep(i,l,ed[p],1)
	{
		a[i]+=k;
    }
    sum[p].clear();
    rep(i,st[p],ed[p],1)
	{
       	sum[p].push_back(a[i]);
    }
	sort(sum[p].begin(),sum[p].end());
    rep(i,st[q],r,1)
	{
		a[i]+=k;
    }
    sum[q].clear();
    rep(i,st[q],ed[q],1)
	{
	    sum[q].push_back(a[i]);
    }
    sort(sum[q].begin(),sum[q].end());
}
LL ask(LL l,LL r,LL k)
{
    LL ans=-1,p=pos[l],q=pos[r];
    if(p==q)
	{
		rep(i,l,r,1)if(a[i]+add[p]<k)ans=max(ans,a[i]+add[p]);
        return ans;
    }
    repn(i,p+1,q,1)
	{
    	LL tt=lower_bound(sum[i].begin(),sum[i].end(),k-add[i])-sum[i].begin();
		if(tt==0)continue;
		ans=max(ans,add[i]+sum[i][tt-1]);
    }
	rep(i,l,ed[p],1)if(a[i]+add[p]<k)ans=max(ans,a[i]+add[p]);
    rep(i,st[q],r,1)if(a[i]+add[q]<k)ans=max(ans,a[i]+add[q]);
    return ans;
}
int main()
{
	cin>>n;
	rep(i,1,n,1)
	{
		read(a[i]);
	}
	build();
	rep(i,1,n,1)
	{
	    read(op);
	    read(l);
	    read(r);
	    read(c);
		if(!op)
		{
			change(l,r,c);
		}
		else
		{
			write(ask(l,r,c));
			puts("");
		}
	}
	return 0;
}

T4

水题，维护一段块的和。

本题代码
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 LL
#define lowbit(x) ((x)&(-(x)))
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void write(i128 x)
{
	if(x>=10)write(x/10);
	putchar(x%10+'0');
}
LL n,a[50010],lz[50010],ss[50010],op,l,r,c,kc;
LL q(LL l,LL r,LL c)
{
	LL sum=0;
	if(l/kc==r/kc)
	{
		rep(i,l,r,1)
		{
			sum+=a[i]%c+lz[i/kc]%c;
			sum%=c;
		}
	}
	else
	{
		rep(i,l,(l/kc+1)*kc-1,1)
		{
			sum+=a[i]%c+lz[i/kc]%c;
			sum%=c;
		}
		rep(i,r/kc*kc,r,1)
		{
			sum+=a[i]%c+lz[i/kc]%c;
			sum%=c;
		}
		repn(i,l/kc+1,r/kc,1)
		{
			sum+=ss[i];
			sum%=c;
		}
	}
	return sum;
}
void ud(LL l,LL r,LL c)
{
	if(l/kc==r/kc)
	{
		rep(i,l,r,1)
		{
			a[i]+=c;
			ss[i/kc]+=c;
		}
	}
	else
	{
		rep(i,l,(l/kc+1)*kc-1,1)
		{
			a[i]+=c;
			ss[i/kc]+=c;
		}
		rep(i,r/kc*kc,r,1)
		{
			a[i]+=c;
			ss[i/kc]+=c;
		}
		repn(i,l/kc+1,r/kc,1)
		{
			lz[i]+=c;
			ss[i]+=c*kc;
		}
	}
}
int main()
{
	cin>>n;
	kc=sqrt(n);
	rep(i,1,n,1)read(a[i]);
	rep(i,1,n,1)ss[i/kc]+=a[i];
	rep(i,1,n,1)
	{
		read(op);
		read(l);
		read(r);
		read(c);
		if(!op)
		{
			ud(l,r,c);
		}
		else
		{
			write(q(l,r,c+1));
			puts("");
		}
	}
	return 0;
}

T5

啊？根号可以用分块吗？——刚开题的时候的我beeeeeeeeeee like

直到我想起一道题，但是忘了是哪道。

你想啊，就这么点数据范围（也许 \(a_i\) 范围上到 LONG_LONG_MAX 都可以做！），根号不是几下就废了吗？（变成 \(1\) 或者 \(0\)）

没算是几下，应该是不超过 \(10\) 下，够了。

所有部分，包括两头散块和中间整块，都可以用一个 sol 函数解决。

这个函数干嘛呢？

把需要处理的块内部还可以开方的开方。

好了就是这么简单。文章来源地址https://www.toymoban.com/news/detail-839329.html

本题代码
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 LL
#define lowbit(x) ((x)&(-(x)))
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void writing(i128 x)
{
	if(x>=10)writing(x/10);
	putchar(x%10+'0');
}
void write(i128 x)
{
	if(x<0)
	{
		cout<<'-';
		x=-x;
	}
	writing(x);
}
LL n,a[50010],ss[50010],op,l,r,c,kc;
vector<LL>b[50010];
LL q(LL l,LL r)
{
	LL sum=0;
	if(l/kc==r/kc)
	{
		rep(i,l,r,1)
		{
			sum+=a[i];
		}
	}
	else
	{
		rep(i,l,(l/kc+1)*kc-1,1)
		{
			sum+=a[i];
		}
		rep(i,r/kc*kc,r,1)
		{
			sum+=a[i];
		}
		repn(i,l/kc+1,r/kc,1)
		{
			sum+=ss[i];
		}
	}
	return sum;
}
void sol(LL l,LL r)
{
	LL po=l/kc;
	repn(i,0,b[po].size(),1)
	{
		LL j=b[po][i];
		if(j>=l&&j<=r)
		{
			ss[po]-=a[j];
			a[j]=sqrt(a[j]);
			ss[po]+=a[j];
			if(a[j]<=1)
			{
				b[po].erase(b[po].begin()+i--);
			}
		}
	}
}
void ud(LL l,LL r)
{
	if(l/kc==r/kc)
	{
		sol(l,r);
	}
	else
	{
		sol(l,(l/kc+1)*kc-1);
		sol(r/kc*kc,r);
		repn(i,l/kc+1,r/kc,1)
		{
			sol(i*kc,(i+1)*kc-1);
		}
	}
}
int main()
{
	cin>>n;
	kc=sqrt(n);
	rep(i,1,n,1)read(a[i]);
	rep(i,1,n,1)
	{
		b[i/kc].push_back(i);
		ss[i/kc]+=a[i];
	}
	rep(i,1,n,1)
	{
		read(op);
		read(l);
		read(r);
		read(c);
		if(!op)
		{
			ud(l,r);
		}
		else
		{
			write(q(l,r));
			puts("");
		}
	}
	return 0;
}

到了这里，关于分块学习笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 刷论文的感觉太棒了！（对比学习 / CLIP改进 / 视频理解）

    刷论文的感觉太棒了！（对比学习 / CLIP改进 / 视频理解）

    😍😍😍更多精彩福利😍😍😍 1. 对比学习论文总结 学习视频： 李沐-MoCo论文逐段精读 李沐-对比学习论文综述 阶段 代表工作 百花齐放（18-19中） Inst Disc : memory Bank, 每张图都是一个类别（个体判别） Inva Spread : end-to-end, 在同一mini-batch中选正负样本 CPC V1 ：用预测未来的代

    2023年04月14日
    浏览(77)
  • 破玩意 | 用 HTTPS 传纸条

    破玩意 | 用 HTTPS 传纸条

    我和小宇早恋了，上课的时候老说话 。 老师把我们的座位分得很远，我在第一排，她在最后一排，我们中间隔了很多人。 但我们还是想通过传纸条的方式交流。 我们中间的那些同学，虽然坏心思比较多， 但好在可以保证将纸条传递到位 ，于是我们用传纸条的方式，一直秘

    2024年01月19日
    浏览(21)
  • 翻车了，lombok这玩意真坑

    翻车了，lombok这玩意真坑

    青柠最近在写自己的项目，刚开始就写不下去了，心态崩了，这啥玩意啊，就是找不到问题在哪？ 早前，在项目当中引入了Lombok插件，着实解放了双手，代替了一些重复的简单工作(Getter,Setter,toString等方法的编写)。 但是，在使用的过程当中，也发现了一些问题，开始的时候

    2024年02月08日
    浏览(29)
  • C++好难（6）：模板初阶

    C++好难（6）：模板初阶

    1. 泛型编程 2. 函数模板 3. 类模板 目录 【本节目标】 1.泛型编程 2.函数模板 概念： 格式： 原理： 实例化： 1.隐式实例化： 2.显式实例化 原则一： 原则二： 原则三： 3.类模板 格式 类模板的实例化 如何实现一个通用的交换函数呢？ 以下面的交换函数为例： 可以看到两种不

    2024年02月03日
    浏览(30)
  • C++好难（4）：类和对象（下）

    C++好难（4）：类和对象（下）

    okk我们终于来到了C++类和对象的最后一节，大多都是对之前学习的内容做的补充 所以加油继续冲啦！        ∧_∧::    (´･ω･`)::   /⌒ ⌒)::  /へ_＿  / /:: (＿＼＼  ﾐ)/::  ｜ `-イ::  /  ｙ  ):: /／  ／:: ／ ／:: ( く::: |＼ ヽ::: 再谈构造函数 Static成员 友元 内部类 匿名对

    2024年02月03日
    浏览(32)
  • C++好难（3）：类和对象（中篇）

    C++好难（3）：类和对象（中篇）

    类的6个默认成员函数 构造函数 析构函数 拷贝构造函数 赋值运算符重载 const成员函数 取地址及const取地址操作符重载 目录 【本章目标】 1.类的6个默认成员函数 2.构造函数 2.1概念 2.2构造函数的特性 特性一 特性二 特性三 特性四 特性五 特性六 特性七 2.3总结 3.析构函数 3.

    2024年02月03日
    浏览(34)
  • STL好难（4）：list的使用

    STL好难（4）：list的使用

    和列表很像 点击这里查看 list 的官方文档 list类似数据结构中的 链表 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且 该容器可以前后双向迭代。 2. list的底层是双向链表结构 ，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指

    2024年02月13日
    浏览(47)
  • C++好难（8）：C++中的继承

    C++好难（8）：C++中的继承

    目录 1.继承的概念及定义 🍉继承的概念 🍉 继承的定义： 🍒格式定义：  🍒继承关系和访问限定符 🍒继承基类成员访问方式的变化 2.基类和派生类对象赋值转换 3.继承中的作用域： 4.派生类的默认成员函数 5.继承与友元 6.继承与静态成员  7.复杂的菱形继承记菱形虚拟继

    2024年02月13日
    浏览(33)
  • ChatGPT3.5——AI人工智能是个什么玩意？

    ChatGPT3.5——AI人工智能是个什么玩意？

    AI，就像是一位超级聪明的机器朋友，它不会抢你的零食，但可以回答你的问题。AI可以扮演各种角色，就像是一个多面手，但不会像演员那样要求高薪。最重要的是，AI从不生气，总是耐心地听你唠叨。它会让你在学习和娱乐中倍感惊喜！ 那么，到底什么是AI？ AI，即人工智

    2024年02月14日
    浏览(47)
  • 自学web前端觉得好难，可能你遇到了这些困境

    自学web前端觉得好难，可能你遇到了这些困境

    好多人跟我说上学的时候也学过前端，毕业了想从事web前端开发的工作，但自学起来好难，快要放弃了，所以我总结了一些大家遇到的困境，希望对你会有所帮助。   目录 1.  意志是否坚定 2. 没有找到合适自己的老师 3. 为了找到工作，啥都想学  4. 学习途中遇到问题怎么办

    2024年02月02日
    浏览(98)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包