一类区间分治技巧

对于一类区间询问问题,如果可以离线并且可以快速合并区间信息那么就有一个非常实用的分治方法。首先我们对总区间分治下去,当前区间[l , r]中点为mid,那么我们将所有的询问分成三类,一类包括mid这个点,一类完全在左侧,一类完全在右侧,我们只要在当前这层解决第一类的所有询问,后两类分治下去即可。怎么快速的求呢?方法也非常简单,因为信息可以快速合并,那么我们以mid为界,往前处理出所有后缀信息,往后处理出所有前缀信息,对于一个跨过mid的询问,拿两部分拼一下就算出答案了!

比在线算法优秀的地方在于可以优雅的去掉询问数所乘的log。

练习题目

1.2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest J. Subsequence Sum Queries

考虑背包dp,如果用普通的线段树,时间复杂度\(O((n+q)m^2logn)\),因为拆成logn个区间,要完全合并两个背包log次,合并一次(循环卷积)复杂度是\(O(m^2)\),必T无疑。用优秀的分治就可以降到\(O(m(nlogn+q))\)。

2.2018 Multi-University Training Contest 3 Problem J. Rectangle Radar Scanner 

对x轴分治,对于y用线段树维护一下就好了

时间复杂度\(O(nlog^2n+mlogn)\)

 

高维前缀和

问题的引入

一个\(n \times m\)二维矩阵\(A\)的前缀和\(S\),一般来说定义为\(S_{x,y}=\sum_{i=1}^{x}\sum_{j=1}^{y}A_{i,j}\)。

代码常见的写法就是用容斥加加减减:

这是二维的情况,如果是三维或者是更高的k维,不难发现复杂度有一个\(2^k\),指数爆炸了。

然而,用高维前缀和的技巧,就可以有效的将时间复杂度降下来。具体的思路是一维一维的求和。比如还是刚才二维的例子,为方便叙述,想象矩阵左上角是\((1,1)\),我们先对每行分别从左到右累加,即对每行求一维前缀和,再对每列从上到下累加,还是相同的过程,这样求出的结果就是二维前缀和了。也可以从定义前缀和的式子入手考虑,每个求和号就代表一个维度,我们的计算过程就相当于一个求和号一个求和号的算,比较简单。

高维前缀和代码,简洁的一匹:

子集和变换

高维前缀和在二进制数上的应用就是做子集和变换。比如有一些小于\(2^{20}\)正整数给一个数x,我要统计所有满足\(x\&y=y\)的数y有多少个,这里的and就是二进制与。这里其实还是高维前缀和,可以把每一个数看成20维超立方体的其中一个格子,满足上述式子的x和y的关系就是,每一个维度下y对应的值都要小于等于x对应的值(虽然每个维度只有两种值,0或1)这样就是相同的问题了,于是我们不仅可以维护一个子集的信息,还可以维护超集的信息,维护的内容也不只限于求和,还可以求最值等等。

求超集和:

第一层循环枚举维度,第二层枚举所有元素,注意第二层循环正序或者倒序都是一样的,因为每个维度大小只有2,即0或1,做的就是把“1”加到“0”上。

练习题目

1.SPOJ Time Limit Exceeded

简单的递推一下就是记\(dp_{i,j}\)表示考虑前i个数,第i个数为j的方案数,转移方程很容易\(dp_{i,j}=\sum_{k=0}^{2^m-1}dp_{i-1,k}[j\&k=0]\),并且如果j是\(c_i\)的倍数,那么\(dp_{i,j}=0\)。

然而朴素的转移是\(O(n(2^m)^2)\),显然会TLE。转化一下\(j\&k=0\)等价于\(j\&(~k)=(~k)\),那么我们把上一次的dp值状态取反,然后求超集和就ok了,时间复杂度\(O(n^{2}2^{m})\)。

2.codeforces 449D – Jzzhu and Numbers

求and起来为0的子集的个数。

先用高维前缀和算出\(dp_S\)表示状态包含S的数的个数,然后令\(2^{dp_S}-1\)就是and起来包含S的子集的个数,然后再高维差分回去,就能求出答案了。

3.hihocoder 1496 寻找最大值

求\(a_i\times a_j \times (a_i \& a_j)\)的最大值,枚举&值,前面就选超集中的最大值和次大值,用高维前缀和处理出来。

4.2016 Multi-University Training Contest 4 Bonds

给一个不超过20个点的无向连通图,无重边无自环,求每条边被多少个极小割边集包括。

显然能观察到极小割只会将图分成两个连通块,那么我们先用点的连通性作为状态bfs一下,得到所有可能的分法。之后如果暴力统计的话复杂度就是\(O(n^{2}2^{n})\),我们计算反面,每条边极小割边集出出现的次数等于极小割总数减去这条边连接的两点在同一连通块的情况,然后就可以高维前缀和了,\(O(n2^{n})\)。

5.2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest F.GCD

先从n个数中随机一个数,然后就有大于二分之一的概率选到了最优解中的一个数,那么枚举这个数的所有约数,用至少是n-k个数的约数的数更新答案,重复多做几次,降低随不到的概率。关键是怎么不暴力的做后面说的这个事情。首先,一个\(10^{18}\)范围内的数的约数个数不会很多,大概几倍的\(10^{6}\)就够,这个可以等完写个搜索验证一下。然后将随到数分解质因数,每个不同的质因数看成一个维度,然后求个高维后缀和,就可以了。

 

线段树优化凸壳

Lena and Queries

题目链接:http://codeforces.com/contest/678/problem/F

三种操作,1.插入一个点(x,y) 2.删除之前第i个操作插入的点 3.给一个q,询问在已有点中qx+y最大是多少

如果没有删除完全可以cdq分治然后在上凸壳上三分。有删除操作的话因为贡献不独立,所以不能cdq分治。

但是可以用上一次线段树优化建图一样的技巧,按时间来看,因为每个点的存在是一段区间,那么就可以用线段树拆成log个区间,然后把点“打”在上面(加进vector),最后对于线段树上每个区间,做凸壳然后询问就行了。每个询问会被问log次,所以时间复杂度粗略算有\(O(nlog^2n)\)。

 

 

2018 CCPC网络赛 GuGu Convolution

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6442

定义序列\(\{a\}=(a_0,a_1,a_2,\dots)\)

它的指数型生成函数为\(g_{\{a\}}(x)=\sum_{i=0}^{\infty}\frac{a_i}{i!}x^i\)

设\(c\)是一个常数

定义序列\(\{u_c\}=(c^0,c^1,c^2,\dots)\),\(\{e_c\}=(0,c^1,0,c^3,0,c^5,\dots)\)

定义两个生成函数\(g_{\{a\}},g_{\{b\}}\)的卷积\(G(x)=(g_{\{a\}}*g_{\{b\}})(x)=\sum_{n=0}^{\infty}(\sum_{i+j=n}\frac{a_i}{i!}\frac{b_j}{j!})x^n\)(原题面省略了阶乘,可能是写错了?)

现在给三个正整数\(n,A,B\),求\(G(x)=g_{u_A}*g_{e_{\sqrt{B}}}\)的\(x^n\)前的系数乘上\(n!\)后的结果

赛中走了很多弯路,思路大概是这样的

首先用泰勒展开,可以看出

\(g_{u_A}=e^{Ax},g_{e_B}=\frac{1}{2}(e^{\sqrt{B}x}-e^{-\sqrt{B}x})\)

所以\(G(x)=g_{u_A}*g_{e_{\sqrt{B}}}=\frac{1}{2}(e^{(A+\sqrt{B})x}-e^{(A-\sqrt{B})x})\)

第n项系数为\(\frac{(A+\sqrt{B})^n-(A-\sqrt{B})^n}{2}\)

类似斐波那契数列也可以强行求出线性递推的式子然后矩阵快速幂,就是推得比较难受罢了==

更快的方法

不用泰勒展开,直接用二项式定理类似的凑一下就可以得到第n项系数的式子,最后也不用推递推式,答案就是\((A+\sqrt{B})^n=x+y\sqrt{B}\)中去掉整数项x,直接快速幂就做完了。

赛中代码:

 

线段树优化建图

有一类经典的问题,之前见过很多次了,好像某一场区域赛的热身赛里就出过:一维数轴上有n个炸弹,\(x_i,r_i\)分别表示第i个炸弹的位置和引爆半径,即如果引爆炸弹i,那么位置在\([x_i-r_i,x_i+r_i]\)范围内的炸弹都会爆炸,并且引发连锁反应。然后比如询问最少引爆几个炸弹才能全部炸完。

首先一个建图思路是如果i能引爆j,那么i向j连一条边,做tarjan求强连通分量就可以知道很多信息了。但是这样暴力连边是\(O(n^2)\)的,需要优化。一个显然的观察是,一个点i的引爆范围是一段区间(这句是废话),所以是和一个区间的点连边,那么我们把炸弹按位置排序后,1到n编好号,建线段树,线段树每个点向左右儿子分别连边。如果i要向区间(l,r)所有点连边的话,就在线段树中将区间(l,r)分解成\(O(logn)\)条线段,这样就转化成了向对应的线段树中的一些点连边,总的边数就是\(O(nlogn)\)。

来看两道具体的题目:

bzoj 5017 [Snoi2017]炸弹

询问如果把第 i 个炸弹引爆,将引爆多少个炸弹。

线段树优化建图,然后tarjan,答案是从i所在的SCC出发,能走到的SCC含有的原炸弹数之和。因为对于每个i都要询问,所以这里不能暴力,一个方法是在这个DAG的反图上拓扑序dp一下。

 

Petrozavodsk Winter-2018. Carnegie Mellon U Contest A Mines

现在每个炸弹多了一个初始的引爆费用,因为连锁发生的爆炸是免费的。有q次修改,每次修改一个炸弹的费用,对于每次修改都要查询当前要引爆所有炸弹的最小花费。

前面的操作都一样,首先一个显然的想法是只要引爆DAG中所有入度为0的SCC里的费用最小的炸弹。然后有个致命的问题是,入度为0的SCC可能不含有原1到n号点,所以需要做拓扑排序删掉没用的点,之后对于每次询问用set维护即可。

 

NOIP 2014

题目链接:https://vijos.org/p/category/2014

D1T1 生活大爆炸版 石头剪刀布

没想到noip还会出纯模拟

D1T2 联合权值 

dfs一下就统计出来了

D1T3  飞扬的小鸟

这个dp有、东西,日常不会dp

 

D2T1 无线网络发射器选址  

记前缀和,然后枚举

D2T2 寻找道路

先在反图上从终点bfs,求出哪些点能到终点,然后从起点正着按题意bfs就好了

D2T3 解方程

直接解肯定没办法,只能枚举答案,然后随机素数取模验证。

 

 

NOIP 2013

最近突然想回顾一下历年noip题目,就开个新坑吧,题解就从略了

题目链接 https://vijos.org/p/category/2013

D1T1 转圈游戏

公式就\((x+m10^k)\%n\),现在一眼的事情当时想了很久orz

D1T2 火柴排队

首先肯定是小对小,大对大,才能使那个式子最小,这一点可以交换一下然后做差说明。并且题目保证了高度互不相同,也就是给了两个排列,问最少交换相邻元素多少次,才能使两个排列一样,再转化一步,假设第一个排列就是1,2,3,…n,问第二个排列最少交换相邻元素几次才能变成1,2,3,…n,这就是逆序对的定义了。

不知道如果不保证高度互不相同该怎么做orz

当时这个题爆零了,一点也不会QAQ

 

D1T3 货车运输

这个不难看出是最大生成树上倍增求路径边权最小值。要注意的是可能是一个森林,当时蠢的用tarjan判连通性了,强行增加码量。还好在赛前刚给别人讲过倍增,这题满分了。

D2T1 积木大赛

可能太简单,这题没什么印象了

D2T2  花匠

当时从最长上升子序列的思路出发,然后推了推,写了个单调队列,具体怎么写的忘了,不过也是AC。实际上最简单的做法只需要扫一遍,求出拐点的个数,加2就是答案了。

D2T3 华容道

这题xjb搜,就得了5分…

正确做法是bfs预处理,拆点,建图跑最短路。

具体来说:可以观察到只有空白块位于指定块的四方向上,指定块才可以移动。本质上还有另外一种移动方式,就是指定块不动,空白块从它的上/下左/右中的一个移动到另一个。那么这样就可以bfs预处理了,状态也有了,(x,y,k)表示指定块在(x,y),空白块在相邻的k方向上。spfa求最短路即可。

 

Dominator Tree

问题引入

题目要求解决的模型: 给定有向图G(可能有环)和图中的一个点r,对于G中的任意一个点x,求从r到x的路径上(可能有很多条)必须经过的点集。

  • Flow Graph:若有向图G中存在一点r,从r出发可到达G中所有的点,则称G是Flow Graph,记为(G,r)。
  • 必经点(dom):若在(G,r)中从r到y的路径一定经过点x,则称x是从r到达y的必经点,记为x dom y。 从r出发到达y的所有必经点构成的集合记为dom(y),即dom(y)={x | x dom y}。
  • 最近必经点(idom): 节点y的必经点集合dom(y)中dfn值最大的点x是距离y最近的必经点,称为y的最近必经点。最近必经点是唯一的,因此可以记x=idom(y)。

于是可以按下面\(O(V^2)\)暴力求解

  • \(pre(y)=\{x|(x,y)\in E\}\) y的前驱节点集合
  • \(suc(x)=\{y|(x,y)\in E\}\) x的后继节点集合
  • \(dom(r)=\{r\}\)
  • \(dom(y)=\cap _{x\in pre(y)} dom(x) \cup \{y\}\)
  • \(idom(x)=id[Max\{dfn[y]|y\in dom(x)\}]\)

Dominator Tree

设有向图G=(V,E),(G,r)是一个Flow Graph,则称(G,r)的子图\(D=(V, \{ (idom(i),i) | i\in V , i\neq r \}, r)\)为(G,r)的一棵Dominator Tree。

(G,r)的Dominator Tree是一棵有向有根树,从r出发可以到达G中的所有点,并且树上的每条边(u,v)都满足:u=idom(v),即父节点是子节点的最近必经点。

  • x=idom(y),当且仅当有向边(x,y)是Dominator Tree中的一条树枝边。
  • x dom y,当且仅当在Dominator Tree中存在一条从x到y的路径。
  • x的必经点集合dom(x)是Dominator Tree上x的所有祖先以及x自身。

半必经点

半必经点(semi) 在搜索树T上点y的祖先中,经过时间戳比y大的节点可以到达y的深度最小的祖先x,称为y的半必经点。关于半必经点有如下性质:

  • 半必经点也是唯一的,因此可以记x=semi(y)。
  • 一个点的半必经点必定是它在dfs树上的祖先,dfn[semi[x]]<dfn[x]
  • 半必经点不一定是x的必经点。

如何求半必经点:对于G中一点y,考虑所有\(x\in pre(y)\),设\(temp=INF\)。

  • 若dfn[x]<dfn[y],则(x,y)为树枝边或前向边,此时\(temp=min(temp,dfn[x])\)
  • 若dfn[x]>dfn[y],则(x,y)为横叉边或后向边,此时任意x在T中的祖先z,满足dfn[z]>dfn[y]时,\(temp=min(temp,dfn[semi[z]])\)
  • \(semi[y]=id[temp]\)

必经点

对于G中的一点x,考虑搜索树T中semi(x)到x的路径上除端点之外的点构成的集合path

设\(y=id[min\{dfn[semi(z)]|z\in path\}]\),即path中半必经节点的时间戳最小的节点。

  • \(semi(x)=semi(y)\)时,\(idom(x)=semi(x)\)
  • \(semi(x)\neq semi(y)\)时,\(idom(x)=idom(y)\)

题目

1.hdu 4694 Important Sisters

给一个有向图,输出每个点的必经点集合里的点的编号和,源点是n

2.2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest L

无向图,边有边权,起点为1号点,记起点到点k的最短路为dk,询问如果增大输入中第i条边的边权,最短路会受到影响的点有多少个。

做法很自然,在最短路构成的DAG上求支配树,询问的就是支配树子树大小了。这里把边新建点,方便处理。