猫树分治
猫树，整体二分与线段树分治的结合，前者我快忘了，后者更是学都没学过 www。 说人话，就是一种不支持修改，仅仅支持快速区间询问的一种静态线段树。构造要执行 O(nlogn)O(n\log n)O(nlogn) 次合并操作，而查询可以加速到 O(1)O(1)O(1) 次合并操作。 猫树问题可以适用于离线解决以下类型的数据结构问题： 与序列有关，且询问是一段区间。 序列静态，即，不涉及修改操作。 当然离不离线都可以，由于其过程类似于点分治，所以在线的情况可通过类似于建出建出点分治的情况动态维护。 我们通过一道例题来进行引入： 给你一个长为 nnn 的序列 aaa，有 qqq 次询问，每次询问区间 [l,r][l,r][l,r] 的最大值和最大值个数，可以离线。 1≤n≤2×105,1≤q≤7×106,1≤l≤r≤n,1≤ai≤1091\le n\le 2\times 10^5,1\le q \le 7\times 10^6,1\le l\le r\le n,1\le a_{i}\le 10^91≤n≤2×105,1≤q≤7×106,1≤l≤r≤n,1≤ai≤109。 显然...
MatrixTree矩阵树定理
0. 前言 前置知识：行列式。 我已经 500 万年没写过这个笔记了，赶紧抽空写一个。 1. 生成树计数 1.1 无向图不带权 我们对于无向图，定义 DGD_{G}DG 表示图 GGG 的度数矩阵，即： DG(i,j)={degi(i=j)0(i≠j)D_{G}(i,j)= \begin{cases} \text{deg}_{i} & (i=j) \\ \\ 0 & (i\neq j) \end{cases} DG(i,j)=⎩⎪⎪⎨⎪⎪⎧degi0(i=j)(i=j) 还有邻接矩阵，这里就不解释了，不过需要注意的是如果有重边的话应该算有多少条。 同时介绍 Kirchhoff 矩阵，指的对于一个图构造出来的一个矩阵。具体定义为度数矩阵减去邻接矩阵。 矩阵树定理说的是，一个图中的生成树个数等于其 Kirchhoff 矩阵的任意一个 代数余子式的行列式，说人话就是对其矩阵任意一个 n−1×n−1n-1\times n-1n−1×n−1 的子矩阵求行列式，注意如果直接对 n×nn\times nn×n 求行列式答案为 000，因为一个图的 Kirch...
abc423题解
省流：ABCDEF，G 感觉有点难了而且慢速选手无法完成 www，rk280。 A,B,C 略去，不过这里需要特别提醒一下 C 题，显然有结论，就是我们锁上门后显然不会再打开，否则一定不优，开操作和闭操作各自至多进行一次。要能够把所有门都变为锁状态的充要条件是：在完成所有开操作之后，仍然处于打开状态的锁的编号集合必须是形如 {i∣X≤i≤Y}\{i\mid X\le i\le Y\}{i∣X≤i≤Y} 的一个连续区间（并满足 X≤R,;R−1≤YX\le R,;R-1\le YX≤R,;R−1≤Y）。令 Li=0L_i=0Li=0 的最小下标为 xxx、最大下标为 yyy。当 x≤R−1x\le R-1x≤R−1 时，只需进行使得门 x,x+1,…,R−1x,x+1,\dots,R-1x,x+1,…,R−1 的钥匙全部打开的操作；当 y≥Ry\ge Ry≥R 时，只需进行使得门 R,R+1,…,yR,R+1,\dots,yR,R+1,…,y 的钥匙全部打开的操作，也可以暴力模拟，时间复杂度 O(n)O(n)O(n)。 D 用一个堆维护当前在餐馆内的人，模拟即可，时间复杂度 ...
整体DP—从勤拿少取到量大管饱
0. 前言 这可能是全网比较全面的整体 DP 思想叙述？话说回来到底什么是整体 DP 啊嘞？ 你在做 DP 题的时候。如果熟练的话，常常会写出正确的 DP 方程，却因为状态太多或过多的重复转移而超时。而整体 DP 的思想就是一种化繁为简的思路，我们把原本需要逐个处理的状态或子问题，放进一个整体里批量处理。本蒟蒻遇到的情况大致可以分为以下两类： 转移整体化：将逐点更新的转移，通过改写转移方程，转化通过数据结构上的批量操作替代逐点枚举，用数据结构一次性完成转移从而达到复杂度的优化。 多次转移合并：将多次重复的转移，转化为不再对每个问题单独求解，而是把所有子问题作为整体嵌入同一个 DP 过程。 上述的所有过程，都体现整体 DP 的思想中的核心——整体：用一次整体操作代替多次操作，避免重复计算。 想这些概括的词很累的呜呜呜。 1. 转移整体化 1.1 概述 转移整体化是什么呢？你看上面不说人话的大范围概括，其实就是通过类似数据结构维护序列的方式将 DP 状态中的一维压入数据结构，并通过批量操作（整体修改、整体查询）优化。其中最常见的就是线段树合并优化转移。 同时不难发现，我们由...
bitset大肘子
0. 前言 1234567891011121314151617181920212223//整数，string和char数组可以强制类型转换成bitset//不支持迭代器//类似string，可以存入unordered_set/map，可以用cin/cout输入输出//转化为整数时0为最低位，转化为字符串时顺序与原先顺序相同，输出时从高位到低位输出bitset<N>b;//定义初始值全为0的bitset，N为整型常量bitset<N>b(x);//用无符号整型x初始化bitset，不超过unsigned long long范围bitset<N>b(s);//用s初始化b，s可以是basic_string类型或bitset类型，若为basic_string类型则s中只能包含'0'或'1'bitset<N>b(s,p);//用s从p位置开始到末尾初始化b，此处s只能为basic_string类型，下同bitset<N>b(s,p,n);//用s从p开始的n个数初始化b，p和n都是整数b...
ABC422题解A-F
省流：20:50~22:00 短时场 A 暴力模拟即可 B 每个点暴力判断即可，写挂了 1 次 C 没脑子写二分，有脑子猜结论，上界显然是 min{na,nb}\min\{n_{a},n_{b}\}min{na,nb}，下界不太好，因为下界和这个能够分配的数量有关，设数量为 xxx，那么显然答案必定为 na−x+nb+nc−x≥xn_{a}-x+n_{b}+n_{c}-x\ge xna−x+nb+nc−x≥x，那么显然 na+nb+nc−2x≥xn_{a}+n_{b}+n_{c}-2x\ge xna+nb+nc−2x≥x。显然有 x≥nA+nB+nC3x\ge \dfrac{n_{A}+n_{B}+n_{C}}{3}x≥3nA+nB+nC。上下界有了知道咋做了吧。 D 你猜为什么给你 2n2^n2n？ 你倒着操作，每次操作肯定是 2n2=2n−1\dfrac{2^n}{2}=2^{n-1}22n=2n−1 啊，这些部分相当于子问题分治的结构，再翻译一下就是完全二叉树的结构，根节点点权为 kkk，你要在遍历每一层的时候通过合理均分当前点点权到两个...
Kruskal重构树学习笔记
1.算法简介 我们回忆一下 Kruskal 求最小生成树的过程，可以表述为以下： 将边按照边权从小到大进行排序。 若当前边 (u,v)(u,v)(u,v) 两端不连通，我们就在生成树的边集中加入这条边并连接 (u,v)(u,v)(u,v)，关于连通性显然我们可以考虑利用冰茶几维护。 有的时候，我们可能想要求得信息就和边权的大小关系有关，例如路径上的最大边权和最小边权，你可能会想到使用最小生成树，但是问题在于最小生成树上的边权是乱序的，但是我们发现在构建的最小生成树的过程就可以解决这个路径上最大边权和最小边权问题。 如果能用某种结构描述每条边被连接的先后顺序就很好了，因为越往后加入的边权就越大，就可以快速刻画边权有限制的图连通性了。 于是我们就有了 Kruskal 重构树！它在 Kruskal 的过程上进行了一些改进： 将边按照边权进行排序。 若当前边 (u,v)(u,v)(u,v) 两端不连通，连接 u,vu,vu,v 的时候找到 u,vu,vu,v 的代表元 U,VU,VU,V。新建节点 ccc，将并查集中 U,VU,VU,V 的父亲设为 ccc，并在图上连边 c→Uc...