首页 > 其他分享 >【学习笔记】分块学习笔记

【学习笔记】分块学习笔记

时间：2024-02-26 21:13:59浏览次数：20  
标签：le 分块 守墓 墓碑 long 学习 笔记 风水 id

学习笔记索引

分块经常听别人提起，我也学一下。

正片

分块就是将一个数列分成很多块，然后每块单独操作，最后的结果放到原数列里。

分块的题目类型经常是区间中修改和查询。

这里，一个长度为 \(n\) 的数列最多分成 \(\sqrt n\) 个块。

先来看例题吧。

例题

P2357 守墓人

题目背景

在一个荒凉的墓地上，有一个令人尊敬的守墓人， 他看守的墓地从来没有被盗过， 所以人们很放心的把自己的先人的墓安顿在他那

守墓人能看好这片墓地是必然而不是偶然……

因为……守墓人懂风水 0.0

题目描述

他把墓地分为主要墓碑和次要墓碑， 主要墓碑只能有 \(1\) 个， 守墓人把他记为 \(1\) 号， 而次要墓碑有 \(n-1\) 个，守墓人将之编号为 \(2,3\dots n\)，所以构成了一个有 \(n\) 个墓碑的墓地。

而每个墓碑有一个初始的风水值，这些风水值决定了墓地的风水的好坏，所以守墓人需要经常来查询这些墓碑。

善于运用风水的守墓人，通过一次次逆天改命，使得自己拥有了无限寿命，没人知道他活了多久。这天，你幸运的拜访到了他，他要求你和他共同见证接下来几年他的战果，但不过他每次统计风水值之和都需要你来帮他计算，算错了他会要你命 QAQ

风水也不是不可变，除非遭遇特殊情况，已知在接下来的 \(2147483647\) 年里，会有 \(f\) 次灾难，守墓人会有几个操作：

  1. 将 \([l,r]\) 这个区间所有的墓碑的风水值增加 \(k\)。

2.将主墓碑的风水值增加 \(k\)

3.将主墓碑的风水值减少 \(k\)

4.统计 \([l,r]\) 这个区间所有的墓碑的风水值之和

5.求主墓碑的风水值

上面也说了，很多人会把先人的墓安居在这里，而且守墓人活了很多世纪→_→，墓碑的数量会多的你不敢相信= =

守墓人和善的邀请你帮他完成这些操作，要不然哪天你的旅馆爆炸了，天上下刀子.....

为了活命，还是帮他吧

输入格式

第一行，两个正整数 \(n,f\) 表示共有 \(n\) 块墓碑，并且在接下来的 $2147483647 $年里，会有 \(f\) 次世界末日

第二行，\(n\) 个正整数，表示第 \(i\) 块墓碑的风水值

接下来 \(f\) 行，每行都会有一个针对世界末日的解决方案，如题所述，标记同题

输出格式

输出会有若干行，对 \(4\) 和 \(5\) 的提问做出回答

提示

\(20\%\) 的数据满足：\(1\leq n\leq 100\)

\(50\%\) 的数据满足：\(1\leq n\leq 6000\)

\(100\%\) 的数据满足：\(1\leq n,f\leq 2 \times 10^5\)，答案不超过 64 位整数。

这道题可以用线段树，但是我用分块做。

主墓碑的修改和查询很简单，我们先看区间的修改和查询。

其实在修改的时候，我们可以发现：

1.这个区间中会有一些完整的块，我们就可以不用修改 \(a_i\)，给他打上修改的标记就行了，类似于懒标记，再将这个块中 \(a\) 的总和加上风水值 \(\times\) 区间长度，即为每一项都加上了风水值 。

2.区间中的两头也会有不完整的块，我们直接遍历这个块，暴力修改就行了，但是要记得改掉记录的这个块中 \(a\) 的总和。

再来看看查询，仍然是有两种块：

1.如果是完整块，直接将存总和的变量加上这个块中 \(a\) 的总和（有记录）就可以了。

2.如果是不完整块，需要加上目前的 \(a_i\) 和历史上标记的增加的值。

还是挺简单的吧！

CODE：

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,l,r,y,id[200010],siz,a[200010],b[200010],sum[200010];
void updata(long long l,long long r,long long y){
	long long s=id[l],t=id[r];//开头在的块和结尾在的块
	if(s==t){//全在一个块
		for(int i=l;i<=r;i++){//暴力修改
			a[i]+=y,sum[s]+=y;//sum是和，别忘了！
		}return;
	}for(int i=l;id[i]==s;i++){
		a[i]+=y,sum[s]+=y;
	}for(int i=s+1;i<t;i++){
		b[i]+=y,sum[i]+=y*siz;//打标记
	}for(int i=r;id[i]==t;i--){
		a[i]+=y,sum[t]+=y;
	}
}long long query(long long l,long long r){
	long long s=id[l],t=id[r],ret=0;
	if(s==t){
		for(int i=l;i<=r;i++){
			ret+=a[i],ret+=b[s];//加上a[i]和标记
		}return ret;
	}for(int i=l;id[i]==s;i++){
		ret+=a[i],ret+=b[s];
	}for(int i=s+1;i<t;i++){
		ret+=sum[i];//加上整个块的和
	}for(int i=r;id[i]==t;i--){
		ret+=a[i],ret+=b[t];
	}return ret;
}int main(){
	scanf("%lld%lld",&n,&m);
	siz=sqrt(n);//算长度
	for(int i=1;i<=n;i++){//分块
		scanf("%lld",&a[i]);
		id[i]=(i-1)/siz+1;
		sum[(i-1)/siz+1]+=a[i];
	}for(int i=1;i<=m;i++){
		scanf("%lld",&k);
		if(k==1){
			scanf("%lld%lld%lld",&l,&r,&y);
			updata(l,r,y);//修改
		}else if(k==2){
			scanf("%lld",&y);
			a[1]+=y,sum[1]+=y;//单点直接修改
		}else if(k==3){
			scanf("%lld",&y);
			a[1]-=y,sum[1]-=y;
		}else if(k==4){
			scanf("%lld%lld",&l,&r);
			printf("%lld\n",query(l,r));//查询
		}else{
			printf("%lld\n",a[1]+b[1]);//别忘了加上历史标记！
		}
	}return 0;
}

再看一道题。

P4145 上帝造题的七分钟 2 / 花神游历各国

题目背景

XLk 觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。

题目描述

"第一分钟，X 说，要有数列，于是便给定了一个正整数数列。

第二分钟，L 说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。

第三分钟，k 说，要能查询，于是便有了求一段数的和的操作。

第四分钟，彩虹喵说，要是 noip 难度，于是便有了数据范围。

第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。

第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过 \(64\) 位有符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。"

——《上帝造题的七分钟·第二部》

所以这个神圣的任务就交给你了。

输入格式

第一行一个整数 \(n\)，代表数列中数的个数。

第二行 \(n\) 个正整数，表示初始状态下数列中的数。

第三行一个整数 \(m\)，表示有 \(m\) 次操作。

接下来 \(m\) 行每行三个整数 k l r。

  • \(k=0\) 表示给 \([l,r]\) 中的每个数开平方（下取整）。

  • \(k=1\) 表示询问 \([l,r]\) 中各个数的和。

数据中有可能 \(l>r\)，所以遇到这种情况请交换 \(l\) 和 \(r\)。

输出格式

对于询问操作，每行输出一个回答。

提示

对于 \(30\%\) 的数据，\(1\le n,m\le 10^3\)，数列中的数不超过 \(32767\)。

对于 \(100\%\) 的数据，\(1\le n,m\le 10^5\)，\(1\le l,r\le n\)，数列中的数大于 \(0\)，且不超过 \(10^{12}\)。

这题也是分块，但是要有一个小优化。

我们可以发现，\(\sqrt 1\) 就是 \(1\)，而且一个数开根号很快就会变为 \(1\)，所以，我们可以判断是否全是 \(1\)，如果是，修改就不用了，查询直接加上长度就行了。

那么如何判断是否全是 \(1\) 呢？直接判断它的最大值是不是 \(1\) 就可以了。

CODE：

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,l,r,id[100010],siz,a[100010],b[100010],sum[100010];
void updata(long long l,long long r){
	long long s=id[l],t=id[r];
	if(s==t){
		sum[s]=0,b[s]=0;
		for(int i=l;i<=r;i++){
			a[i]=(long long)sqrt(a[i]);//开根
		}for(int i=siz*(s-1)+1;i<=siz*s;i++){
			b[s]=max(b[s],a[i]);//更新
			sum[s]+=a[i];
		}return;
	}sum[s]=0,b[s]=0;
	for(int i=l;id[i]==s;i++){
		a[i]=(long long)sqrt(a[i]);
	}for(int i=siz*(s-1)+1;i<=siz*s;i++){
		b[s]=max(b[s],a[i]);
		sum[s]+=a[i];
	}for(int i=s+1;i<t;i++){
		if(b[i]!=1){
			sum[i]=0,b[i]=0;
			for(int j=siz*(i-1)+1;j<=siz*i;j++){//这里没办法，只能暴力
				a[j]=(long long)sqrt(a[j]);
			}for(int j=siz*(i-1)+1;j<=siz*i;j++){
				sum[i]+=a[j];
				b[i]=max(b[i],a[j]);
			}
		}
	}sum[t]=0,b[t]=0;
	for(int i=r;id[i]==t;i--){
		a[i]=(long long)sqrt(a[i]);
	}for(int i=siz*(t-1)+1;i<=siz*t;i++){
		b[t]=max(b[t],a[i]);
		sum[t]+=a[i];
	}
}long long query(long long l,long long r){
	long long s=id[l],t=id[r],ret=0;
	if(s==t){
		for(int i=l;i<=r;i++){
			ret+=a[i];
		}return ret;
	}for(int i=l;id[i]==s;i++){
		ret+=a[i];
	}for(int i=s+1;i<t;i++){
		if(b[i]!=1){
			ret+=sum[i];
		}else{
			ret+=siz;//直接加长度
		}
	}for(int i=r;id[i]==t;i--){
		ret+=a[i];
	}return ret;
}int main(){
	scanf("%lld",&n);
	siz=sqrt(n);//算长度
	for(int i=1;i<=n;i++){//分块
		scanf("%lld",&a[i]);
		id[i]=(i-1)/siz+1;
		b[(i-1)/siz+1]=max(b[(i-1)/siz+1],a[i]);
		sum[(i-1)/siz+1]+=a[i];
	}scanf("%lld",&m);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&k,&l,&r);
		if(k==0){
			if(l>r){//l>r是存在的！！
				swap(l,r);
			}updata(l,r);
		}else{
			if(l>r){
				swap(l,r);
			}printf("%lld\n",query(l,r));
		}
	}return 0;
}

P3870 [TJOI2009] 开关

题目描述

现有 \(n\) 盏灯排成一排，从左到右依次编号为：\(1\)，\(2\)，……，\(n\)。然后依次执行 \(m\) 项操作。

操作分为两种：

  1. 指定一个区间 \([a,b]\)，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开）；
  2. 指定一个区间 \([a,b]\)，要求你输出这个区间内有多少盏灯是打开的。

灯在初始时都是关着的。

输入格式

第一行有两个整数 \(n\) 和 \(m\)，分别表示灯的数目和操作的数目。

接下来有 \(m\) 行，每行有三个整数，依次为：\(c\)、\(a\)、\(b\)。其中 \(c\) 表示操作的种类。

  • 当 \(c\) 的值为 \(0\) 时，表示是第一种操作。
  • 当 \(c\) 的值为 \(1\) 时，表示是第二种操作。

\(a\) 和 \(b\) 则分别表示了操作区间的左右边界。

输出格式

每当遇到第二种操作时，输出一行，包含一个整数，表示此时在查询的区间中打开的灯的数目。

提示

对于全部的测试点，保证 \(2\le n\le 10^5\)，\(1\le m\le 10^5\)，\(1\le a,b\le n\)，\(c\in\{0,1\}\)。

在反转的时候，整块就直接记录每一块 \(0\) 的数量和 \(1\) 的数量，后面交换就可以了，但是 \(a_i\) 没变，于是要将反转的次数标记，因为反转两次就是没反转，那标记时异或 \(1\) 就可以了，然后散块要先将标记给下传然后清空，再暴力。

在查询的时候，散块一定要先将标记下传、清空，才可以再暴力，整块直接加上前面记录的 \(1\) 的数量就行了。

CODE：

#include<bits/stdc++.h>
using namespace std;
int n,m,k,l,r,id[100010],siz,a[100010],cnt[100010],cnt0[100010],tmp[200010];
void updata(int l,int r){
	int s=id[l],t=id[r];
	if(s==t){
		cnt[s]=0,cnt0[s]=0;
		if(tmp[s]==1){
			tmp[s]=0;
			for(int i=siz*(s-1)+1;i<=min(n,siz*s);i++){//下传标记
				if(a[i]==0){
					a[i]=1;
				}else if(a[i]==1){
					a[i]=0;
				}	
			}	
		}for(int i=l;i<=r;i++){
			if(a[i]==0){
				a[i]=1;
			}else if(a[i]==1){
				a[i]=0;
			}
		}for(int i=siz*(s-1)+1;i<=min(n,siz*s);i++){
			if(a[i]==1){
				cnt[s]++;
			}else{
				cnt0[s]++;
			}
		}return;
	}cnt[s]=0,cnt0[s]=0;
	if(tmp[s]==1){
		tmp[s]=0;
		for(int i=siz*(s-1)+1;i<=min(n,siz*s);i++){
			if(a[i]==0){
				a[i]=1;
			}else if(a[i]==1){
				a[i]=0;
			}	
		}	
	}for(int i=l;id[i]==s;i++){
		if(a[i]==0){
			a[i]=1;
		}else if(a[i]==1){
			a[i]=0;
		}
	}for(int i=siz*(s-1)+1;i<=min(n,siz*s);i++){
		if(a[i]==1){
			cnt[s]++;
		}else{
			cnt0[s]++;
		}
	}for(int i=s+1;i<t;i++){
		swap(cnt[i],cnt0[i]);//交换和标记
		tmp[i]++;
		if(tmp[i]==2){
			tmp[i]=0;
		}
	}cnt[t]=0,cnt0[t]=0;
	if(tmp[t]==1){
		tmp[t]=0;
		for(int i=siz*(t-1)+1;i<=min(n,siz*t);i++){
			if(a[i]==0){
				a[i]=1;
			}else if(a[i]==1){
				a[i]=0;
			}	
		}	
	}for(int i=r;id[i]==t;i--){
		if(a[i]==0){
			a[i]=1;
		}else if(a[i]==1){
			a[i]=0;
		}
	}for(int i=siz*(t-1)+1;i<=min(n,siz*t);i++){
		if(a[i]==1){
			cnt[t]++;
		}else{
			cnt0[t]++;
		}
	}
}int query(int l,int r){
	int s=id[l],t=id[r],ret=0;
	if(s==t){
		if(tmp[s]==1){
			tmp[s]=0;
			for(int i=siz*(s-1)+1;i<=min(n,siz*s);i++){//下传标记
				if(a[i]==0){
					a[i]=1;
				}else if(a[i]==1){
					a[i]=0;
				}	
			}	
		}for(int i=l;i<=r;i++){
			if(a[i]==1){
				ret++;
			}
		}return ret;
	}if(tmp[s]==1){
		tmp[s]=0;
		for(int i=siz*(s-1)+1;i<=min(n,siz*s);i++){
			if(a[i]==0){
				a[i]=1;
			}else if(a[i]==1){
				a[i]=0;	
			}	
		}	
	}for(int i=l;id[i]==s;i++){
		if(a[i]==1){
			ret++;
		}
	}for(int i=s+1;i<t;i++){
		ret+=cnt[i];
	}if(tmp[t]==1){
		tmp[t]=0;
		for(int i=siz*(t-1)+1;i<=min(n,siz*t);i++){
			if(a[i]==0){
				a[i]=1;
			}else if(a[i]==1){
				a[i]=0;
			}	
		}
	}for(int i=r;id[i]==t;i--){
		if(a[i]==1){
			ret++;
		}
	}return ret;
}int main(){
	scanf("%d",&n);
	siz=sqrt(n);
	for(int i=1;i<=n;i++){
		id[i]=(i-1)/siz+1;
		cnt0[(i-1)/siz+1]++;//0的数量
	}scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&k,&l,&r);
		if(k==0){
			if(l>r){
				swap(l,r);
			}updata(l,r);
		}else{
			if(l>r){
				swap(l,r);
			}printf("%d\n",query(l,r));
		}
	}return 0;
}

咕咕咕

标签：le,分块,守墓,墓碑,long,学习,笔记,风水,id
From： https://www.cnblogs.com/scyqwq/p/18035185

相关文章

  • 冯梓轩学习目标
    目标短期目标：把平时做题的较好状态带到考试当中，不粗心大意，不犯低级错误（例如读错题）；合理分配时间，不死磕一道题能够独立的尽量推完作业表能够独立完成大部分蓝及一下题目和一些中、下位紫学完并熟练掌握提高级知识多打在线比赛（如Atcoder,Codeforces），积累做题经验（特......
  • 学习环境部署
     学习自动化或者jmeter没练习的接口？来，简单快速部署一个学习环境。 1、网盘下载、配置虚拟机https://www.cnblogs.com/uncleyong/p/15777706.html（资料在文末评论区）虚拟机配置、使用相关：https://www.cnblogs.com/uncleyong/p/17874484.html 2、linux下安装jdkhttps://www......
  • 【Django开发】0到1开发美多shop项目：用户登录模块开发。全md文档笔记（附代码 文档）
    本系列文章md笔记（已分享）主要讨论django商城项目相关知识。项目利用Django框架开发一套前后端不分离的商城项目（4.0版本）含代码和文档。功能包括前后端不分离，方便SEO。采用Django+Jinja2模板引擎+Vue.js实现前后端逻辑，Nginx服务器（反向代理）Nginx服务器（静态首页、商品详情页、uwsg......
  • Vue学习笔记16--监视属性watch + 深度监视 + 监视简写
    监视属性watch示例一：<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>计算属性</title&......
  • 标记永久化【学习笔记】
    众所周知，线段树最重要的操作之一便是标记下传。但在一些情况下，我们不能进行标记的下传（可能是正确性的问题、或者是复杂度的问题）正确性问题：比如带修的可持久化线段树中，如果标记下传，会影响之前的版本。复杂度问题：比如树套树中，push_up操作的复杂度会直接炸掉。因此，就产生了标记永......
  • #分块，二分#洛谷 5356 [Ynoi2017] 由乃打扑克
    题目支持区间加和区间查询第\(k\)小分析分块之后给每个整块排序，这样修改的时候整块打标记，散块直接分开把需要加的部分暴力加之后归并，就是\(O(\sqrt{n})\)的查询的话，如果只有散块直接归并出结果，否则二分答案，加上小块合并成的整块，相当于是整体二分，就是\(O(\sqrt{n}\log{a_......
  • 【李宏毅机器学习2021】(二）Tips for training
    这一节主要讲解机器学习、类神经网络训练不起来怎么办？讲解一些训练的tips。先来回顾下机器学习的步骤：接下来将介绍在机器学习过程中，遇到问题时如何判断原因并解决：在训练数据上Loss值很大ModelBias在训练数据上Loss值很大，有可能是发生了Model问题。问题原因：模型太......
  • 【李宏毅机器学习2021】（一）引入机器学习和深度学习
    引入机器学习MachineLearning概括来说就是LookingforFunction，即让机器具备找一个函数的能力这些函数显然非常复杂，要依靠机器自动找出该函数。随着要找的函数不同，机器学习有不同的类别：Regression，回归：函数输出的是数值。Classification，分类：函数从给定选项（类别）中选择一个......
  • 古人云：时间线段树 爽！时间线段树学习笔记。
    嘛，这个东西虽然叫时间线段树，但是和线段树好像关系并不大，只是借用了一下线段树的结构。算法介绍这个算法是用来解决这类问题的：每个操作只在一段时间内生效，然后询问某个时间点所有操作的贡献。于是我们考虑离线，对整个时间序列建一个线段树，每次操作相当于是在这个线段树上进行了区......
  • 容斥原理学习笔记
    前言可能需要一点二项式定理和二项式反演的相关知识。有许多不足还请指出。公式经典容斥\(A_1,A_2,\cdots,A_n\)均为有限集，\(A_i\subseteqS\)，则\[\left\vert\bigcup\limits_{i=1}^nA_i\right\vert=\sum\limits_{k=1}^n(-1)^{k-1}\sum\limits_{1\lei_1<i_2<\cdots<i_k\le......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99