Trick

· · 算法·理论

From [20240922] 洗牌

对于01串做不相交区翻操作，可以再log次以内完成，每次合并相邻的一段一。

From [20240916] 序列

序列区间减归零问题除了单调栈、笛卡尔数，还应该想到差分。

From [20240908] 随机游走

期望转移中，如果存在未知量，可以用线段树记录系数，在往上合并的过程中不断消元。

From [20240928] 排列

首先对于只存在一个排列的方案数就是错排的方案数。可以转化为 \forall i,i !=p_i 的方案数。由此连边得到的一堆环的图是不存在一元环的。

sol1：容斥

2^n$ 次的情况，显然奇减偶加。但会发现，选相同个数的方案都是等价的。所以可以只用枚举选的个数就行了。时间复杂度 $O(n)

具体的：

ans=\sum_{i=0}^n [i\&1?-1:1] C_{n}^{i} \times(n-i)!

sol2：递推

除此之外，还有递推的做法，令 Dn 表示选 n 个数的错排方案数。 则有：

D_i=(n-1)(D_{i-1}+D_{i-2})

可以理解为，从1到n-1中选取1个数放到n的位置上，令其为k，将n当做k则有 D_{i-1} 种方案，此情况中，n是不能放到位置k上的，然而事实是可以的，所以在令n就在位置k上，方案数为抛开n和k的方案数，即 D_{i-2}。

两个排列时，可以先将 a_i 与 b_i 连边，因为两个排列完全不相同，所以连出来的图一定也是多个环。第i条边的信息左端点被选表示位置i上放的是 a_i，右端点被选表示位置i上放的是 b_i，两端点不能同时被选，同时不选时表示无限定。

与之前的容斥一样，我们只需要求出 i 个违反时的方案数。环内可以dp，环与环之间的贡献可以用背包加起来。总时间复杂度 O(n^2)。

由这题还可以得到的一个技巧是，二选一可转化成图论。

From [20241015] 棋盘游戏

棋盘上，当条件为每行每列只能出现一个元素的时候，可以考虑二分图。

From [20241017] 开发者选项

询问某个区间是否被覆盖可以转化为对于每个点去求覆盖它的区间。

From [20241004] 粉刷

棋盘上每次操作行或列，若要使每个点都被覆盖，一定会有其中一种操作是操作了所有的。

From [20241002] 合并数字

对于合并两个数的操作，每队合并关系可以建边，由此得到一颗树，此树的层数可能会和操作次数的多少和权值挂钩。

From [20241019] 循环涂色

每位可选元素为整数集合，求使得任意相邻两个和首尾两个不同的方案数。

有两种方法可以解决此问题，令位置有 n 个可选的集合大小总和为 S 个。

sol1 O(mnS):

其中 mn 指的最小的集合的大小，此方法容易想到，从最小的集合开始dp，每次枚举第一个元素，在最后一个元素统计答案。

sol2 O(nS):

考虑原问题是否可以容斥，当不考虑第一位时，不合法的方案就是第一个与最后一相同的方案数，也就是条件为 a_1=a_n 其余位均满足条件的方案数，发现此时有条件 a_1=a_n\neq a_{n-1}，那么当删去最后一个元素时，前 n-1 个便成了一个新的环，可以发现此时 a_1 可以选的元素为 1 与 n 都能选的数。

形式化的，令 f(s_1,s_2,...,s_n) 为答案， g(s_1,s_2,...,s_n) 为不考虑首尾的方案数。有：

f(s_1,s_2,...,s_n)=g(s_1,s_2,...,s_n)-f(s_1\cap s_n,s_2,...,s_{n-1})

可以递归处理。

这两部分结合起来就可以在 O(S\sqrt n)的时间复杂度内完成。

From Prufer序

给定每个数的度数，构建原树。因为有\sum_{i=1}^nd_i=2n-2，且可以将一条连边转化为对于两个数加一。

所以可以每次取出度数最大的两个数，将它们连一条边，然后将它们的度数减一，此操作可以用堆实现。证明可以看一些结论中的第一个。

From [20241109] 最大独立集

对于询问 \sum_{l=1}^n\sum_{r=l}^nf(l,r) 的题大概总结为三种方法：

sol1 扫描线:

移动右端点带来的影响如果好计算的话就可以枚举右端点，左端点数据结构维护。时间复杂度 O(nlogn) 。

sol2 矩阵：

矩阵每次需要完成的是从上一位到这一位的转移，累计答案，和新增一个起点，但是有取 max 的操作就没有那么好算，但是可以支持修改操作。时间复杂度 O(nm^2)。

sol3 cdq分治：

对于cdq分出来的左右区间，当左端点在左区间右端点在右区间时，是可以覆盖所有区间的。考虑cdq是否能做就是看 f(l,r) 拆分成首尾两端时是否好合并，然后对于一个右端点计算左边所有左端点答案的和。时间复杂度 O(nlog^2n)。

upd on 20250108

sol4 整体二分

From [Ynoi Easy Round 2021] TEST_152

关于区间段覆盖问题，代码用set维护可以这样写，时间复杂度 O(nlogn)。

inline auto split(int pos){
    auto it=s.lower_bound((node){pos,0,0}); 
    if(it->l==pos)return it;
    it--;
    int l=it->l,r=it->r;
    ll x=it->x;
    s.erase(it);
    s.insert((node){l,pos-1,x});
    return s.insert((node){pos,r,x}).first;
}
inline void ins(int l,int r,int x){
    auto itr=split(r+1);
    auto itl=split(l);
    //现将 l,r+1 点作为断点，使得删除的都是整区间 
    for(auto it=itl;it!=itr;it++){
        ll nl=it->l,nr=it->r,nx=it->x;
        删除当前 [nl,nr] 区间的影响 
    }
    s.erase(itl,itr);
    //删除 [l,r] 之间的区间 
    s.insert((node){l,r,x});
    加入当前 [l,r] 区间的影响 
}

upd2024.12.1 :意识到这就是ODT。

From 「CEOI2019」魔法树

对于形如：

dp_{u,j}=dp_{u,j}+max_{k=1}^jdp_{v,k}

的树上问题转移。可以用线段树合并完成。新加入的 v 为一个前缀最值，可以用一个变量记录，因为线段树访问叶子的顺序也是从左至右，所以可以在合并过程中维护前缀最值。

From ARC187 B-Sum of CC

对于存在多种序列，每种序列的权值为划分区间的个数，求所有序列的全职和的问题可以转化为求所有对于 i 和 i+1 属于同一个区间的序列个数，当 i 和 i+1 不属于同一个区间时，相当于对于答案新贡献了一个区间。

From [20241113] 排列计数

对于一个排列重拍，计算其任意两个相邻下标数值不相邻的个数。考虑容斥，首先会想到求分别有 k 个位置不满足条件（ |a_i-a_{i+1}|=1 ）的方案数，目标状态为 k=0，然后就可以通过 (-1)^i 的容斥系数计算答案。但是会发现，对于相邻两个下标，若都不满足要求方案数就不好统计。发现对于一段连续的不满足要求的数，在确定元素的条件下，它只有一种或两种方案，当 len （连续段长度）>1 时，它可以有单调递增和递减两种可能。所以可以将容斥改为求有 k 段不满足条件的方案数，其余不变即可。

From [20241113] 冒泡排序

对于求所有权值和的问题，可以改成求大于 1 元素个数 + 大于 2 元素个数 + ……。相当于对于问题从竖向的算每一列变成很想算每一行。

From [20241119] 标号

对于一个联通图，删去一个边集，使两点不联通。可以从其中一个点跑一边最短路，然后可以发现对于与起点距离相同的点，删去这些点连出去的顺向边以后，到终点一定不联通，考虑反证，若删去以后终点所在点集与起点所在点集有连边，那么一定存在一条路径上，存在当前点权的 点能连向终点。

From [20241123] 挑战 RSA

对于 n=pq 的信息，若其差或和存在一定关系，尝试构造 n=pq=(a+b)(a-b)=a^2-b^2 可以有关系式 a^2=n+b^2，观察到此函数为凸，所以枚举 a 会优于枚举 b 。

From 【AC自动机】背单词

关于暴力定期重构的除了每 \sqrt n 次重建以外，还可以动态维护一颗线段树。

From QMT3

对于两颗子树的并的信息，除了用线段树合并维护另一颗树的dfs序以外，还可以转化成两个偏序条件，用cdq来做。

From [20240227] 隧道

对于求解最短路径过程中存在一种包含很多数的操作，可以每次取特殊操作维护的极值和堆维护的极值取更优的作为当前更新节点。例如此题结合了堆与李超树，注意要支持删除操作。

From [20250226] 位运算

维护一个 f[x][s1][s2] 表示原本 popcnt=s2 ，\&x 下 popcnt=s1 个数的桶，时间复杂度为 O(nlog^3n)


    for(int step=0;step<li;step++){
        for(int i=0;i<1<<li;i++)for(int j=0;j<=li;j++)for(int k=0;k<=li;k++)g[i][j][k]=f[i][j][k];
        for(int i=0;i<1<<li;i++){
            for(int j=0;j<=li;j++){
                for(int k=0;k<=li;k++){
                    if((1<<step)&i){
                        f[i][j][k]=g[i][j][k-1]+g[i-(1<<step)][j][k];
                    }else{
                        f[i][j][k]=g[i][j][k]+g[i+(1<<step)][j][k];
                    }
                }
            }
        }
    }

From 20250310 ARC194 B

关于使用交换操作使得序列有序求代价，可以考虑每个逆序对贡献。

From nkoj8316 买酒卖酒

对于一个最大流模型，可以转化为求解它的最小割划分，用动态规划的方法，求出点集划分最小代价。

注意：原问题可能是求解最大值，通过转化之后就是求解最小值。

From nkoj9943 出好题

莫队中对于一个数的变化值只有1，所以处理形如 \le k 的所有询问都可以在 O(1) 的时间复杂度修改查询。

From nkoj9946 易碎树

对于分别维护了直径的两颗子树合并时，新的直径端点一定是其中组合而成。

From 20250620 abc

\sum _{i=1}^n \sum _{j=i}^n max-min

可转化成：

\sum _{i=1}^n \sum_{j=1}^n max

From 20250623 Żelki

对于类似完全背包的问题，可以把转移建边，最短路即为答案。