OI中的常见套路

发表于 更新于 分类于 Waline：

本质相同

Example1

对于所有满足以下条件的长度为\(n\)的序列\(\{a\}\),我们称它是好的: \[ a_1=1\\ \forall 2\leq i\leq n,a_i\leq \max\{a_1,\cdots,a_{i-1}\}+1 \] 对于每一个数\(1\leq x\leq n\),求它在每个好的序列中出现的次数的平方和.其中\(1\leq n\leq 3000\),任意模数.

首先注意到可以枚举每个数\(x\)出现的次数,这样就转化为对满足某些位置是\(x\)的好的序列计数.

对于一个没有限制的好的序列,设\(f_{i,j}\)表示\([1,i]\)中填了\([1,j]\)(其中\(j\)必填)的方案数,不难发现这就是第二类斯特林数.

这样,对于一个\(x\),我们可以枚举它第一次出现的位置以及出现的次数,以及它第一次出现的位置后面的大于等于它的数的数量,合并即可.复杂度\(O(n^4)\).

再思考一下,似乎我们不用枚举它出现的次数,而是可以直接用\(g_{i,j,0/1/2}\)表示在\([1,i]\)中填\([1,j]\),\(1\)出现次数的平方和.同样枚举后面有多少大于等于它的位置,然后就可以把这些位置抽出来作为一个子序列,这个子序列就可以认为\(x\)就是\(1\).复杂度\(O(n^3)\).

如果写出上面的式子的话,会发现最难处理的是一个形如\(x^k\)的项,表示\(x\)第一次出现的位置后面仍然选比它小的数字的位置的方案数.这个怎么办呢?自然的想法是想在dp中顺便把它算了.

再进一步想,我们之所以合并麻烦,是因为取了两段上升区间.如果我们能求出一个上升区间和一个下降区间,在交点处合并呢?

但是这样怎么统计平方和呢?我们发现如果在\([1,k]\)中选了\([1,i]\),那么\([1,i]\)在\([k+1,n]\)中是本质完全相同的,因此还是可以用上面的dp求.

排列转环

Example1(P8416)

这题牛逼.

首先考虑一维的情况,一维情况下最劣应该是\(2,3,...,n,1\)这样的.

为啥捏?因为注意到操作数\(=n-\)排列环数,这样的排列环数为\(1\),显然是最小的.加上列也差不多,所以\(k_0=2n(n-1)=2n^2-2n\).

而我们显然可以通过两次操作把一个位置归位,最后剩一行再随便做做,这样的答案就是\(2n^2-n+1\),如果我们想赢,那就需要在上面的\(n-1\)行每行省出一步操作.

这咋做呢?类似上面的做法,也考虑找环然后省一步,对于一行,我们找到所有应该放在这里的值以及它们所在的列,把它们应该在的列和实际在的列连边,一定能找到至少一个环(自环也算),删环就可以省一步操作.

Example2

给序列\(a\)和排列\(b\),有若干次操作:

  1. 修改操作:给定\(x,y\),将\(a_x\)改为\(y\).
  2. 查询操作:给定\(l,r,x\),查区间\([l,r]\)内最长的子区间\([l',r']\),使得对\(\forall l'\leq i<r'\),有\(a_{i+1}=b_{a_i}\),且存在\(l'\leq i\leq r'\)使得\(a_i=x\).需要输出满足条件的子区间的长度最大值.

一步一步来,首先处理出所有的极长的满足条件的段,不难发现修改一个点只会断掉一个段或者连接两个段,影响是\(O(1)\)的.

难点在于,我们如何处理要求其中存在一个\(x\)这种东西.

注意到\(b\)是排列,上置换,不难发现\(b\)其实就是一个置换,也就是说每一个极长的段一定是一个置换环内部的元素,我们可以快速定位到\(x\)所在的置换环.但这样还是不能做.

考虑由于是单点查询\(x\),我们可以直接将数组也做置换,这样一个置换环就在一个区间内部,意味着一个极长的段一定是一个区间或者两个区间(原区间的一段前缀和一段后缀).

现在对于区间查询,我们考虑特殊处理和端点相交的段,这个是平凡的.这样我们只需要处理出完全被区间包含的那些段该怎么做.把右端点缩一缩,就等价于左端点完全被区间包含的那些点.也就是以\(a\)为横坐标,\(l\)为纵坐标,这样这些就相当于对一条横线取\(\max\),然后查询一段竖着的线段的最大值.注意到一行不可能有两个横线,因此可以线段树分治+线段树维护,复杂度\(O(n\log ^2n)\).

规定转移顺序

Example1

给定一张\(n\)个点的图,每个点有一个\([1,k]\)的颜色,求这张图有多少个子图是一棵树并且在这棵树中每种颜色恰好出现了一次.

首先无根树转有根树计数,设\(dp_{i,S}\)表示以\(i\)为根,已经选了\(S\)集合中的颜色的方案数.转移的时候枚举出边(注意可能会算重,只要是会算重的都考虑钦定某种颜色在其中一个块里),复杂度\(O(m3^k)\).

冷静一下,想到斯坦纳树,于是再设一个\(g_{x,S}\)表示以\(x\)为根且\(x\)只有一个儿子,\(S\)的定义类似的方案数.这样我们就可以用斯坦纳树的换根技巧计数.很厉害.

这个故事告诉我们:对于图论计数问题(尤其是和树有关),\(m\)大概率可以转化为\(n\),但是需要一些小技巧(例如斯坦纳树)

Example2(P7142)

类似宝藏那个题,我们考虑设\(f_{d,S_1,S_2}\)表示\(S_1\)中的点到\(1\)的距离\(<d\),\(S_2\)中的点到\(1\)的距离\(=d\).然后枚举到\(1\)的距离\(=d+1\)的点集,这一部分复杂度是\(O(n3^n)\),预处理一下不同情况的答案即可.

复杂度均摊

大概是如果多组询问那复杂度是错误的,但是如果我全局求,那我\(\sum\)起来的总复杂度大概是对的.经典问题是树上背包.

Example1

给定一颗二叉树,求对于每一个\(x\),满足\(x,y,z\)互不相同的三元组\((x,y,z)\)的价值(定义为两两距离之和对\(L\)取膜)的最大值是多少.\(n\leq 3000\).

乍一看,二叉树,想到换根后做dsu on tree+set.但是\(O(n^2\log^2n)\)实在是跑不过去.冷静一下,除去三点共线的情况,考虑三个点在二叉树上的两两LCA一定只有两个点,枚举其中深度较浅的那个点并枚举其子树中的两个点和子树外的一个点.假设其子树内有\(x\)个点对,子树外有\(y\)个点,注意到\(\sum x=n^2\and \sum y\leq n^2\),于是总复杂度\(O(n^2\log n)\).

字典序相关

题目中询问满足条件的字典序第\(k\)小之类的问题,通常采用转化为计数问题.

Example1([2022noip十连测day8]8ady)

首先,我们肯定想如果知道\(a\),我们怎么求出\(b\).

首先不难发现,我们可以这么还原:先开一个堆,然后先将前\(m-1\)个位置扔进堆里,从第\(m\)个位置开始,假设现在到了第\(i\)个位置\((m\leq i\leq n)\),每次将\(a_i\)扔进堆里,并从堆中取最小元素扔到\(i-m+1\)位置,最后把堆清空到剩下的位置即可.

大量实验证明:这种反向构造思路,你用个堆通常是做不动的.

我们考虑有没有别的做法.

一个一个数地考虑,\(b_1\)在\(a\)中的位置应该在哪?显然是应该在\([1,m]\)中,而且根据上面的堆的做法,显然它应该是\([1,m]\)中最小的数字,换句话说,我们需要满足:\([1,m]\)中除它以外的数字都比它大.

我们继续考虑\(b_2\),显然它在\(a\)中应该在\([1,m+1 ]\)中,并且需要满足\([1,m+1]\)中的所有数字除了\(b_1\),都比它大.

以此类推.不难注意到对于一个数\(b_i\),其中\(1\leq i\leq n-m+1\),它能填回的原序列的位置一定最大最大是\([1,m+i-1]\),并且如果它能填到区间\([l,r]\)中,这个区间中除去在它之前填进来的数字以外,均比它大.

但是,这显然是个上界.这个区间能不能缩小一下呢?

对于一个\(i\),我们找到最大的\(j\)满足\(1\leq j<i\)并且\(b_j>b_i\)(有可能找不到).

冷静一下,显然,\(b_i\)不能填到\([1,j+m-1]\).(因为如果它扔在这里,那它就:在\(j\)出堆前入堆,在\(j\)出堆后出堆,显然不合法)

也就是说,我们将每个数能填的区间缩小为了\([j+m,i+m-1]\).

那是不是说每个数只要填在这个区间中,就一定合法呢?

我们考虑一个数\(i\)以及所有比它小且在它后面的数字\(j\),当\(j=i+1\)时,显然\(j\)只有一种选择,直接填上;当\(j=i+2\)时,若\(i+1\)已经选择好了,那\(j\)显然也只有一种选择,填上.这样,对于所有\(i\),如果它前面有一个大于它的数字,那它一定只有一个位置可以填.

这样我们就可以简化为:给定\(b\)数组单调递增的问题.不难发现该条件下\(i\)可以选择的区间是\([1,i+m-1]\),且满足条件一定有解.

冷静一下,这个时候假设新序列长度为\(len\),那显然一共有\(m^{len}\)个满足条件的\(a\)序列.注意到这个级别是指数级别.

所以前面一定是按顺序填,直到后面才会打乱顺序.而后面的长度大概也就是个\(\log_m k\),枚举枚举就行.

前缀和与差分

Example1(loj3266)

把点都扔到坐标系上,显然到一个点曼哈顿距离相等的数一定在一个正方形(对角线平行于坐标轴)上.

我们考虑如果已知两个点,怎么找第三个点的坐标,显然是两个正方形的边界的交点,那也就是说,曼哈顿距离下,一个等边三角形必定有两个点所在直线与坐标轴成\(45\degree\)角,那这两个点必然和另一个点组成了一个等腰直角三角形(欧几里得意义下),我们枚举等腰直角三角形的直角顶点和直角边长就可以确认这两个点的坐标,而另一个点一定在一条与坐标轴成\(45\degree\)的斜线上,可以使用前缀和做.

注意到有的点对可能会被算两遍,要特判.

Example2

小孔在玩卡牌游戏.众所周知,在卡牌游戏里,过牌是很关键的,所以目前小孔的牌库中,只可能有数字牌\(0,1,2,3,4\).

数字牌\(x\)的含义是当你打出它的时候,会从牌库的顶端抽\(x\)张牌到自己手里,若牌库中不足\(x\)张牌,则将牌库抽空为止.打出的数字牌\(x\)会放入弃牌堆中.在题目中你可以认为这张牌不会再被用到了.

目前,牌库里有\(n\)张牌,从牌堆顶到牌堆底数第\(i\)张牌为数字牌\(a_i\).在开始回合时,发牌员会进行一次切牌,切牌的结果是从牌堆顶到牌堆底的牌的顺序变为了\(a_s,a_{s+1},...,a_n,a_1,...,a_{s−1}\).

接着,小孔会抽\(k\)张牌堆顶的牌到自己手上.每次小孔可以打出一张牌,但这一回合中小孔至多打出\(p\)张牌.小孔可以在任意时刻结束回合.

请问,这一回合中若小孔使用最优策略,那么牌库里最少还剩多少牌.进一步地,有\(q\)次这样的询问,每次询问给定三个整数\(s,k,p\),你需要输出牌库里最少还剩多少牌.\((n,q\leq 3\times 10^5)\).

每次询问是独立的,也就是说每次询问并不会以任何方式影响到之后的询问.

首先我们想一下我们需要知道什么:我们需要知道其在这一回合中打出的各种牌的数量是多少.而只要知道这一点,我们自然得到了答案是多少.注意到每次一定优先打出手头上最大的牌.

我们设\(sum_{t,i}\)表示从开始到抽完第\(i\)张牌之前,在只用大于\(t\)的牌的前提下,还能往下抽多少张牌.显然\(sum_{t,0}=0\)并且\(sum_{t,i}=sum_{t,i-1}+a_{i-1}[a_{i-1}>t]-1\).注意到\(sum_{t,i}=0\)就抽不了第\(i\)张牌了.不考虑还能抽负数张牌的情况,注意到\(sum\)数组具有可差分性!

那我们一开始抽了\(k\)张牌,也就是令\(sum_{s+1}\leftarrow sum_{s+1}+k\),那第一个不能继续抽牌的地方显然也就是第一个满足\(sum_{i}-sum_{s}\leq 0\)的地方,用原本的\(sum\)数组表示也就是\(sum_{i}+k\leq sum_{s}\).那第二个地方呢?由于后面的\(sum\)都加上\(k\)了,第二个地方也就是满足\(sum_j\leq sum_{i}-t\)的地方(不过注意到后面要倍增,所以直接写\(sum_j< sum_i\)也可以,这样方便用单调栈维护这个东西).以此类推,注意到这个东西和询问无关,可以使用倍增预处理,处理的过程中判断一下还有没有大小为\(t\)的牌以及用牌总数是否小于等于\(p\)即可.都是可以用前缀和之类的东西预处理的.最后从小的牌开始选,选完之后的牌就可以当成\(0\)牌了.另外要注意:我们要保证目前一定有大小为\(t\)的牌选,所以需要在做之前判断一下最后一次选择大小为\(t\)的牌的位置是在哪里.

等一下,注意到我们好像没啥办法判断还有没有大小为\(t\)的牌.有一个方法是:我们直接令所有\(\leq t-1\)的牌变成\(t\),并处理出不用\(\leq t-1\)的牌能跑到的最右点,然后取个\(\min\).

想出\(sum\)数组并发现可差分性后,这个题突然就变可做了.问题来了:咋想到的\(sum\)数组,又是怎么发现的可差分性?

首先,由于切牌这个环节会变化起点.所以有两种可能:要么是像倍增那样起点不定,要么是像差分一样其它起点的答案可以由原本的起点答案得到.那想到差分后呢?又注意到一定会先选较大的牌,所以大概率可以分层考虑:这样就先把问题转化为只有\(0/1\)或者是只有\(0/1/2\)的情况再继续考虑.由于要多组询问,所以答案一定是可以通过某种方式迅速算出来的,考虑到只要得到每种牌选的次数就可以快速算答案.又有一定是比它大的牌都选完了才选它,于是考虑第一次选不了其它牌只能选它的地方.注意到这个地方可以使用前缀和在变换起点的情况下求.于是由前缀和判断差分性质.

二分答案

Example1([2022qbxt国庆Day6]kth)

考虑\(f\)的取值不会很多,我们可以枚举\(f\)的取值,并把相同取值的归类.也就是,对于\(f=i\)的类别里也就是后\(i\)位为\(0\),第\(i\)位为\(1\)的那些数.

注意到每个类别内部是很有序的,也就是说我们可以采取类似初赛归并排序的方法二分,找到前\(k\)大的和.

调了一年,这个故事告诉我们,如果一个东西暴力调整能过/复杂度均摊,就不要写一些很丑的很难写的即使更快的东西去做.

Example2

给你一棵\(n\)个点的树,每条边是一个字符(字符集是小写字母),一个点的所有相邻边边权不同.

有\(m\)次操作:每次询问给出点\(x\)和字符串\(S\),\(S\)中不包含相同字符,\(|S|=26\),每次修改会修改一条边边权.

从\(x\)点开始,每次对与\(x\)点相邻的边,对这些边找出其边权在\(S\)中出现的位置,找出边权出现位置最靠前的边,然后走过去.

每次询问走过的边直接从树上删除,一条边正反方向算同一条边,也就是说没法\(x\rightarrow y\rightarrow x\).

这个过程会停机,你需要输出在哪个点停下来,询问之间独立.

这题最重要的思想在于:我们首先需要将这个问题改成一个判定性问题:判定性问题显然弱于找到答案.

怎么判定呢?对于一条路径,如果我们要沿着它走,那么我们就可以确定每个点的最小边(或者次小边),这等价于给出若干个边之间的大小关系,可以使用bitset维护一下,最后判定即可.我们发现判定数组是可以合并的,于是这玩意可以扔到线段树上维护.

会了判定这题就做完了,做树链剖分,然后开始从下往上跳重链,能跳到顶端就跳,不然二分跳到哪里,下去是同理的,只不过下去的二分需要多个\(\log n\).

整体二分

通常解决在二分的情况下,单次check的复杂度比较高的问题.思想是把所有询问共同的check一起做.

整体二分的具体复杂度往往需要现场分析.

最常用的整体二分的写法是分治.但是有的问题(例如不能撤销)可能不太好写分治.

还有一种方式是,我们把所有询问一字排开,然后求出每个询问当前二分的\(mid\),然后顺序处理或者别的什么处理方式做这些\(mid\).

Example1([AGC002D]Stamp Rally)

直接整体二分,注意需要做可撤销并查集之类的东西.

###分治

Example1(平面最近点对)

按照\(x\)轴排序,递归做两边的子问题,假设两边问题的最小值为\(d\),对着\(d\)做中间的问题.

Example2([CF1764G3] Doremy’s Perfect DS Class (Hard Version))

有一个\([1,n]\)的排列\(p\),每次可以询问\(l,r,k\),交互库会返回\(\lfloor\frac{p_l}{k}\rfloor,\lfloor\frac{p_{l+1}}{k}\rfloor,\cdots,\lfloor\frac{p_r}{k}\rfloor\)中不同数字的个数,你需要在\(20\)次询问内找到\(p\)中\(1\)的位置.

第一反应就是令\(k=2\),然后如果\(n\)是奇数,不难发现此时只有\(1\)自己一个人一组.一个自然的想法是,我们可以对于每个位置\(i\),查询\([1,i-1]\)和\([1,i]\)的答案,如果答案一样,那这个位置肯定不是\(1\).如果不一样,我们再查一下\([i,n]\)和\([i+1,n]\).由于\(1\)不会和左右任意一个人配对,不难发现如果这两种情况都不一样,那这里一定是\(1\),这样我们就做到了\(2n-2\)次查询.

那么如何优化呢?我们冷静一下,如果我们查询一个区间\([l,r]\),那么得到的答案自然是\(len-\)配对数字都在区间内的对数,因此我们自然也能得到这个区间的未配对数.这个时候发现,对于位置\(i\),如果我们查询\([1,i]\)和\([i+1,n]\),由于这两个区间内没配对的数字要么是\(1\),要么会和另一个区间中的数字配对,因此这两个区间中,未配对数多的那个一定包含\(1\).这样就可以通过\(k\)不断向下二分,最后只需要\(20\)步操作就可以解决\(n\)是奇数的情况.

那么\(n\)是偶数怎么办呢?这个时候\(1\)和\(n\)都没人配对.我们需要找到\(n\)并将它杀掉.注意到\(k\)可以取别的数,我们如果只是让\(k=2\)未免有些弱,而且看上去也区分不了\(1\)和\(n\),而不难发现,令\(k=n\)就可以找到\(n\)在哪里,于是可以先找\(n\)再找\(1\),需要\(40\)步.

那怎么继续优化呢?我们还是令\(k=2\),查询\([1,i]\)和\([i+1,n]\),我们发现此时会有两种情况:

  1. 左右两边未配对数量相差\(2\),这个时候\(1\)和\(n\)一定都在较大的那边,直接递归.
  2. 左右两边未配对数量相等,这个时候一定\(1\)在一边,\(n\)在另一边,我们可以通过一次查询\(k=n\)判断哪边是\(n\).

于是只需要\(21\)次.

但是还是不够,我们从哪里抠出那一次呢?发现最后处理区间\([i,i+1]\)还需要两步操作,我们看看能不能省掉一步.

  1. \(1\)和\(n\)都在\([i,i+1]\)中,我们显然只需要查询一步就可以知道哪边是\(n\).
  2. 只有\(1\)在\([i,i+1]\)中,我们考虑利用一下前面的信息.注意到我们一定已经知道\([1,i-1],[i,n],[1,i+1],[i+2,n]\)的答案(如果区间为空或者区间为\([1,n]\)显然我们也知道答案),假设这个区间中的两个数是\(1\)和\(x\),\(x\in(1,n)\),那么\(x\)一定有一个和它配对的数字,我们考虑通过\([1,i-1]\)和\([1,i+1]\)就可以知道和\(x\)配对的数字在\([1,i-1]\)还是在\([i+2,n]\).接下来只需要一步判断就可以找到\(1\)了.
Example3(XVII Open Cup named after E.V. Pankratiev. Grand Prix of Japan(opentraisn contest 1489)D Nice Set of Points)

给定一个点集\(S=\{(x,y)\}\),\((x_1,y_1)\)和\((x_2,y_2)\)可达当且仅当\(x_1=x_2\or y_1=y_2\).称一个点集是好的当且仅当这个点集中任意两个点的最短距离是它们的曼哈顿距离.给出一个点集,大小为\(N\),\(1\leq N\leq 1000\),加入不多于\(10000-N\)个点使得这个点集变成好的.

找一条分界线\(x=d\),我们将这条线左右两边的点全都作出在这条线上的投影点,将这些投影点全都加入,不难发现左右两边之间的路径就合法了,继续递归就行.

Example4([CF1442D]Sum)

一个自然的想法是由于越靠后的可能越优秀,所以应该是要不断往后挖的.具体地,我们发现只可能有一个数组被选了一部分,剩下的数组要么不选,要么全选.

为什么呢?假设有两个数组各选了一部分,不妨假设它们最后选的数分别是\(a\)和\(b\),下一个未选的数分别是\(c\)和\(d\),有\(c\geq a,d\geq b\),假设\(a\geq b\),那么自然有\(c\geq b\),于是我们把\(b\)删掉换成\(c\)一定更优秀.

有了这个性质后,我们可以枚举是哪个数组只选了一部分,然后求出剩下部分的背包,背包部分可以求前缀和后缀最后合并起来,我们的复杂度就是\(O(nk^2)\).

但这个复杂度还是不太够,如何优化呢?

注意到这里的背包是支持撤销操作的,我们考虑一个分治做法:每次做到\([l,r]\)的时候,假设此时\([1,l-1]\)和\([r+1,n]\)都加入答案了,我们把\([mid+1,r]\)也加入背包,然后递归求解\([l,mid]\),然后再撤销,同样的方法求解右边的答案.复杂度\(O(nk\log n)\).

Example5(AGC044D)

这题在于分治后归并,考虑我们是可以快速判断一个串是否是原串的子序列的,就是判断它们的编辑距离是否恰好等于长度之差.而我们也可以快速判断每个字母在原串中出现了多少次,只需要询问\(L\)个这个字母然后看编辑距离就是替换的次数.这样我们考虑对字母分治,\([l,r]\)表示只用到\([l,r]\)中的字母,得到的极长的原串的子序列是什么.边界情况\([l,l]\)是好处理的,对于\([l,r]\),我们考虑归并,合并\([l,mid]\)和\([mid+1,r]\)的时候不断判断当前串是否是子序列就行.

倍增

顺便一提,倍增比二分方便的一点在于:倍增能迅速确定答案的规模,这在复杂度与答案规模有关的时候至关重要.

Example1([SCOI2015]国旗计划)

先破环成链,然后设\(f_{i,j}\)表示从\(i\)这个人,途径\(2^j\)个人后能到达的最远的人是谁,然后就可以直接通过倍增处理.

#####Example2([PKUSC2018]星际穿越)

#####Example3(CF1523H Hopping Around the Array)

类似国旗计划,只不过需要用背包合并一维.

不过吧,这题有个问题在于最后的询问,我们要每次判断当前越界的点的代价是否小于等于dp数组的代价,如果小就回撤dp数组(因为无论如何都必不可能在这里选择).

Example4(loj3665)

思考一下发现,走相同的步数能到的点一定是一段区间,于是考虑使用倍增算法,设\(f_{x,i}\)表示从\(x\)走\(2^i\)步能到的区间,转移是简单的RMQ问题.

但是初值怎么求呢?先考虑右端点怎么求.对于每个路线\(j\),它会把\([A_j,A_j+k-1]\)能到达的右端点与\(B_j\)取\(\max\),由于查询在修改之后,所以这个东西很好做.

Example5(CF1707E)

引理1:如果\([l,r]\subseteq[L,R]\),则\(f((l,r))\subseteq f((L,R))\).

引理2:如果\([L,R]=[l_1,r_1]\cup[l_2,r_2]\),则\(f((L,R))=f((l_1,r_1))\cup f((l_2,r_2))\).

引理1显然,引理2是因为\([L,R]\)中的最大值和最小值一定都被后面的两个部分取到.

于是,考虑\([l,r]=\cup_{i=l}^{r-1}[i,i+1]\),就可以倍增了.

考虑求出每个单点的倍增数组,那么总区间的倍增数组也就是这些数组的最小值和最大值.

大概做一下.

Example6([22zr提高组十连测day6]百分号)

首先看上去多组询问给定起点终点看上去就很像倍增.

一个很自然的设计是\(L_{x,i}\)表示从\(x\)这个点跳\(2^i\)所能到达的最左端的点,\(R_{x,i}\)同理.但是能跳到最远的点不一定能跳到一个较近的点,那咋办呢?

冷静一下,注意到我们好像还没有用到括号序列的性质:两个跳跃要么包含要么不交,不可能出现第三种情况.

所以,如果目前能跳到的最远的点为\(l,r\),那么再跳一步能到达的最远的点一定是从\(l\)或\(r\)跳过去的.考虑反证这个结论,设能从\((l,r)\)中的一个点\(k\)跳到更远的点,那么由于之前没跳到过\(k\)就跳到\(l\)了,所以一定存在一个\(i>k\),\(i\rightarrow l\),而如果存在\(j<l\),\(k\rightarrow j\),显然不满足性质.

同理,我们最后处理询问答案的时候,考虑从\(x\)和\(y\)都跳.先从\(x\)跳到再跳一步就会跳过\(y\)的位置,然后把\(y\)跳到再跳一步就会跳过\(x\)的位置,那么现在的\(x\)和\(y\)一定相邻,不然分别跳一步就会出现包含的情况,于是一定是最优解.

对称/建立双射

Example1(CF1627F)

冷静一下考虑,分界线一定是一个中心对称图形,分成的两部分一定中心对称.那这条分界线一定过中心点.

我们考虑这么一点:如果所有点对都在矩阵一边,我们就可以直接求中心点到矩阵一边的最短路然后对称一下就好了.

而矩阵上遍布点对怎么办呢?我们在和每个点对对称的位置把这个点对复制一遍,然后从中心点找到一条到边界的最短路,把它对称一下即可.

Example2([AH2017/HNOI2017]抛硬币)

设\(A\)的正面朝上为\(S_A\),\(B\)的为\(S_B\).设\(p_1=\sum[S_A>S_B],p_2=\sum[S_A=S_B],p_3=\sum[S_A<S_B]\).

当\(a=b\),翻转所有硬币,自然有\(p_1=p_3\),又设\(P=p_1+p_2+p_3=2^{a+b}\),于是求得\(p_2\)即可得到答案.而\(p_2=\sum_{i=0}^a\binom{a}{i}\binom{b}{i}\),用范德蒙德卷积的变式,有\(p_2=\binom{a+b}{a}\).

同样,当\(a>b\)时.我们设\(p_4=\sum[a-S_A>b-S_B],p_5=\sum[a-S_A=b-S_B],p_6=\sum[a-S_A<b-S_B]\).同样是翻转硬币的套路,自然有\(p_4=p_1,p_5=p_2,p_6=p_3\).注意到:\(S_A\leq S_B\Rightarrow a-S_A>b-S_B\),但逆命题不成立.不妨设\(p_7=\sum[S_A>S_B\and a-S_A>b-S_B]\).自然有: \[ p_1=p_4=p_7+p_2+p_3=p_7+P-p_1 \] 于是只要求出\(p_7\)就可以求得\(p_1\).

考虑\(p_7\)如何求,注意到\([S_A>S_B\and a-S_A>b-S_B]=[0<S_A-S_B<a-b]\),我们可以枚举\(S_A-S_B\),然后继续用范德蒙德卷积的变式.

#####Example3([2022qbxt国庆Day4]C)

直接考虑对于每一对位置\((i,j),i<j\),计算它们可能产生的逆序对贡献.注意到每一对对答案的贡献会大概接近\(0.5\),我们考虑构造一个双射,判断双射左右是否都会贡献.

设\(d_i\)为\(i\)个数的错排数量,根据错排公式有\(d_n=(n-1)(d_{n-1}+d_{n-2})\).接下来讨论一下这两个位置的取值:

  1. 如果\(a_i=j,a_j=i\),那么一定贡献了逆序对,这里总共贡献为\(d_{n-2}\cfrac{n(n-1)}{2}\),一半的贡献也就是\(\cfrac{d_{n-2}n(n-1)}{4}\).
  2. 如果\(a_i=j,a_j=k,k\ne i\or a_i=k,a_j=i,k\ne j\),考虑前后两者形成双射.如果\(k\)在\(i\)和\(j\)之间,那么无论前者还是后者,都一定贡献逆序对;不然,则两种情况一定只有一种会贡献逆序对.前者多出的贡献应该是\(\cfrac{n(n-1)(n-2)}{6}(d_{n-2}+d_{n-3})\),也就是先选出\(i<k<j\),如果\(a_k=i\),那么剩余的可能性就是\(d_{n-3}\);不然,也就是说\(a_k\ne i\),类似于错排公式,剩余的可能性为\(d_{n-2}\).另外,由于\(d_{n-2}+d_{n-3}=\cfrac{d_{n-1}}{n-2}\),所以上面的贡献也就是\(\cfrac{n(n-1)}{6}d_{n-1}\).
  3. 如果\(i,j,a_i,a_j\)互不相同,那我们交换\(a_i\)和\(a_j\)一定可以构造出另一组答案,并且这两组答案中一定只有一组贡献了逆序对,于是二者形成双射.

除去上面的部分的贡献是\(\cfrac{d_nn(n-1)}{4}\).于是总贡献为:\(n(n-1)(\cfrac{d_{n-1}}{6}+\cfrac{d_n+d_{n-2}}{4})\).

Example4(ARC115D)

第一反应感觉完全不可做.

思考一下,如果我们随便选边肯定完蛋了:我们又不知道选出了几个奇度点,这不完蛋了?

先考虑要求全是偶度点怎么办?

由于点只有奇度点和偶度点两种,如果我能先随便选个边集,再把它删到全是偶度点好像就赢了.但是一方面我咋删啊,一方面这样删有可能删出重复的.又注意到删一条边就一定可以让两个点的奇偶性改变.

我们考虑求出原图的一棵生成树,然后剩下的边随便选.之后从生成树深度较大的点开始考虑:如果这个点是奇度点,我们就把它的父边删掉.容易发现这样是双射.而如果有奇度点的话可以先组合数选出来然后同样做上面的操作,容易发现是一样的.

不同的连通块可以分别做最后卷起来.

Example5(Hihocoder1230)

这题最重要的一点在于观察到一组\(a\)如果有解,那么一定是唯一解.为啥呢?我们考虑如何构造一个解:从小位到高位枚举,如果当前位所有数异或起来是\(1\),那么\(x\)这一位也必然是\(1\),然后加上后进位.这是由于序列长度是奇数.然后就每次对于\(a\in [x,m+x]\)计数,做FWT就行.

Example6(23省选10连测 day5B)

首先我们要知道,一轮冒泡排序的过程等价于:从前往后考虑每一个点,如果它前面存在一个比它大的点,就将它和前面的点交换.

于是我们考虑令\(b_i=\sum_{j=1}^{i-1}[a_j>a_i]\).也就是每次冒泡排序,这个\(b_i\)都会变成\(\max\{b_i-1,0\}\).显然\(b_i\)需要满足的条件是\(b_i\in[0,n-i]\),接下来我们证明:只要满足这个条件,\(b\)和\(a\)就是双射关系.根据\(a\)还原\(b\)是简单的,那么如何根据\(b\)还原\(a\)呢?我们只需要从大向小考虑元素,就可以判断元素插入哪里.

有了这个条件后,我们不妨设原序列是\(a'\),其对应\(b'\),那么显然\(b_i=\max\{0,b_i'-m\}\leq \max\{0,n-i-m\}\).也就是说,如果\(b_i=0\),那么\(b_i'\in[0,m]\),反之\(b_i'=b_i+m\).但问题在于:我们如何保证\(b_i'\in[0,n-i]\)呢?不难发现,冒泡排序每次会把前面最大的数扔到后面,也就是说整个序列最后的\(m\)个数一定有序,那我们分开考虑:对于最后的\(m\)个数,它一开始在序列中的相对顺序是无所谓的:无论如何都会扔到最后.而对于其它的数,如果\(b_i=0\),\(b_i'\in[0,m]\),由于最后都已经凑出\(m\)个数了,从大向小将数字插入,一定可以使这一部分满足条件.而如果\(b_i>0\),由于有判定条件\(b_i\leq \max\{0,n-i-m\}\),显然满足.于是我们设一共有\(k\)个\(b_i=0\)的位置(也就是前缀最大值位置),于是自然有\(f(a,m)=(m+1)^km!\).注意这个式子的前提在于判定每个\(b_i\leq \max\{0,n-i-m\}\)以及\(a\)的最后\(m\)个位置是\(n-m+1,\cdots,n-1 ,n\).到这里不难发现只要满足后者前者必定满足.现在只需要统计前缀最大值的个数就可以解决这个问题了.这个设计个\(dp_{i,j}\)表示前\(i\)个数的最大值是\(j\)就行.

拆多项式

通常适用于数据范围中有一项的范围不大的情况,然后拆成多项式后可以带入另一项较大的值.

Example1([22zr提高组十连测day5]可)

首先考虑数位dp,每次枚举当前的\(k\)个数中还有\(x\)个数被limit,这次又有\(y\)个数不用被limit,再枚举一下当前各位之和,然后可以写一个转移,复杂度\(O(k^4\lg x)\)

然后想了好久发现这个东西好像优化不动了.

冷静一下,注意到问题在于枚举,我们不妨把枚举换成容斥试试.设\(g(x)\)为\(\sum a\)为\(x\)的方案数,那么可以通过容斥得知:

\[ g(n)=\sum_{i=0}^k(-1)^i\binom{k}{i}\binom{n-i(x+1)+k-1}{k-1} \] 我们最后要求的答案也就是\(\sum f(n)g(n)\),继续推式子:

\[ ans=\sum_{n=0}^{kx}f(n)g(n)=\sum_{n=0}^{kx}f(n)\sum_{i=0}^k(-1)^i\binom{k}{i}\binom{n-i(x+1)+k-1}{k-1} \] \[ =\sum_{i=0}^k(-1)^i\binom{k}{i}\sum_{n=0}^{kx}f(n)\binom{n-i(x+1)+k-1}{k-1} \] 看上去好像推不动了.

冷静一下,会发现\(n\)的取值远远大于\(i,k\)的取值.于是我们选择把组合数拆成一个\(k-1\)次多项式,这样只需要处理出这个多项式的每一项的系数,然后就可以预处理后面的东西.

拆二项式系数的时候要注意特判上指标小于下指标的情况.

\[ ans=\sum_{i=0}^k(-1)^i\binom{k}{i}\sum_{j=0}^{k-1}c_{i,j}\sum_{n=i(x+1)}^{kx}f(n)n^j \] 其中\(c_{i,j}=[n^j]\binom{n-i(x+1)+k-1}{k-1}\).

这样我们就成功地分离出了一项\(\sum_{n=i(x+1)}^{kx}f(n)n^j\),接下来考虑怎么处理这一项.

考虑枚举\(i\),然后设\(dp_{j,limit}=\sum_{n=0}^{limit}f(n)n^j\),考虑拿数位dp做这个东西,枚举当前位置\(cnt\)的取值\(w\),根据二项式定理,\(dp_{a+b,limit}\leftarrow \binom{a+b}{b}dp_{b,limit}f(w)(w10^{cnt})^a\),那么\(\sum_{n=i(x+1)}^{kx}f(n)n^j=dp_{j,kx}-dp_{j,i(x+1)-1}\).

这样我们需要枚举\(i,a,b,cnt\)得到一组答案,然后还需要把这些答案合并起来,复杂度\(O(k^3\lg x)\).

抽屉原理

Example1([UNR #6]小火车)

首先考虑证明一定有解:

注意到我们可以先选择出两个不完全相同的集合,如果这两个集合的和相等,那么我们把只在第一个集合的\(b\)设为\(-1\),只在第二个集合的\(b\)设为\(1\),都在或都不在的设为\(0\),那么这显然就是一组解.

而由于\(p<2^n\),根据抽屉原理,显然存在这么两个集合.

考虑对于一个权值区间\([l,r]\),如果有超过\(r-l+1\)个集合的和在这个区间内,那一定有两个集合可以组成一个解.

假设现在已知权值区间\([l,r]\)一定有解,我们判断\([l,mid]\)中是否有超过\(mid-l+1\)个集合,使用折半搜索再合并可以快速求出权值和为某个定值的集合有多少个.然后可以使用双指针判断,继续递归下去判断即可.复杂度\(O(2^{\frac{n}{2}}n)\).

Example2([NOI2021]量子通信)

考虑\(k\leq 15\),所以如果我们把两个零一串每\(16\)个分一块,那么两个零一串相差少于\(k\)处,则一定有一块完全相等.由于数据随机,这个概率为\(\cfrac{1}{2^{16}}\).

考虑把在一块中是某个数的零一串全都集合到一起,然后暴力判断,复杂度约为\(O(\cfrac{n^2q}{2^{16}w})\).

拆贡献

Example1([2022qbxt国庆Day7]fenwick)

注意到要变换多次,考虑每个值的贡献.

一个点要往后更新,不难通过平行求和法则一个值\(v\)对它向后跳\(w\)步的贡献为\(\binom{w+k}{w}\).但是有修改很难办,怎么办?注意到如果我们暴力跳,查询的时候复杂度是\(O(1)\)的,我们没必要让它这么低.我们把所有值对\(p\)这个点的更新存到一个数组里,显然只有\(\log n\)种步数.最后每次查询的时候用组合数一起更新即可.

Example2([QOJ5097] 小 P 爱学习)

这个题的厉害之处在于完全将贡献拆开.

我们不妨设最后将所有的数分成了\(k\)组,那么显然我们只要算出两个东西就可以得到此时的答案的和:

  1. \(\sum_{x_{1,...,k}}\prod_{i=1}^ka_{x_i}\\\).
  2. \(\sum_{1\leq x_1,...,x_k\leq n,\sum x=n}\frac{(nm-k)!}{\prod_{i=1}^k(x_im-1)!}\\\).

第一个显然就是个背包,问题在于第二个的分子部分,我们用生成函数,设\(F=\sum_{i=1}^{n}\frac{1}{(im-1)!}x^i\),我们要求的就是\([x^n]F^k,\forall 1\leq k\leq n\).

这个东西可以做BSGS,也就是光速幂.这样就可以用\(O(n^2\sqrt n)\)预处理,用\(O(n)\)查询单个\(k\).

Example3(Luogu4211 [LNOI2014]LCA)

将\(dep\)拆成到根节点的路径上的点的数量,差分一下\([l,r]\),这样就只需要求\(z\)和一个前缀点的LCA的\(dep\).将这个操作离线下来,我们对于每一个点把它到根节点的路径上的点全部\(+1\),查询每个点到根节点上的权值和就行.

CF757G是一样的,只不过好像需要卡卡空间?

二进制拆位

Example1(Luogu5354 [Ynoi2017]由乃的OJ)

对每一位分开处理,对于线段树上每个区间,设\(f_{0}\)表示一开始\(v\)的这一位是\(0\),最后的答案是\(1\)还是\(0\),显然可以合并,拿bitset优化一下.

bitset优化暴力

Example1([2022qbxt国庆Day4]D)

先想一个很明显的优化:我们记录一下每个字符出现的位置,当我们判断当前字符串是否出现过的时候,我们直接从这个字符串开头的字符存在的位置进行判断.

如果我们记录下每个字符在母串中的某个位置是否存在,我们就可以基本脱离母串进行判断.注意到只需要用bitset优化这个过程就可以做到\(O(\sum tlen+\cfrac{nq}{w})\).

Example2([NOI2020] 制作菜品)

这题首先要根据数据范围,注意到\(m\geq n-1\)的时候存在贪心解法.

具体怎么做呢?我们将原料按照质量排序,每次选最小的那个,不够的话就选最大的那个的一部分,重新排序后递归处理.

为啥这个是对的呢?根据鸽笼原理,最大的那个的质量一定大于等于\(\frac{mk}{n}\),而最小的那个数和最大的那个数之和一定大于等于\(0+\frac{mk}{n-1}\geq k\),因此一定有解.

接下来我们就只需要做\(m=n-2\)的情况.

那么这个怎么做呢?我们发现每道菜和两个原材料有关,于是不妨抽象成图论模型:将这两个原材料所代表的点用一条边连起来:我们发现有\(n-2\)条边和\(n\)个点,这个图必不联通.也就是说如果有解,必然可以分成两个集合,这两个集合互不相关.如果我们分成了两个集合,一个集合有\(a\)个原材料,另一个集合有\(n-a\)个原材料,我们就可以第一个集合做\(a-1\)道菜,第二个集合做\(n-a-1\)道菜,自然解决了问题.

接下来的问题在于01背包,用bitset优化一下.

简化能更新答案的集合

简单来说就是当你注意到一个答案只有可能由某些地方贡献,我们就只判断这些地方的贡献.有的时候不仅需要减小集合,还需要使这个集合尽可能好维护,这个时候可能会向集合里放一些不合法但不可能更新答案的选项.

Example1(CF1149D Abandoning Roads)

首先一个把只有\(a\)边的连通块缩起来,那\(1\)到\(i\)的最短路显然是通过几个\(b\)连接若干个连通块来到\(i\).

由于防止用\(b\)边链接连通块的时候连出环,我们需要用一个\(dp_{S,x}\)表示从\(1\)经过\(S\)集合的连通块到\(x\)的最短路.

但是集合数量可能很多,怎么办?

注意到,如果这个集合只有一个点,那显然不可能重复经过;如果这个集合只有两个点,那重复经过意味着想用一条长度为\(2b\)的边代替一条长度为\(a\)的边,显然也不优秀;同理集合只有三个点也不优秀.

于是只有点数\(\geq 4\)的集合是有用的,复杂度\(O(2^{\frac{n}{4}}m\log n)\).

Example2

给定\(n\)个正整数,要求将\(n\)个正整数分到\(k\)个集合中,每个集合恰好\(\cfrac{n}{k}\)个数(保证\(k|n\))且每个集合中不能有相同的数.设一个方案的代价是每个集合的极差之和,求最小代价,\(n\leq 70\).

首先\(O(3^n)\)很好设计不说了.

注意到这题看上去就不太能多项式复杂度,我们考虑简化一下状态数.考虑做\(O(3^n)\)的时候,我们是将\(\cfrac{n}{k}\)个数打包成一个集合再塞进去,这样看上去就不太优秀,我们考虑能不能一个数一个数塞进去.

我们现在有\(k\)个集合,要塞进去一个数到一个集合中.注意到最后的代价实际上和很多数是没啥关系的.考虑先把数字从小到大排序,然后挨个插入集合.如果插入一个数之前,这个集合是空的,那这个数对答案有负的贡献;如果插入一个数之后,这个集合是满的,那这个数对答案有正的贡献;反之无贡献.

于是我们可以枚举目前集合填成啥样了,这样状态数变成了\((\cfrac{n}{k}+1)^k\).

这样还是过不去,我们再冷静一下,显然我们只关心每个集合填了多少个数而不关心具体是哪个集合,于是我们把每个集合的大小排序后再压成状态,这样状态数就是\(\sum_{i=0}^{k}{\binom{i+\frac{n}{k}}{\frac{n}{k}}}\\\),根据目前填到第几个数分一分类就会发现这部分上限是\(O(n\binom{2\sqrt n}{\sqrt n})\).

不过我们还需要保证一个集合里不能有相同的元素.这里我们考虑将相同的元素一起放并规定放的顺序.因为放进去的集合在放这种元素前是有大小顺序的,我们每次放进最大的集合中.换句话说,我们设\(f_{i,j,S}\)表示目前放到\(i\),状态是\(S\),并且\(a_i\)放进去的那个集合目前大小是\(j+1\)(放前是\(j\)).

算一下复杂度是\(O(n^2\binom{2\sqrt n}{\sqrt n})\)的,实际上远远跑不满,甚至写了个map来做双射也跑过去了.

Example3

给定一张有向图,多组询问,每次询问三个数\(p,x,y\),求是否能从\(p\)出发只经过\([x,y]\)中的边且经过的边的编号单调递减到达\(1\)号节点.

冷静一下,先加边,注意到如果加\(u\rightarrow v\)这条边的时候,不存在一条从\(v\)到\(1\)的路径,那这条边显然没有用.

做完这一步后,我们注意到可以在加边的过程中对于每个\(u\)维护从\(u\)到\(1\)的所有合法路径经过的最小编号的边的最大值\(maxn_u\),这样就可以对于每个点维护若干个二元组\((l,r)\),只要对于\(p\),存在一个二元组\([l,r]\in[x,y]\)就合法.

Example4([Petrozavodsk Winter-2014. Moscow SU Tapir Contest(openstrain contest 1435) C]Combinations Strike Back)

给定一个大小为\(n\)的可重集,多次询问,每次询问查询插入一个数\(x\)后,这个集合大小为\(k\)的可重子集共有多少个,每次询问互相独立.\(n,q\leq 1.2\times 10^5\),答案对\(1051721729=1003\times 2^{20}+1\)取膜.

自然的想法是上生成函数.

假设数字\(i\)在原集合中共有\(b_i\)个,那么原集合大小为\(k\)的可重子集数量显然为\([z^k]\prod_{i=1}^n\frac{z^{b_i+1}-1}{z-1}\).

插入一个数字\(x\),自然就是乘上一个\(\frac{z^{b_x+2}-1}{z^{b_x+1}-1}\).但如果每次都乘的话复杂度显然不行.怎么办?

注意到答案与插入的数字本身无关,只和这个数字在原集合中出现了多少次有关.而原集合最多有\(\sqrt n\)(自然根号)个出现次数不同的数字,预处理一下就行.

Example5([CF1621G]Weighted Increasing Subsequences)

一个自然的想法是拆出每个点\(x\)的贡献,再枚举终点\(y\),这样问题就转化为了以\(y\)结尾并且包含\(x\)的LIS计数,这样做到\(O(n^2)\)的复杂度.

那么怎么继续优化呢?我们还是想拆出每个点的贡献,但是如何不枚举终点\(y\)呢?我们考虑枚举一下和它做贡献的点\(z\)满足\(a_z>a_x\)并且终点\(y\)满足\(y<z\),但是这样的\(z\)有很多个,不难发现取最后一个就行.如果我们对整个序列取后缀\(\max\),就可以得到所有可能被当作\(z\)的点,而且更强的性质是,只要这些点不在LIS中,LIS的终点\(y\)必然有\(y<z\),这是显然的.做一下补集转化,就变成了计数包含\(x\)和\(z\)的LIS数量.

注意到\(z\)的数量不多,且所有数字按照权值排序后被这些\(z\)分成了若干个区间.所以颠倒值域和下标重新做LIS就行.

Example6(CF919F A Game With Numbers)

最小表示法表示每个人的手牌.

不过要注意有可能成环.我们考虑用刷表法更新,最后刷不出来的点就是和.

Example7([IOI2014]holiday)

首先发现走的一定是一个区间,然后发现这个区间\([l,r]\)的\(l\)随\(r\)的增大具有决策单调性,然后做完了,上主席树就行.

Example8(CF1446D2)

我们假设目前得到的答案区间是\([l,r]\),也就是说\([l,r]\)无论如何不可能扩展成更大的区间了.那这需要满足什么条件呢?注意到全局众数一定是答案,如果它不是答案,我们就可以往两边拓展,直到满足区间众数是答案且区间合法.显然可以实现.然后做根号分治.

这个是怎么想到的呢?我们考虑一个区间如何拓展成更大的区间:如果每个数出现次数不降,显然是一个更大的区间.这同样是在说:如果我们能找到一段区间,使得加上这段区间后,原本不是区间众数的数成为了区间众数,并且区间仍然合法,那就一定更为优秀.再注意到如果一个数在全局出现次数多于区间众数,这一定可以实现,进而推出全局众数的结论.

你以为结束了?没有,我们下面给出一个\(O(n\log n)\)的做法:

首先,我们假设全局众数是\(x\),枚举和它一起成为区间众数的数字\(y\),剩下的数先不管,那么区间大概长这个样:xyxyyxyxxxxxx.

我们发现这一段x一定是没有意义的:xyxyyxyxx[xxxx].

我们对于每一个\(y\)出现的位置,找到其左右两边离他最近的没有被标记的\(x\)标记一下,没有被标记的\(x\)一定没有意义.这样对于一组解\((x,y)\),合法的端点数量只有\(O(y出现的次数)\)次.每次判断每个端点是否可以做右端点,拿\(set\)维护一下后缀和就可以实现\(O(n\log n)\).

当然,这里得到的区间不一定是合法的(有可能\(x,y\)出现的次数都不是最多的,但没关系,这种一定不优秀).

【luoguP4062 [Code+#1]Yazid 的新生舞会】也是这个标记的思路,标记的话用一下链表之类的大概能做.

支配对问题

lxl起的名字.

这里的思路其实大概就是:我们将一些很废物的二元组杀了,然后将剩下的二元组进行贡献答案.我们称这种一个二元组严格强于另一个二元组的限制称作支配关系.

第一类支配对

虽然总数很多,但是本质不同的很少.

Example1(luoguP7880 [Ynoi2006] rldcot)

我们这么考虑:如果现在有三个点\(a,b,c,a<b<c\),它们两两LCA都是\(d\),那么显然\((a,c)\)这一对是没有用的,有用的是\((a,b)\)和\((b,c)\).进一步你发现这等价于什么呢:我们从下往上合并子树,每次做启发式合并,假设当前要把子树\(A\)合并到子树\(B\)上,考虑所有的点对\((a,b),a\in A,b\in B\)的贡献,显然,能贡献到\(a\)的\(b\)只有\(a\)的前驱和后继,这样我们就只找到了\(O(n\log n)\)个点对,它们等价于\(O(n\log n)\)个矩形,最后把\(dep\)相等的合并一下,随便做做.

Example2(luoguP8528 [Ynoi2003] 铃原露露)

和Example1基本差不多.

第二类支配对

虽然总数很多,但是有用的很少.

Example1(CF765F)

典.

Example2(CodeChef MINXORSEG)

这个题比较厉害,仍然考虑\(a<b<c\),我们看如果\(a\oplus c>\max\{a\oplus b,b\oplus c\}\)的充要条件是什么.

简单分类讨论一下,不难发现这意味着\(LCP(a,c)>LCP(a,b)\).于是有用的贡献对只有\(O(n\log v)\)个.

Example3(Luogu9058 [Ynoi2004] rpmtdq)

这题更为逆天.

首先,这题有两个维度:树和序列,我们要先处理掉其中一维.lxl:树这一维度更加困难,因此我们应该是选择困难的那一维分治掉.

考虑边分治,然后就只需要处理两棵子树间的贡献.但是对于一棵子树内的点,我们要找到在另一棵子树中有可能和它产生贡献的点对,这个咋做呢?

牛逼的一步来了,我们考虑对于每个点,算出它到分治中心的距离\(r\),然后找另一棵子树中到分治中心距离\(\leq r\)的点\(x\)与它贡献,但是这还是有很多点,其实只需要找这些点中的\(x\)的前驱后继就可以了.因为如果\(x<b<c\),\(b\)和\(c\)在同一边,那么\((b,c)\)一定比\((a,c)\)更加优秀.

Example4(CF1635F Closest Pair)

首先,由于匹配无序,我们考虑对于一对数\((i,j)\),只在\(w\)较大的那个位置来更新答案.

不妨假设较大的为\(i\),我们考虑\(i\)有可能和谁来更新答案.

如果现在有两个数\(k<j,w_k\leq w_i\and w_j\leq w_i\),如果\(w_k\geq w_j\),那肯定选\((j,i)\)更优秀;不然,如果选\((k,i)\)比选\((j,i)\)更优秀,那么我们会发现\((k,j)\)比\((k,i)\)更要优秀,因此答案一定会由\((k,j)\)更新而不是由\((k,i)\)更新.通过这里的分析我们发现,每个数只有可能和它左右两边的第一个\(w\)小于等于它的数更新.

于是我们可以找到\(O(n)\)个可能更新答案的点对,设点对为\((x,y)\),我们每次查找一个区间\([l,r]\),即要找到所有在\([l,r]\)内的点对并将它们的答案取min.

这一步可以将\((x,y)\)当作二维平面的点,查询当作一个左下角为\((l,l)\),右上角为\((r,r)\)的矩阵,就是一个经典的矩阵取min的操作.

Example5([ICPC2017 WF]Money for nothing)

注意到抽象问题后等价于有若干个A点\((x_1,y_1)\)和若干个B点\((x_2,y_2)\),我们想要找到一个A点和一个B点使得\((x_1-x_2)(y_1-y_2)\)最大.也就是它们作为右上和左下顶点的矩形面积最大.

怎么做这个问题呢?首先我们必须要发现的一点是:对于A点来说,如果有两个点\((a_1,b_1)\)和\((a_2,b_2)\)满足\(a_1\leq a_2\),\(b_1\leq b_2\),那么前者一定更优秀.把那些废点删掉后,就会得到一个横坐标递增,纵坐标递减的点的序列.对于B点是同理的.

这个序列看上去就很亲切了,接下来简单证明一下是满足决策单调性的就可以判断答案了.

奇偶染色

Example1

一个\(9\times 9\)的网格,一开始上面有\(65\)个蚂蚁,每个蚂蚁每分钟会四联通移动一格,每个蚂蚁每三分钟所在的格子不能在一条直线上,求证:一定会有一个时间,两只蚂蚁在同一个格子里.

sol1:

注意到如果条件不成立,则一定存在若干条路径,蚂蚁在路径上转圈,也就是找到长度和尽可能大的路径不交地覆盖矩阵,注意到一定是使用\(2\times 2\)的矩阵路径,于是最多有\(64\)只蚂蚁.(感性理解)

sol2:

考虑对奇偶染色,设\((i,j)=\begin{cases}white & 2\nmid (i+j)\\blue& 2\mid i\and 2\mid j\\yellow&otherwise\end{cases}\).

我们把黄格子和蓝格子称为彩格子,注意到如果一开始一只蚂蚁在白格子,一分钟后必定在彩格子.一开始一只蚂蚁在蓝格子,两分钟后必定在黄格子.

因为最多有\(16\)个蓝格子,所以一开始黄格子和蓝格子上分别最多有\(16\)只蚂蚁,从而白格子上最多有\(32\)只蚂蚁,总共最多\(64\)只,得证.

Example2(CF1521E)

首先考虑我们显然可以一行空一行放,也就是说如果最大的\(a_i> n\times \lceil\frac{n}2\rceil\)的话显然不可以,如果能放的位置少于\(\sum a\)显然也不可以.

类似lyz那个题,我们考虑删去行列编号均为偶数的点,这样就满足了一个子矩阵不能全放的限制.

然后呢?我们考虑将所有能放的位置排序.先把所有的位置分成三类:\((even,odd),(odd,odd),(odd,even)\),不同类位置按照这个顺序排,不然按照相对位置排.然后直接从头开始放.如果不合法,一定是同种颜色放到了\((even,odd)\)和\((odd,even)\),并且相同类别是按照相对位置排序的,于是一定不满足最大的\(a_i\leq n\times \lceil\frac{n}2\rceil\)的限制条件.所以这么做一定是对的.

好!冷静一下,咋想到的啊.

首先这种题肯定要找到一些看上去就很显然的边界,当你发现找不到的时候,大概率就一定有解了(大概率).

然后呢?注意到不合法一定是同种颜色放到了\((even,odd)\)和\((odd,even)\),又观察到每种位置的数量和一个边界限制条件很像,于是就可以构造出来了.

所以大概是说,这种构造题要先想判断边界的条件,然后对着做.

Example3(CF1615F)

太牛逼了这个题.

首先,找边界条件:啥时候\(s\)不能变成\(t\)呢?一个自然的想法是数\(1\)的个数的奇偶性,但这样显然不对(\(01\)和\(10\)不能互相转移),我们需要一个更强的条件.

然后:注意到每次操作是相邻的两个数,于是我们有:奇数位置的和-偶数位置的和是定值.但是:注意到这个操作是有限制的!它只能对相邻相同的位置做.

然后我也不知道咋想到的,可能是因为找到限制条件后只要不改变限制条件就可以随便转化?反正我们先把偶数位置全部取反,这样操作就变成了交换相邻数字(如果相邻数字不相同,取反后相同,交换无用).

就可以dp了.

Example4(CF1517G)

按照横纵坐标的奇偶性,分四种情况染色.注意到四边形接下来的路径一定会形如\(1\rightarrow 2\rightarrow3\rightarrow4\),建立分层图跑最小割.

捆绑更新答案

Example1([2022qbxt国庆Day6]binary)

首先因为有\(-1\),我们先考虑一个朴素的暴力,从\(L\)到\(R\)枚举现在被匹配的数\(i\),我们假设之前匹配到\(p-1\),那我们接下来一定是要找到一个最小的\(x\geq p\)能把\(i\)给匹配掉,仔细思考这个过程,由于是二进制考虑最高位,不难发现我们只需要找到\((p\and i)\oplus i\)的最高位\(1\),然后把\(p\)的这一位改成\(1\),然后后面的位置全部设成\(0\),如果\(i\subseteq p\)那么就不用改.

冷静一下,二进制大概率是没啥通项公式的,还是要一点一点做.但是我们枚举每一个数实在是太慢了,我们考虑一个地方:\(i\subseteq p\)就不用改,下一步\(i+=1,p+=1\),如果没有发生进位还是不用改,这个过程看上去就很可以优化.

所以我们考虑:当遇到\(i\subseteq p\)的时候,我们就捆绑更新.如果不满足就暴力更新.重复这个过程,每次不断暴力更新\(\rightarrow\)捆绑更新$\(暴力更新\)…\(.每次捆绑更新至少会更新一个\)lowbit\(,而暴力更新的情况下,每次\)p\(至少会多包含一位\)i\(.就算后面进位把这一位消掉了,由于这里进位了,那下一步一定可以直接包含掉,于是复杂度也是\)n\(的,反复做一下就做完了,这里能分析复杂度\)O(T^2R)$.我们冷静一下,发现二者复杂度算重了,捆绑更新会帮助暴力更新多匹配\(1\),于是复杂度\(O(T\log R)\).但是肯定跑不满,考场甚至写了个上界\(O(T\log^2 R)\)的仍然跑的飞快.

Example2

给定一棵树和一个值域为\(n\)序列\(a\),每次询问给出\(l,r,x\).

设\(f(x,y)\)为点\(x\)朝着\(y\)的方向走一步后得到的点,求\(x\)在经过\(a[l\cdots r]\)操作后得到的答案.

这么考虑:这题看上去就需要把任何一个数字\(x\),通过若干个点变成了一个\(f(x)\),我们要做的就是把\(f(x)\)求出来,这玩意很难求,考虑分块,单点用长剖做\(O(1)\)求\(k\)级祖先,然后对于每个整块预处理出它的\(f\)就可以了.

接下来的问题在于如何快速处理一个块的答案,考虑把所有的\(x\)扔到树上,然后一起维护它们的\(f(x)\).这玩意看上去好像有点不太能做.

牛逼的一步来了:考虑对于每个块内的\(\sqrt n\)个点,建立这些点的虚树,对于不在虚树上的点,它们一定会往虚树的方向跑(其实也就是向上跑),然后处理出时间扫描线转化成在虚树上的点的问题.对于在虚树上的点,考虑虚树一共有\(O(\sqrt n)\)条边(也就是原树上的路径),我们用一个双端队列维护每条边上的点,显然每次每条边只会有\(O(1)\)的入队和出队,这样就实现了\(O(n)\)的预处理单个块.

单独更新答案

Example1

一个数轴上有\(n\)个小球,第\(i\)个小球在\(x_i\)坐标处.数轴上还有\(m\)个洞.第\(i\)个洞在\(y_i\)坐标处.你每秒可以以相同矢量速度移动所有小球.当一个小球和一个洞重合时,小球就会进洞.求一共可能出现多少种最终情况.(我们认为,两种”最终情况”不同,当且仅当存在一个球在两种情况中进入了不同的魔法洞中)

考场的想法:按照洞分类,把被同样两个洞夹起来的球一起处理,显然会有一段区间往左走一段区间往右走,按照这种区间的长度排序,然后硬dp,复杂度\(O(n^3)\).

实际的做法:我们抛弃区间,单独考虑每个球.对于每个球而言,有用的信息只有它到左端点的距离和它到右端点的距离.我们把这两个距离缩为\((x_i,y_i)\).接下来我们要给每个点\(0/1\)染色,如果是\(0\)代表它要到左边的洞里,如果是\(1\)代表要到右边的洞里.那什么染色条件是无解的呢?

如果存在两个点\(a\)和\(b\),\(col_a=0\),\(col_b=1\),那显然当\(x_a\geq x_b\and y_a\leq y_b\)时无解.换句话说,如果\(col_b=1\and x_a\geq x_b\and y_a\leq y_b\),那么\(col_a=1\).我们不妨按照\(x\)降序排序,\(x\)相同的按照\(y\)升序排列.那就会先决定\(b\)再决定\(a\).注意到:如果\(a\)能确定\(c\)的状态,那\(b\)一定也能确定\(c\)的状态.因此我们采取这个策略:如果\(x_a\geq x_b\and y_a\leq y_b\and col_b=1\),那我们直接不管\(a\);反之,则考虑一下\(a\)的两种取值即可.具体一点,我们设\(f_{i,0/1}\)表示以\(i\)结尾,\(col_i=0/1\)的方案数,然后顺着做就好.注意到:我们其实不关心\(col_x\)具体是啥,我们只关心最后的方案数.所以其实可以直接删去第二维.

zhq对这题的理解:

这可以等价成求一个上升子序列.上升子序列说的是如果\(x_i<x_j,y_i>y_j\),\(i\)“选了”,\(j\)就必须”不选”.但是钦定必须选和必须不选,这两个限制是一样的.就是说,\(j\)没有选择的权力了.

这个说法很有意思,但是要注意:类似说法成立当且仅当我们认为\(j\)选了和认为\(j\)没选对后面不会产生影响.

Example2([Petrozavodsk Summer-2015. Moscow IPT Contest(openstrain contest 1464) J]Two Airlines)

这是一道交互题.给定一张\(n\)个点的完全图,每两个点之间是红色的边或是蓝色的边.可以询问\(2n\)次某两个点之间的边的颜色,求一条哈密顿回路使得这条路上的颜色段最多有两个.

考虑将点逐个加入.假设现在的哈密顿回路的两种颜色分别是\(r_s\rightarrow r_t\)和\(b_s\rightarrow b_t\),当前要加入\(x\),我们每次询问\(x\)和\(r_t\)和\(b_t\)之间的颜色,如果可以加入链就加入.如果不能加入,必然意味着\(x\)和\(r_t\)之间是蓝边,和\(b_t\)之间是红边,我们查一下\(r_t\)和\(b_t\)之间是什么边,然后将其中一个点与\(x\)一起扔到对面就行.

不过这样用了\(3n\)次询问,考虑先询问\(r_t\)和\(b_t\)之间的颜色,这样就能省掉一种.

寻找不变量

Example1([NOIP2021] 方差)

首先我们注意到:设\(b_i=a_i-a_{i-1}\)这个操作相当于交换\(b_{i-1}\)和\(b_i\).

接下来推一下式子: \[ n^2S^2=n\sum_{i=1}^na_i^2-(\sum_{i=1}^na_i)^2\\ =n\sum_{i=1}^n(\sum_{j=1}^ib_j)^2-(\sum_{i=1}^n(n-i+1)b_i)^2\\ =n\sum_{i=1}^n\sum_{j=1}^ib_j\sum_{k=1}^ib_k-\sum_{j=1}^n(n-j+1)b_j\sum_{k=1}^n(n-k+1)b_k\\ =n\sum_{j=1}^nb_j\sum_{k=1}^nb_k\times (n-\max\{j,k\}+1)-\sum_{j=1}^n(n-j+1)b_j\sum_{k=1}^n(n-k+1)b_k\\ =n\sum_{j=1}^nb_{n-j+1}\sum_{k=1}^nb_{n-k+1}\times \min\{j,k\}-\sum_{j=1}^njb_{n-j+1}\sum_{k=1}^nkb_{n-k+1} \] 令\(c\)为\(b\)的倒置数组,则原式 \[ =n\sum_{j=1}^nc_{j}\sum_{k=1}^nc_{k}\times \min\{j,k\}-\sum_{j=1}^njc_{j}\sum_{k=1}^nkc_{k}\\ =2\sum_{j=1}^nnc_j\sum_{k=1}^jc_kk-2\sum_{j=1}^njc_{j}\sum_{k=1}^jkc_{k}+\sum_{i=1}^nc_i^2i(i-1)\\ =2\sum_{j=1}^n(n-j)c_j\sum_{k=1}^jc_kk+\sum_{i=1}^nc_i^2i(i-1)\\ =\sum_{j=1}^n(n-j)c_j\sum_{k=1}^nc_kk+\sum_{i=1}^n(n-1)ic_i^2 \] 推到这一步发现好像没啥用但是推了好久懒得删了

冷静一下,由于一开始的数列是单调递增的,所以改变后的数列一定也是单调递增的(差分数组均\(\geq 0\)).感性上理解,我们肯定是想让尽可能多的数接近绝对值,于是让重新排列后的差分数组呈现单最小值的峰看上去就很优秀.

这样我们设计\(dp_{i,S}\)表示现在填到第\(i\)小的\(b\),\(\sum a=S\)的情况下最小的\(\sum a^2\),复杂度\(O(n^2a)\).

注意到\(a\)很小的时候大部分\(b\)都是\(0\),于是可以优化为\(O(na^2)\).

Example2([AGC030E] Less than 3)

注意到:当我们把一个位置取反的时候,这个位置相邻的左右两个位置一定有一个\(0\)和一个\(1\),所以我们的操作等价于移动\(0\)和\(1\)的分界线.

然后枚举一下从边界多产生了多少个分界线就行.

组合意义

Example1(ARC110D)

注意到这相当于先把一个长度等于\(m\)的序列划分成\(n+1\)段,再从第\(i\)段选出\(a_i\),其中\(a_{n+1}=0\).

于是自然是\(\binom{n+m}{\sum a+n}\).

Example2(ABC231G)

乍一看,感觉完全不可做.因为一开始给定\(a\)了,感觉上好像也不太能组合意义.

如果没有\(a_i\)怎么做?我们设\(f_n\)表示将\(k\)个小球分到\(n\)个盒子后的答案.那乘法相当于:分完后,在每个盒子中取出一个小球的方案数.于是\(f_n=\binom{k}{n}n!n^{k-n}\).

那给定\(a\)咋做呢?我们注意到上面的式子好像可以对于任意\(n\)快速求.于是将原式子拆为:\(\prod(a_i+b_i)\),那答案就是选出\(n-x\)个\(a\)和选出\(x\)个\(b\)的答案.前者可以背包,后者也就是\(f_x=\binom{k}{x}x!n^{k-x}\).

Example3(AGC060D)

不妨设\(C_p=\{i|p_i>p_{i+1},1\leq i<n\}\).

用一下组合意义,注意到答案等于: \[ \sum_{S}(\sum_{p}[S=C_p])^2 \] 中间那个地方看上去是经典的计数容斥,我们对着它做容斥: \[ \sum_{S}(\sum_{p}[S=C_p])^2=\sum_{S}(\sum_{S\subseteq T}\sum_{p}(-1)^{|T|-|S|}[T\subseteq C_p])^2 \] 这个咋做呢?我们考虑用组合意义展开: \[ \sum_{S}(\sum_{S\subseteq T}\sum_{p}(-1)^{|T|-|S|}[T\subseteq C_p])^2\\=\sum_{S}\sum_{S\subseteq T_1,T_2}(-1)^{|T_1|+|T_2|}(\sum_{p}[T_1\subseteq C_p])(\sum_p[T_2\subseteq C_p]) \] 注意到\(S\)屁用没有,直接交换枚举顺序. \[ \sum_{S}\sum_{S\subseteq T_1,T_2}(-1)^{|T_1|+|T_2|}(\sum_{p}[T_1\subseteq C_p])(\sum_p[T_2\subseteq C_p])\\=\sum_{T_1,T_2}2^{|T_1\cap T_2|}(-1)^{|T_1|+|T_2|}(\sum_{p}[T_1\subseteq C_p])(\sum_p[T_2\subseteq C_p]) \] 考虑\((\sum_{p}[T_1\subseteq C_p])\)怎么求,注意到这等价于所有\(T_1\)中的位置全都被钦定为\(>\),而其他位置任意,如果我们设所有以大于号连接的部分的长度为\(l_1,l_2,...,l_k\),那么这里的答案就是\(n!\prod_{i=1}^k\frac{1}{l_i!}\).

但我们很快发现了难点:\(2^{|T_1\cap T_2|}\)这个东西是难求的,怎么办呢?

我们考虑一下这个东西的意义:其实也就是在\(T_1\)和\(T_2\)中都是\(>\)的位置,这个好像不太好求,因为\(>\)是很平常的,但如果取补集就不一样了,取补集后意味着都是任意的位置的数量,而我们上面已经发现了:如果有一个位置对前后两个数字的约束是独立的,那我们可以把前后两个位置拆开.于是我们有: \[ \sum_{T_1,T_2}2^{|T_1\cap T_2|}(-1)^{|T_1|+|T_2|}(\sum_{p}[T_1\subseteq C_p])(\sum_p[T_2\subseteq C_p])\\ =\sum_{T_1,T_2}2^{((n-1)-|T_1\cup T_2|)-(n-1)}(-2)^{|T_1|+|T_2|}(\sum_{p}[T_1\subseteq C_p])(\sum_p[T_2\subseteq C_p])\\ =2^{1-n}(n!)^2\sum_{T_1}((-2)^{|T_1|}\frac{1}{\prod l_{1,i}!})\sum_{T_2}((-2)^{|T_2|}\frac{1}{\prod l_{2,i}!})2^{n-1-|T_1\cup T_2|} \] 其中\(n-1-|T_1\cup T_2|\)意味着均不在\(T_1\)和\(T_2\)中的位置的数量.为了给每一段连续的\(>\)都分配权值,我们进行一个细小的修改: \[ 2^{-1-n}(n!)^2\sum_{T_1}((-2)^{|T_1|+1}\frac{1}{\prod l_{1,i}!})\sum_{T_2}((-2)^{|T_2|+1}\frac{1}{\prod l_{2,i}!})2^{n-1-|T_1\cup T_2|} \] 写到这里应该就能发现,接下来必然要对\(n-1-|T_1\cup T_2|\)做整体操作.那我们再这么搞可能就很难受,我们采取这样的方式:对\(T_1\)和\(T_2\)求补集,这样它们的含义就变成了除了集合中的元素,剩下的全部被钦定为了\(>\),我们自然有: \[ 2^{1+n}(n!)^2\sum_{T_1}(\frac{1}{(-2)^{|T_1|+1}}\frac{1}{\prod l_{1,i}!})\sum_{T_2}(\frac{1}{(-2)^{|T_2|+1}}\frac{1}{\prod l_{2,i}!})2^{|T_1\cap T_2|}\\ \] 这里已经很显然了,我们大概要做一个不断加段的做法,那此时\(|T_1\cap T_2|\)这个限制就显得尤其强,如果只是\(S\subseteq T_1,T_2\)就会好做很多:我们可以钦定\(S\)作为分界线,然后把两边的东西卷起来.因此我们暴力拆开后面的式子: \[ 2^{1+n}(n!)^2\sum_{T_1}(\frac{1}{(-2)^{|T_1|+1}}\frac{1}{\prod l_{1,i}!})\sum_{T_2}(\frac{1}{(-2)^{|T_2|+1}}\frac{1}{\prod l_{2,i}!})2^{|T_1\cap T_2|}\\ =2^{1+n}(n!)^2\sum_{S}\sum_{S\subseteq T_1}(\frac{1}{(-2)^{|T_1|+1}}\frac{1}{\prod l_{1,i}!})\sum_{S\subseteq T_2}(\frac{1}{(-2)^{|T_2|+1}}\frac{1}{\prod l_{2,i}!})\\ \] 令\(f(T)=\sum_{S\subseteq T}(\frac{1}{(-2)^{|T|+1}}\frac{1}{\prod l_{2,i}!})\\\),则原式即: \[ 2^{1+n}(n!)^2\sum_{S}(\sum_{S\subseteq T}f(T))^2 \] 考虑下面这个东西怎么求: \[ \sum_{S}(\sum_{S\subseteq T}f(T))^2 \] 注意到,如果我们把每一段(\([T_i,T_{i+1})\))的贡献求和,那么\(f(T)\)相当于这些和乘起来,那么\((\sum_{S\subseteq T}f(T))^2\)就是这些和的平方乘起来.换句话说,我们自然有\(ans_n=\sum_{m}ans_{n-m}g^2_{m}\),其中\(g_m\)表示长度为\(m\)的一段的贡献之和.而\(g_{n}=\sum_m g_{n-m}\frac{1}{-2m!}\).二者都可以使用分治FFT或多项式求逆解决.更进一步地,\(h_i=\frac{1}{-2i!},G=\frac{1}{1-H},F=\frac{1}{1-G}\).

这题还有一个做法:tyy的变魔术做法.

还是容斥,考虑将\((>,>)\)容斥掉,这样我们有若干种对:\(2(<,<),1(e,e),-(e,<),-(<,e)\),然后我们发现两个序列联系得太紧了,我们考虑分配系数:\(<\rightarrow \sqrt 2\),\(e\rightarrow -\frac{1}{\sqrt 2}\),但是这样发现\((e,e)\)算错了,你把剩下的补上就行.你会发现这个式子和上面我们推的是等价的,但是变魔术.

复杂度抵消

Example1(CF1439B)

首先注意到度数小于\(k-1\)的点一定没用,于是可以不断删点.删点后的图度数全部\(\geq k-1\).

首先如果剩下的点度数全都\(\geq k\)那就直接找到答案,不然,我们看一下度数为\(k-1\)的点:它要么在团里,要么没用.不妨直接暴力判断是否在团里,复杂度\(O(k^2)\).

欸等一下,这总复杂度\(O(mk^2)\)了啊,这咋办?

首先,删完点后的度数全都\(\geq k-1\),注意到此时的点数是\(O(\frac{m}{k})\)的.所以复杂度\(O(mk)\).

好像还是过不去,这咋办?

冷静一下,如果\(k\geq \sqrt m\),显然不可能存在团.于是复杂度\(O(m\sqrt m)\).

寻找关系式

Example1

一张有向图,边有两种颜色,从\(s\)开始随机游走,维护一个权值.经过第一种颜色的边,权值\(+1\).经过第二种颜色的边,权值归\(0\).保证\(t\)没有出边,所有点均能到\(t\).询问到\(t\)时权值的期望和方差.\(n\leq 100\).

(注意方差为平方的期望减去期望的平方.)

注意到难点在于权值归\(0\).所以一个点到\(t\)的期望权值一定和到达它时的权值有关系.

然后就来到了降维打击的时间:我们可以使用数学归纳法证明,如果到一个点\(u\)的权值是\(x\),那它到达\(t\)的权值一定形如\(a_ux+b_u\).

如果要严谨一点的话,我们发现第一种颜色的边会影响常数项,第二种颜色的边会影响一次项,因此最后的答案一定是一次函数.

最后可以使用高斯消元直接求出每个点权值的\(a_u\)和\(b_u\),就可以求出期望.

至于方差是同理的,你注意到平方的期望一定是一个二次函数.

特判边界

Example1(2022ICPC杭州E)

第一反应肯定是一点一点调整成\(\{1,2,...,n\}\)的形式,写个暴力验证一下发现当\(n\geq 4\)的时候的确都可以调整成功.

假设目前形如:\([1,k],A,k+1,B\).我们考虑如何调整:

  1. \(|B|\ne 0\).

我们有: \[ \{[1,k],A,k+1,B\}\rightarrow \{B,A,k+1,[1,k]\}\rightarrow \{[1,k+1],B,A\} \]

  1. \(|B|=0,|A|=0\).

直接合并就行.

  1. \(|B|=0,|A|\geq 2\).

假设\(A=A_1A_2\),我们有: \[ \{[1,k],A_1,A_2,k+1\}\rightarrow \{A_2,k+1,A_1,[1,k]\}\rightarrow \{[1,k+1],A_1,A_2\} \]

  1. \(|B|=0,|A|=1\).

此时一定有\(k\geq 2\),发现有点难构造,但是我们猜测是可以构造出来的.不难证明这个问题等价于将\(\{1,2,4,3\}\)调整为\(\{1,2,3,4\}\),写个暴力跑一下就行.

摩尔投票

Example1([CF643G]Choosing Ads)

将摩尔投票扩展一下.我们现在想求其中出现次数大于等于\(\lfloor\frac{n}{p}\rfloor\)的数字,令\(k=\lfloor\frac{100}{p}\rfloor\),我们考虑每次取出\(k+1\)个两两不同的数字并且全部杀掉,那么做完这一步操作后,该满足条件的仍然满足条件(讨论一下),于是拿线段树维护当前的五个数的出现数量,每次对着杀就行.

寻找周期性

Example1([CF1463F]Max Correct Set)

自然的想法是\(O(n2^{\max(x,y)})\)作dp.

接下来比较牛逼的是,注意到如果\(S_1\)满足条件,令\(m=x+y\)那么\(S_1\cup(S_1+m)\)也满足条件.

我们考虑\(S_1\)中满足条件意味着什么,意味着\(\forall a,b\in S_1,a<b\),\(b-a\ne x\and b-a\ne y\),这意味着\(m+b-a\ne x\and m+b-a\ne y\),这同样意味着\(m+a-b=x+y+a-b\ne x+y-x\and m+a-b\ne x+y-y\).

因此,只要我们找到了一个长度为\(m\)的可行解,我们一定可以将其不断扩展到全部集合.

进一步地,我们一定能证明:原集合中的最优解是以一个长度为\(m\)的可行解作为周期的.

这个是为啥呢?我们设\(n=km+c\),那么我们直接求出一个长度为\(m\)的解,满足前\(c\)位对答案的贡献的权值是\(k+1\),后\(m-c\)位贡献的权值为\(k\),然后直接求答案.注意到如果最大答案另有其人,我们一定可以拿其中的某一段不断循环得到更大的答案,这就不符合我们的假设了.

补集转化

Example1

给定一个\(n\)个点\(m\)条边的无向图,求给每一条边定向使得\(1\)和\(2\)能到达同一个点(可以是\(1\)或\(2\))的方案数.\(n\leq 15,m\leq \frac{n(n-1)}{2}\).

考虑正难则反,算不存在的概率(事实上也确实很好理解,因为存在性问题通常都要取补集),这时候我们发现:此时\(1\)能到达一个集合\(S\),\(2\)能到达一个集合\(T\),\(S\)和\(T\)无交,并且两个集合之间不可能存在边,因此我们只需要算\(f(S)\)表示\(1\)能到达\(S\)中的点的方案数即可,\(2\)同理.

那么这个怎么算呢?我们仍然考虑正难则反,如果\(1\)不能到达\(S\)中的所有点,那么\(1\)一定只能到达\(S\)中的一部分点,枚举这一部分,假设是\(T\),就可以用\(f(T)\)算\(f(S)\)的答案.

二进制分组

Example1(loj3273)

先考虑没有插入怎么做,注意到所有的线会扫出一个空白区域:这个空白区域由一条折线围成,而所有的点都在折线外或在折线上,更进一步地,在折线外的点没有动,就是初始位置.

这启发我们分开维护,每次扫线的时候更新折线,把该扔进来的扔进来,由于折线上的点\((x,y)\),随着\(x\)的增大\(y\)不增,因此是简单维护的,用一下平衡树就行.

问题在于如何维护插入点.我们使用二进制分组,将所有点分为大小为\(0,1,2,4,\cdots ,2^k\)大小的组,当然有些组可能没被分出来.然后如果有两个大小都是\(2^k\)的组,我们暴力合并二者,得到一个还没被折线扫过的新的大小为\(2^{k+1}\)的组.

Example2(Luogu7447 [Ynoi2007] rgxsxrs)

一眼看上去和CF702F很像,但是区间操作感觉很艰难,怎么做呢?

我们对值域分块:分成\([0,1),[1,2),[2,4),[4,8),\cdots\),这样只会分成\(\log V\)段,每段内部维护平衡树来处理下标.那么对于一个\(x\),它会把后面的段全部打上一个\(tag\),有些位置要掉落到下面的段上,这个维护每个段的最小值就可以处理(最多只会掉落\(\log n\)段),问题是和\(x\)在同一块内的没有办法打tag,但这一部分一定会掉落到下面的段,一块处理.

好,下面开始思想总结:

首先,我们发现这个区间和值域都很难处理,但是感觉值域更加重要,应该是对值域做均摊(也就是类似CF702F的打tag操作和暴力修改操作分开),于是考虑到对值域分块然后内部平衡树,然后发现可以做了吧.不太清楚,也有可能只是值域分块的套路.

Luogu9069是同款思路,判一下负数.

Example3(CF1515I Phoenix and Diamonds)

俗称带修T-shirt.

做法大概是这样的:我们考虑对于每次给出的\(c\),不妨假设它在\([2^k,2^{k+1})\)这个块上,那么如果它减去了任何一个还在这个块里的数字,那就一定会掉落到下一个块中.这样就又有均摊了.

但是我们不一定能减去一个还在这个块里的数字,我们怎么做呢?

我们考虑最后的操作一定是减去若干个小于这个块的,最后有可能再减去一个这个块的,然后\(c\)就掉到了下一个块,考虑先按照价值排序,然后维护\(f_i\)表示排名在\(i\)前面且代价在更小的块中的代价和,我们要找到最靠左的小于\(c-2^k\)的\(f\),这个可以做线段树二分维护.

[IOI2021]地牢游戏 类似,但是因为是在图上做,所以把二分要改成倍增.