2022 2.8-2.11学习笔记_p4681[thusc2015]平方运算
赞
踩
用作个人记录。
2021.12.18
C1766 【插头DP】
- 过程:换行时舍去不合法的状态；实质是维护轮廓线的状态。对接下来要连线的地方进行预判（表现为插头有或无）。
- 初状态：dp[0][m][0]=1
- 末状态：此题为完成填充，即最后一个格子（可以打标记，也可以障碍格转移）
- 转移：可以正推，也可以逆推 都要判断当前格子是否合法
C1767【插头DP】
延续了模板的思路，多了一种状态 用四进制会更快
-进制怎么处理好？
-如何快速写出下一个状态？
C1769【连通性】
引进了连通性的概念，如何维护？
2022.2.8 数据结构
P4681[THUSC2015]平方运算 【线段树】【复杂度分析】
思路：由于平方后产生的数具有周期性（我的理解：因为这是有穷个，哪怕多，最终一定会落回来），所以对于数据，可以分两步处理：
第一步，暴力走完周期前面的路；
第二步，批量处理周期后面的路。
对于第一步，暴力打表发现其不会超过常数级别的步数。故复杂度为O(11n)左右
对于第二步，同样打表找环取最小公倍数，得最大的最小公倍数不会超过60。所以后续更新的复杂度为O(60logn) o...这么说最好还是分开处理一下，还是能节约时间的
但是，怎么知道什么时候要暴力处理，什么时候可以批量处理？
考虑维护以下几个信息：
tag[N << 2] 维护此区间内的每个单点是否已经全部进入周期（用于知道暴力or批量）
sum[60][N << 2] 维护区间和，sum[0][i]为初始状态（用于查询）
pos[N << 2] 维护当前区间处于自己维护的sum内哪一个位置（用于查询）
lt[N << 2] 懒标记，维护当前区间被推进了多少周期
（zq[N << 2]（非必要，优化常数可用：维护该区间所有点周期的最小公倍数）
再结合数据结构时刻保证数据处于最新状态的特点，思考每个操作要如何进行：
#define lc id<<1
#define rc id<<1|1
- PushUp操作
需要把子区间合并到父区间：
tag[id] = tag[lc] & tag[rc];
int x = zq[lc],y = zq[rc];
if(tag[id]){
pos[id] = 0;
for(int i = 0;i < zq[id];++i,x = (x + 1) % zq[id],y = (y + 1) % zq[id])
sum[i][id] = sum[x][lc] + sum[y][rc];
}
else
sum[pos[id]][id] = sum[x][lc] + sum[y][rc];
- 叶子节点修改——Check
pos[id] = 0;
if(iszq[sum[pos[id]][id] == true){
zq[id] = c[sum[pos[id]][id];
for(int i = 1;i < zq[id];++i)//也可以在循环时统计zq
sum[i][id] = sum[i - 1][id] * sum[i - 1][id] % P;
}
- 建树操作
叶子节点：读入值，check
合并
- 修改操作
若全包含于目标区间
若tag[id] pos[id] = (pos[id] + 1) % zq[id],lt[id] = (lt[id] + 1) % zq[id];return;
否则直到叶节点再推进一步并check
要PushDown
PushUp
- 查询操作
已经保证信息是最新的 所以：把sum[pos[id]][id]的值返回就好了 途中要PushDown
P1198 [JSOI2008]最大数 【线段树模板题】
注意：
线段树中的范围：s <= mid t > mid (不可以用else)
s <= l && r <= t 是当前区间包含于询问区间中
读入：用scanf(“\n”)过滤空字符！
2022.2.9
CF679E Bear and Bad Powers of 42 【线段树】【复杂度分析】
维护三种操作：单点查询、区间赋值、区间加直到区间内没有42的幂次。
目标信息：单点的值
- 纯暴力做法：每次都加。最坏抵达O(N²) 无法承受
- 考虑42的幂次不超过某个常数，问题转化为如何维护区间内是否加爆。考虑如果加爆，必然是跟下一个42的幂次之差＜0，所以只需维护区间内幂次差的最小值即可。当出现＜0时，向下update，向上pushup。时间复杂度为(nlogn)
- 考虑赋值操作对复杂度的影响。赋值之后，该区间可以“同生死”，因此只要统一打一个tag即可。为不影响复杂度，以后进行区间加时，区间加的tag要给赋值的tag。（因为赋值可以不向下，在此就可以计算出新的min差值 若区间加，考虑到下面的min分布不定，就一定要向下更新才行）
- 解决。
P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并 【线段树合并】【差分】
思路：树上区间加问题，考虑差分。4倍单点修改的复杂度，空间开4nlogn才可。线段树合并可类比fhq treap。之后pushup。
易错：求lca时倍增更新的是v的父亲。
2022.2.10
P3373 【模板】线段树 2 【线段树】
注意点：
1.乘法的lt初始值应当赋为1。
实质：lt的初始值应当是操作之后保持不变的东西，并且能够跟val进行同样的操作。（之前的%P也是类似的思想）
2.读入时也要%P
P7453 [THUSCH2017] 大魔法师 【线段树】【矩阵乘法】
直接把矩阵放在线段树上即可。
注意点：线段树的lazytag应为bas矩阵（对角线）
莫比乌斯反演，询问拆成4个（该思想很重要！形如矩阵的询问也常用到）
则问题转化为1-n 1-m，转化为μ× 1，两次变换枚举顺序，整除分块即可
P2257 YY的GCD 【数论】【莫比乌斯·优化】
本题新增了gcd为质数的约束条件。
常见的优化方法：记kd = T，将T提前，发现最后一项可以预处理。
P1390 公约数的和 【去重】
两倍，去重即可
P2568 GCD 【数论】【欧拉函数】
区别于YY的GCD，本题相当于只有一组询问，预处理反而使得复杂度增大。
化为：对于n内所有质数k，n / k内所有互质的数的对数
欧拉函数的定义：小于i,且与i互质的数的个数。
故预处理出欧拉函数，求出前缀和，对于所有质数将2φ(n / k) - 1计入答案即可。
P3810 【模板】三维偏序（陌上花开） 【CDQ分治】
易错点：排序。sort中不能有交换之后始终成立的条件。
2022.2.11
P3157 [CQOI2011]动态逆序对 【CDQ分治】【去重】
注意：CDQ分治一次只能统计单方向：即 <= 或 >= 的数量
如果需要两个方向，需要两次CDQ分治。
本题相等的只能计算一次，故还需要去重。
此外，树状数组不能有0，需要统一 +1 。
P4027 [NOI2007] 货币兑换 【CDQ分治】【动态规划】【斜率优化】
打完这道题终于弄懂斜率优化了
是那种“无需题解，我能证明我一定是对的”的感觉
很快乐！
让我们先推一下式子：
设f[i]表示到第i天时，以当天的汇率最多能兑换到的A券数量，ans表示过程中的最大人民币。
（疑问：为什么一定要是当天的汇率？不能是之前天的汇率留到现在的A券数量吗？其实也有统计 如果不是ans转移过来的就相当于是直接留到现在）
【动态规划的原则：涵盖所有状态，要求不漏但不要求不重】
f[i] = max(ans, max(j ∈ [1, i) )
{f[j] * a[i] + f[j] / rt[j] * b[i]}) * rt[i] / (rt[i] * a[i] + b[i])
令g[j] = f[j] / rt[j]，若决策点f[j]比f[k]优（设f[j] < f[k])则
(f[j] - f[k]) * a[i] + (g[j] - g[k]) * b[i] > 0
即 Δg/Δf < -a[i] / b[i]
显然这是一个有关斜率的式子，考虑斜率优化。
假设f保持有序，用栈维护时，当且仅当s[top]与s[top - 1]的斜率≥-a/b时，s[top]为最优点，故维护斜率递减的凸壳。新插入点时，不满足则剔除栈顶。
同时，秉承“这里抛弃的下次再也不可能用到”的原则，当栈顶因为斜率<-a/b而被抛弃时，它再也不可能被用到。所以-a/b应该递增。
考虑如何使f及-a/b单调。
发现这是三维偏序的问题。
第一维：i < j；第二维：f[i] <= f[j] 第三维：-ai/bi≤-aj/bj
考虑CDQ分治。
由于第一维很好判断属于[l, mid]还是(mid, r]，只需要线性的复杂度，且第三维是一开始就知道的，所以预处理第三维。
在分治的过程中，人工判断左或者右（循环，借用tmp数组），并继续分治左边。结束后，更新右边的答案，并分治右边。最后归并排序。
当抵达终点(l == r)时，注意不能直接返回！
根据前面的分析，我们只统计了“当天售出，当天买入”的A券数量（或者说直接留到当天），而没有统计“之前售出，当天买入”的A券数量。这会导致A券数量始终是第一天的数量。所以需要继承上一个的答案。
此外，由于分治过程中有可能出现ans在它后面的情况，也不能用全局变量。只能在抵达终点时继承。
完结撒花！
转化之后就是三维偏序问题啦。要注意的是当x相等时，应该让修改优先。
