写在最前发现文章被吃掉了好多,先重写一篇分块吧
众所周知某知名大佬 (DeepSeek) 说过这么一句话:
当你不会写线段树的时候,分块是你的救世主;当你学会线段树之后,分块是你的白月光。
所以我是分块的勾!
核心思想分块的核心思想其实很简单:将序列分成若干块,对整块进行整体处理,对零散的部分进行暴力处理。
那么具体分多少块呢,不妨分析一下复杂度:
假设我们序列长为 $n$,块长为 $m$
查询操作:
对于整块,我们需要枚举每一个块,复杂度即为 $O(\frac{n}{m})$
对于零散的部分,我们暴力枚举,因为块长为 $m$,所以复杂度即为 $O(m)$
修改同理
那么整体最坏复杂度即为 $O(\frac{n}{m}+m)$
根据均值不等式 $\frac{a+b}{2} \ge \sqrt{ab}$ 可知,当 $\frac{n}{m}=m$ 即 $m = \sqrt(n)$ 时,复杂度最优
故当块长为 $\sqrt{m}$ 时复杂度最优,为 $O(\sqrt(n))$
不难发现不如线段树(?
那我们为什么要用粪块呢?
虽然分块常被称为”优雅的暴力” ...
写在最前我承认这个封面的线段树有点过于抽象,但是真的没有别的办法乐。
先引用一个大佬说的一句话:
什么是线段树?如果你在考提高组前一天还在问这个问题,那么你会与一等奖失之交臂;如果你还在冲击普及组一等奖,那么这篇博客会浪费你人生中宝贵的5~20分钟。
显而易见,线段树是一个 OIer 从萌新过渡到正式选手的标志性算法。
然而事实上,对于一个正式的 OIer 选手,线段树更应该是一个工具,所以……
线段树是世界上最好的数据结构!!!(bushi
线段树可以 $O(\log n)$ 的实现区间和、区间乘、区间最值、区间修改等操作,在很多题中都可以以略逊于正解的解法过掉。
核心思想线段树的核心思想是 分治。它将一个区间分成若干个子区间,每个节点代表一个区间,并通过递归的方式维护区间的信息。
区间划分:对于一个区间 $[l, r]$,我们将其分成两个子区间 $[l, mid]$ 和 $[mid+1, r]$,其中 $mid = \lfloor \frac{l+r}{2} \rfloor$。
递归维护:通过递归的方式,逐步将区间划分到最小单位(即叶子节点),并在回溯时合并子区间的 ...
写在最前树状数组算是我目前学过最优雅好写的数据结构了。
树状数组也被称为二进制索引树(Binary Indexed Tree,BIT),是一种高效的数据结构,它可以实现 $O(\log n)$ 的单点修改和前缀和查询。
核心思想当我们想实现单点修改和区间查询时,肯定会有人想到用一个数组来维护若干个小区间的和,使得修改和查询的复杂度都不会那么高。
树状数组便是巧妙的运用了二进制来实现这一想法。
现在我们存储每一个位置前面 lowbit 位的和,也就是是说 $c_i=\sum_{j=i-lowbit(i)+1}^ia[j]$,比如 $i=6$,那么我们可以先将 6 转化为二进制 $(0110)_2$,显然 $c[6]=a[5]+a[6]$。
实现区间查询这里偷借一下老师的图((((
不难发现长得确实很像树如果现在要求前 $i$ 项的和,那么就可以通过每次减去 $lowbit(i)$ 得到的 $c_i$ 求和,具体来说就是 $sum[i]=c[i]+sum[i-lowbit[i]]$。
还是拿 6 举例,先化成二进制 $(0110)_2$。 ...
前言如果您不愿意展示自己的代码,可以申请撤下您的代码。
如果上述代码中存在个人信息泄露情况,请立即联系作者。
代码来源:浙江省 NOIP 2023 考生代码
正文统计共 $788$ 人,$3404$ 份文件,平均每入约 $4.319797$ 份文件
其中:
114514 出现 $114$ 次(臭
1919810 出现 $26$ 次
AC 出现 $26$ 次
ccf 出现 $45$ 次
noi 出现 $35$ 次
csp 出现 $11$ 次
orz 出现 $47$ 次
qwq 出现 $212$ 次
rp 出现 $160$ 次
rp++ 出现 $27$ 次
system 出现 $243$ 次
define 出现 $4315$ 次
rand 出现 $400$ 次
$57$ 人注释了文件操作
$63$ 人写了对拍
空间第一:ZJ-0184本场重量级
共 ${44.9 MB}$
一人霸占 ${\frac{9}{10}}$死因:玄学文件
一、白给型ZJ-0595:
12345678910#include<bits/stdc++.h>using namespace std;int n ...