本题解需要掌握dsu on tree和长链剖的相关知识。 具体可以见我的博客 dsu on tree：https://blog.nowcoder.net/n/a84c24c37daf450d8bf9db81607c8f98 长链剖分：https://blog.nowcoder.net/n/5eaebd22f5f846838c637bc337cc1ee9 一开始就读了个假题，读成了。“统计每一层的节点数目，然后输出和为奇数的层共有几层”这个题意，然后样例都过不去一脸懵逼。 题意：给你一棵树，重复做以下动作直到树上所有点的权值都为0 1、对于所有权值大于1的节点...

答案等于，Bsize表示连通块尺寸，这个并不是难点，难点在于连通块大小怎么求。 这个题，第一眼：水题啊，直接并查集或者dfs瞎搞搞。 然后惨遭数据范围毒打。（毒瘤） 那...首先dfs先pass，这个怎么剪枝好像也不行，离散化压缩再dfs感觉也写不太动。 但是并查集是个好思路。 首先根据数据范围，只要地图足够大，障碍物的总数目有有限，障碍物就放的相当稀疏，那我可以提前把一些比较大的连通块并起来。 idea1 如图，'.'表示普通的格子，'X'表示障碍物。 我可以按照行进行扫描，然后把所有连在一起的.合并成一个长长的“面条”，这样子再把行间相邻的“面条”给合并起来不就好了？ （....

第一眼：bfs傻X题，然后发现它能跳。 然后嘴巴BB了一句，起点bfs，终点bfs，单调栈+单调栈合并的傻X题。 （...几小时后...） MD这个题怎么这么麻烦。 好吧，这个题确实是没什么可以说的地方，没思路的话可能是不知道“单调队列处理固定划窗极值”这个套路。 单调队列处理固定划窗极值 它是这么个套路啊，说现在有一个长度大小为n的数组，数组中有一些整数，请你求出所有长度大小为k的子区间的极值。 还是给个例子比较好说明，假设n=9,k=3，a[]={5,6,7,8,9,4,1,1,1} 跟着划窗取子区间，取到的第一个子区间是{5,6,7}这个子区间，该子区间的最大值为7。 那...

本题解需要掌握dsu on tree和长链剖的相关知识。 具体可以见我的博客 dsu on tree：https://blog.nowcoder.net/n/a84c24c37daf450d8bf9db81607c8f98 长链剖分：https://blog.nowcoder.net/n/5eaebd22f5f846838c637bc337cc1ee9 一开始就读了个假题，读成了。“统计每一层的节点数目，然后输出和为奇数的层共有几层”这个题意，然后样例都过不去一脸懵逼。 题意：给你一棵树，重复做以下动作直到树上所有点的权值都为0 1、对于所有权值大于1的节点，权值减少1。当权值...

长链剖分可以视作是dsu on tree算法的一个特例，在学习之前，需要掌握树链剖分以及dsu on tree。 dsu on tree:https://blog.nowcoder.net/n/a84c24c37daf450d8bf9db81607c8f98 dsu on tree用于解决： 子树类的静态查询类问题。 基础复杂度为。 长链剖用于解决： 子树类与深度相关可合并的静态查询类问题。 基础复杂度为。 长链剖应用的场景必须是与子树深度相关的，从这点上来讲他只是dsu on tree的特例。 当然，它的复杂度是比dsu on tree要...

dsu的意思是并查集，但是dsu on tree这个算法和并查集的关系也就剩一个启发式合并了。 学习这个算法的切入点还真不在启发式合并，关于启发式合并的问题实际上是最后再考虑它为什么叫启发式合并。 我们选什么作为切入点呢，选莫队算法，如果你不懂莫队也没关系，这里只是说这两个算法在应用的场景上面有共通点，只不过一个应用于子树，一个应用于数组区间。 莫队 我们从最简单的区间问题“子区间的静态求和问题”开始讨论好了。 假定现在有一个数组a，数组里面有若干个元素，然后你已知这段区间的区间和，假设区间与区间有大面积重合，重合率达到90%。问你如何在已知区间和的情况下...

写在题解前的话 按照惯例，先背锅。 这次比赛没有Hello World或者A+b problem这样的“签到题”。 也没有能直接贴过来的那种，能够AC的话都不错。 爆0的话也不用担心，后面的场都比我这场简单（大概）。 然后锅嘛... B题spj写锅了，可以判题但是不能统计罚时（WA了算内部错误没有罚时） 题目描述上面有点小锅。 这场比赛我每个题都写了很多不同的程序，会公开给大家看一下（选手可能只会被题目恶心一次，但是出题人可能要被自己出的题恶心死...做个10遍8遍的，还得出数据）。 A、牛牛的DRB迷宫I 这个题是所有题里面最简单的题...

树状数组 树状数组常用于维护前缀信息，如前缀和、前缀乘积等等。 最常见的如给你一个长度为n的数组，单点修改，查询区间的和。 首先是想一下为什么不能用前缀和数组强行搞 先看一下前缀和 黄色和蓝色部分合起来表示前缀和覆盖的区间 黄色表示前缀和信息储存的位置 如果要修改a[5]还好…只有s[5]会受到影响，万一要修改a[1]或者a[2]的话就要修改s[1],s[2],s[3],s[4],s[5]，也就是全都要改。 这样的话时间复杂度就上天了。 用前缀和处理带修改的区间求和问题 操作的时间复杂度： 1、对一段区间求和O...

高维前缀和(SOSDP) 高维前缀和，又叫SOSDP，Sum over Subsets dynamic programming，它一般是用来解决子集类的求和问题（虽然也可以解决高维空间的求和问题，但是时空往往不允许）。 高维度下求前缀和时，时间复杂度的瓶颈 先看一下前缀和的式子 一维： 二维： 三维： .... 我们发现这步容斥操作在高纬度下不能被视为O(1)，它与维度k成幂函数的关系。 高维前缀和的时间复杂度为O(|高维空间容量|*)，在高维空间容量不大，但是维度数很高的时候，瓶颈在于维度数k。 想办法进行优化。 另一种求前缀...

树状数组维护前缀和的前缀和 这个东西的用途其实不太大，复杂的区间信息还是靠线段树，而且这个操作线段树能直接干了。 主要应用在以下两个方面： 1、区间加数，区间求和问题。 2、区间加等差数列，单点求值问题。 ①可以用线段树直接干，②可以维护差分数组转化为①。 虽然在一维中是个几乎无用的技巧，但是二维的矩形区间加，求矩形和类的问题，四分树以及树套树又不好写，所以可以用二维的树状数组通过这种技巧实现。 为了处理数组越位以及树状数组中0无法被查询的问题，下标从1开始计算。 前缀和的前缀和 设表示数组a的前缀和，表示的前缀和，则有 那...

二维前缀和与差分 对于一个二维数组a定义数组为数组a的前缀和数组，可以理解为一个左上矩阵的矩阵和 //为了避免数组越位，下标从1开始 for(int i=1;i<=n;++i) {     for(int j=1;j<=m;++j)//可以只用一个数组，这里为了看的清楚区分了s与a     {         s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i...

前缀和与差分 对于一个数组a定义数组为a数组的前缀和数组。 //为了避免数组越位，下标从1开始用 for(int i=1;i<=n;++i) {     s[i]=s[i-1]+a[i]; } 定义数组为a数组的差分数组。 //为了避免数组越位，下标从1开始用 for(int i=n;i;--i) //倒着for的可以不借助两个数组，这里用d和a是为了看着清楚，实际可以用一个数组储存。 {     d[i]=a[i]-a[i-1]; }...

数位DP 所谓数位DP，就是把一个数按照k进制数的每一个位展开，在把每一位的信息作为状态来推出答案。 比如：12345这个数在十进制下可拆为1、2、3、4、5，个位可以推十位，十位可以推百位，以此类推。 推状态的方法有很多，一般来说第一反应就是像普通dp一样从前往后推，但是由于思维难度较高而且写起来难度较大，所以推荐递归写法，也就是记忆话搜索的写法。 以HDU2089 不要62为例。 统计l,r区间内不含62,4的数字个数。 l~r区间符合条件的数字没有普遍的规律，状态数目过多不好做DP。但是1~x一段连续的区间在枚举数字时有大量重复状出现，利用记忆化搜索做DP。 ...

静态维护区间加等差数列的求和问题 维护一个数组，先进行m次操作，然后查询每个位置的值，每个操作给定四个参数l,r,a,k表示从l到r依次加上一个首项为a，公差为k的等差数列。 维护数组，表示原数组的二阶差分。 修改操作 void add(int l,int r,int a,int k) {     d2[l]+=a;     d2[l+1]+=k-a;     d2[r+1]-=(r-l+1)*k+a; ...