道路（road）
竞赛图三元环计数，答案为 \(C(n,3)-\sum_{i=1}^{n} C(du(i), 2)\)。
扫描线维护出度就好了。
图（graph）
考虑最优解是一个森林。
我们想到转到网络流维护。
尝试将图上点随机染色，白点连 \(S\)，黑点连 \(T\)，之间的边互连，这样网络流就能找到最优解。
正确率为 \(1-(1-\frac{1}{2^k})^w\)。
拼图（jigsaw）
考虑对于每个点对 \((a, b)\) 算出有多少对 \((i,j)\) 途径了这个状态。
考虑倒退，从 \((a,b)\) 到 \((a,a+b)\) 和 \((a+b,b)\)。
这东西类似 S-B-T，可以生成所有的 \(ai+bj\le n\) 且 \((i,j)=1\)。
后面就是推式子了。
钥匙（key）
等价于找半平面集，使得交全为给出的点。
找出凸包。
根据皮克定理判断即可。
排列蛤蟆（hammer）
操作不影响逆序对个数。
猜测逆序对相同且 \((1,n)\) 相对位置相同的对可以两两转换。
推性质：若存在 \((a,n,b)\)，若 \(a<b\)，则可转化成 \((b,a,n)\)；否则有 \((n,b,a)\)。
性质：存在 \(\mathcal O(n^2)\) 次操作，使得操作后 \(1\) 和 \(n\) 在序列最右。
证明：
首先有 \(1,n\) 的相对顺序不变。
假设 \(1\) 在 \(n\) 左，对于 \(n\) 考虑，当其转向时，发现 \(\min(a,b)\) 下降，则 \(n^2\) 次操作后，\(1,n\) 相邻，然后通过 \((1,n,a)\) 将 \(n\) 交换到右侧。
再是 \(1\) 在 \(n\) 右，对于 \(1\)，当其转向时，\(\max(a,b)\) 上升，则 \(n^2\) 次操作后，\(n,1\) 相邻，然后通过 \((n,1,a)\) 将 \(1\) 交换到右侧。
证毕。
我们考虑将 \(a,b\) 交换成等价类中的一个序列上，类似于双向搜索。
考虑对 \(a,b\) 都按照一种顺序，要么同时将最小值换到最后，要么同时将最大值换到最后。
考虑将最小/最大同时换到最后，然后划分成 \(n-1\) 的子问题。
若 \(a,b\) 中 \(1,n\) 的相对顺序不同，那么由 \(a,b\) 有解可以推出 \(a\) 或 \(b\) 中 \(1,n\) 的顺序可以交换（后面详细证。
假设当前是 \(n\) 在 \(1\) 左，要交换（\(n\) 在 \(1\) 右同理）。
先将 \(1\) 换到最右。
再将 \(n\) 换到次右（若 \(n\) 在 \(2\) 左，则递归计算子问题，即交换 \(2,n\) 的顺序）。
此时假设有 \(a,b,n,1,?\)。
若 \(a<b,?>n\)，可操作；
若 \(a<b，?<1\)，可操作；
若 \(a>b\)，考虑利用前面的数得到 \(a<b\)：
- \(c<b<a\)，可操作；
- \(b<c<a\)，可操作；
- \(c>a\)，递归处理
发现若无法交换，则这整个子序列是完全逆序的，\(a\ne b\) 就无解。
这样就做完了。
AT_joisc2017_d 切符の手配 (Arranging Tickets)
有点省选的味道了。
考虑先定向 \(\min(a_i,b_i) \to \max(a_i,b_i)\)。
再考虑翻转，当两个区间无交时，不能同时翻转。
则所有翻转区间交不为空，设为 \([l,r]\)。
考虑二分答案 \(lim\)。
考虑枚举 \(t\in [l,r]\)，\(b_i\) 为翻转后的计数，\(z_i\) 表示含 \(i\) 的翻转区间数。
则有 \(b_i=a_i+(z_t-z_i)-z_i\)，根据 \(b_i\le lim\)，有 \(\lceil\frac{a_i+z_t-lim}{2}\rceil \le z_i\le z_t\)。
考虑贪心从前往后 \(i\in[1,t]\) 满足条件，显然为了让 \([x+1,n]\) 满足条件，选择的区间右端点应尽量大。
于是从 \(i\) 向右做扫描线，每次加入 \(i\) 的可选端点，贪心选择可选区间中右端点最大的区间，取到下界即可，最后在判断 \([x+1,n]\) 是否合法，时间复杂度 \(\mathcal O(n^3\log m\log V)\)。
性质：在最优解中，设 \(t\) 为 \(\max_{i\in[l,r]} b_i\) 的下标，有 \(|S|=0\) 或 \(b_t \ge \max_{i=1}^{n} b_i-1\)。
证明：若 \(b_t \le \max_{i=1}^{n}b_i-2\)。
- 若存在翻转区间 \([l,r]\)，则再翻转 \([l,r]\)，\(b_t\) 加一，\(\max_{i=1}^{n}b_i\) 减一，这种情况不可能是最优解，舍。
- 否则分别存在以 \(l\) 为左端点和以 \(r\) 为右端点的不同区间，都翻转，\(b_t\) 加 \(2\)，\(\max_{i=1}^{n}b_i\) 要么变成 \(b_t\)，要么不增，不断调整，若最后有 \(|S|\le 2\)，由于不存在区间 \([l,r]\)，所以 \(|S|=2\)，继续删除，得到 \(|S|=0\)。
那么现在 \(z_t\) 的枚举量是 \(\mathcal O(1)\) 的。
性质：对于 \(t\)，同时有 \(a_t=\max_{i=1}^{n}a_i\)。
证明：设 \(y \notin [l,r]\)，且 \(a_y-a_t \ge 1\)，又由上有 \(b_t-b_y \ge -1\)，则 \(a_y-b_y \ge a_t-b_t\)，与假设矛盾。
那么现在 \(a_t\) 的值域是 \(\mathcal O(1)\)。
性质：最优解包含所有的 \(a_i\) 的最大值的位置。
证明：设 \([L,R]\) 分别表示 \(a_i\) 的最大值的最左和最右位置，假设有 \(L<l\le r < R\)，则若存在将要翻转区间不包含 \(L\)，若翻转了就会变劣，\(R\) 同理。
于是 \(a_t\) 的枚举位置是 \(\mathcal O(1)\) 的。
时间复杂度 \(\mathcal O(n\log n\log V)\)。
矩阵（matrix）
这不是gdkoi？
首先这东西有循环节，然后一个点被操作 \(2^k\) 后只会产生一个十字（五个点）的影响。
找出循环节，倍增加速即可。
修公路（road）
相交的弦连边，每个连通块构造菊花图（很妙，。
可以线段树优化建图。
序列（sequence）
类似维护最大子段和搞一搞就好了，不写。
重振旗鼓（cheer）
显然有确定链端点时的 \(\mathcal O(n\log V)\) 的做法。
考虑一叶子，先做一遍以它为端点的情况，此时他不再是端点，维护一个 \(X\)，表示已删叶子的 \(\gcd\)，将这个叶子删除，然后 \(X\gets \gcd(X,a_u)\)。
考虑优化，发现，当 \(\gcd(X,a_u)=X\) 时，\(a_u\) 直接删就行了，不需要做算法。
于是执行算法的次数是 \(\mathcal O(\log V)\) 的，于是总时间复杂度 \(\mathcal O(n\log^2 V)\)。
惊鸿照影（memory）
二分答案，相当于求圆内交点个数，映射到圆上，就是个二位偏序问题。
明月来归（return）
离线，显然 \(\mathcal O(n\sqrt m)\)。
在线，随便维护。
女巫（witch）
好题。
赛时没想清楚关于求和在取第 \(k\) 位的问题。
拆位，权值相当于前缀异或后 \(1\) 的个数乘上 \(0\) 的个数。
考虑维护虚树，显然，只会在每个子树内取一个点。
设 \(f_u\) 表示以 \(u\) 为根的虚树个数，\(g_{u,0/1}\) 表示以 \(u\) 为根的所有虚树从根往下一层异或和为 \(0/1\) 的方案数，\(h_u\) 表示答案。
考虑 \(u\) 的儿子 \(V\) 的合并，其中 \(e(x,y,k)\) 表示 $dis_y-dis_x $ 第 \(k\) 位的值。
\[f'_u\gets f_u\times (1+\sum_{v\in sub(V)}f_v)\\ g'_{u,0}\gets g_{u,0}\times(1+\sum_{v\in sub(V)}f_v)+f_u\times\sum_{v\in sub(V)}g_{v,e(u,v,k)}\\ g'_{u,1}\gets g_{u,1}\times(1+\sum_{v\in sub(V)}f_v)+f_u\times\sum_{v\in sub(V)}g_{v,e(u,v,k)\oplus 1}\\ h'_u\gets h_u\times(1+\sum_{v\in sub(V)}f_v)+g_{u,0}\times \sum_{v\in sub(V)} g_{v,e(u,v,k)\oplus 1}+g_{u,1}\times \sum_{v\in sub(V)} g_{v,e(u,v,k)}+f_u\times \sum_{v\in sub(V)}h_v \]\(a-b\) 第 \(k\) 位为 \(1\) 的 \(b\) 在两端区间内。
考虑加速，线段树合并即可。
生成树（tree）
求边集 \(E\) 的 MST，可以将 \(E\) 分成若干子集，分别求 MST 得出边，再用这些边求 MST。
考虑点分治优化这个过程，容易发现，每个分治中心将将子树划分为若干个连通块，这一层分治中需要考虑的就是合并这些连通块；发现这个过程类似 boruvka，所以直接用 boruvka 求出合并这些连通块可能用到的边，然后在外层将这些可能用到的边进行一次 kruskal 即可做到 \(\mathcal O(n\log^2n)\)。
在一个分治中心，从根开始维护前缀和 \(dis\)，则要求使 \(|dis_u+dis_v|\) 最小的 \(v\)。
将 \(dis_u,-dis_u\) 放在一起排序，答案就是不同子树的前驱后继。
子树太多不好做。
考虑上边分治，就做完了。
字符串（string）
循环同构经典问题不讲。
找规律，只需要求 \(a\)，\(b\) 内部的答案以及 \(ab\)，\(ba\)，\(bb\) 跨过中间的答案。
系数可以矩乘维护。
标签：sub,七中,max,sum,成都,2024,mathcal,考虑,times From： https://www.cnblogs.com/orzz/p/18120964