UOJ #665 【IOI2021】registers
奇奇怪怪 pia pia sila sila 题目，不知道补得有啥意义所以干脆不补（或者说等以后有时间再慢慢啃这种题目吧
UOJ #664 【IOI2021】dungeons
考虑一个关键性质：打死一个怪以后，英雄的体力值会增长怪物的血量，也就是说，如果英雄打死了一个和自己势均力敌的怪物，那么其血量会成倍增长。
发现了这个性质之后，我们考虑对权值分层，即设第 (i) 层表示血量区间 ([2^i,2^{i+1}))，假设现在英雄血量位于第 (i) 层表示的区间，那显然血量 (<2^i) 的怪都可以被英雄秒掉，而对于血量 (ge 2^i) 的怪，我们不知道其是否能被英雄打败，因此我们考虑这样的策略：先假设它们都不能被英雄打败，这样每次英雄经过血量 (<2^i) 的房间就会获得 (s_j) 的血量并到达房间 (w_i)，经过血量 (ge 2^i) 的房间就会获得 (p_j) 的血量并到达房间 (l_i)。我们考虑对此做倍增，即设：
- (to_{i,j,k}) 表示在第 (i) 层，从 (j) 开始，每经过一个血量 (<2^i) 的怪都到达 (w_i)，经过一个 (ge 2^i) 的怪都到达 (l_i)，这样走 (2^k) 步后会到达哪个房间。
- (sum_{i,j,k}) 表示在第 (i) 层，从 (j) 开始，每经过一个血量 (<2^i) 的怪都积累 (s_i) 的血量，经过一个 (ge 2^i) 的怪都积累 (p_i) 的血量，这样走 (2^k) 步后血量会增加多少。
- (mx_{i,j,k}) 表示在第 (i) 层，从 (j) 开始，初始血量至多为多少，才能保证在接下来 (2^k) 步中打不败任何一个 (ge 2^i) 的怪。
上面三个数组都可以在预处理时候求出。这样每次查询时，每进入一层，就倍增找到后面第一个可以打败的血量 (ge 2^i) 的怪，根据上面的推论，打掉这个怪之后肯定会进入下一层，因此总复杂度 ((n+q)log^2n)，由于 (n) 较大，直接这样做会 MLE，不过注意到 (q) 很小，因此考虑 (B) 进制倍增，这样复杂度变为 (nlog_Bnlog_2n+qBlog_Bnlog n)，取 (B=8) 可以通过。
UOJ #671 【UNR #5】诡异操作
首先考虑一个比较朴素的暴力：操作 1 显然可以 seg-beats，也就是按照区间 sqrt 区间求和的套路，每次递归到一个区间时如果区间中所有元素都为 (0) 则 return。而对于 (2) 操作，我们在线段树上每个节点维护一个长度为 (128) 的数组 (b_0,b_1,cdots,b_{127})，其中 (b_i) 表示这个区间中有多少个数在这一位上为 (1)，然后修改就直接将对应位上是 (0) 的位置改为 (0) 即可。算下复杂度，每个点最多被 and 的次数为 (log v)，而每次 and 最多对应 (log v) 次除法，而 (2) 操作复杂度显然是 (log nlog v)，因此总复杂度 (nlog^2v+qlog nlog v)，一脸过不去的样子。
考虑优化，我们注意到如果一个节点比较靠近叶子，那么这个长度为 (128) 的数组中，肯定几乎所有数最高的那些位都是 (0)，因此我们考虑将数组置换一下，即对于线段树上长度为 (L) 的区间，改维护一个长度 (L) 的数组，其中第 (i) 位表示等于 (sumlimits_{j=0}^{127}b_jtext{ 的第 }itext{ 位}·2^j)，合并就类别带进位的加法。这样我们 (2) 操作复杂度变为 (log^2n)，而 (1) 操作向下搜索的复杂度可以用 (log v·sumlimitslog len) 来计算，后面的 (sum) 的时间复杂度递推式为 (T(n)=T(n/2)+log n)，根据主定理可知 (T(n)=mathcal O(n))，于是总复杂度就变为 (nlog v+qlog^2n)，可以通过。
需要卡常。
UOJ #604 【UER #9】赶路
好久之前做的了，讲到这道题时我甚至连题意都忘了
大体思路就是分治，每次分治一个集合 (S) 以及两个点 (x,y)，递归地解决从 (x) 出发经过 (S) 中点到达 (y) 的位置，分治中途就取出最终间的点 (z)，然后对 (S) 中其他点 (p)，以直线 (xz) 为分界线，如果 (xp) 和 (xy) 在同一侧就放到右侧，否则放到左侧，容易证明其正确性。
CF1208H Red Blue Tree
又毒瘤又 nb 的 DS，今天大概是没时间了，以后有时间一定优先补这道题并单独写题解（
CF1083C Max Mex
又是一道很久之前过的题目，大概就线段树上 ([l,r]) 的区间维护包含 (lsim r) 中所有的点的最短路径，然后线段树上二分，找到最后一个满足存在一条路径覆盖了 (0sim i) 中所有点的 (i)，合并可以通过 ST 表求 LCA 做到 (mathcal O(1))，时间复杂度 (nlog n)。
CF566C Logistical Questions
https://www.cnblogs.com/ET2006/p/Codeforces-566C.html
数据结构 1
不知道原题，鸽了（
数据结构 2
不知道原题 (times 2)，鸽了（
Codeforces Gym 102979K Knowledge Is...
首先这种题好像没法直接建出来图来跑什么东西解决，因此只能从特殊连边方式入手采取贪心的方式解决问题。我们将所有区间按左端点从小到大排序，那么不难发现当我们尝试匹配一个区间 ([l_i,r_i]) 时，如果存在一个候选集合中的区间能与之匹配，我们肯定会贪心地选择能匹配的区间中右端点 (<l_i) 且最小的，这个显然可以 set 维护。
直接按照上面的方式写大概可以获得 WA on test 6 的好成绩，考虑如下 hack：
4
1 2
3 5
4 7
6 8
原因在于你选择将 ([1,2]) 与 ([3,5]) 匹配后就将这个区间固定下来了，实际上 ([4,7]) 也能匹配 ([1,2])，但其不能与 ([6,8]) 匹配，而 ([3,5]) 匹配，也就是说实际上 ([4,7]) 与 ([1,2]) 匹配更加能够尽可能用完右端点大的区间，因此我们考虑加个反悔的元素：我们将所有已经匹配的区间对中较右的再扔进一个 set，如果一个区间 ([l_i,r_i]) 不能匹配候选集合中的区间，我们就考虑反悔集合中右端点最小的区间 ([L,R])，如果 (R<r_i) 我们就用 ([l_i,r_i]) 匹配 ([L,R]) 匹配的区间然后将 ([L,R]) 加入候选集合。
时间复杂度 (nlog n)。
Codeforces Gym 102586L Yosupo's Algorithm
首先考虑最暴力的做法：枚举可以匹配的点对，假设第 (i) 个点对的两个点的横坐标分别为 (a_i,b_i)，那么我们将 ((a_i,b_i)) 看作二维平面上的一个点，问题就转化为二维数点，离线 + 树状数组解决。
考虑优化，注意到我们将所有 (mathcal O(n^2)) 个点对都存下来有点浪费，因此考虑删除一些无用点对。我们考虑将所有点按 (y) 坐标排序后分治，分治到区间 ([l,r]) 时，设 (mid=dfrac{l+r}{2})，那么有这样一个性质：对于 ([l,mid]) 中的红点 (i) 和 ([mid+1,r]) 中的蓝点 (j)，点对 ((i,j)) 是有用的当且仅当 (i) 是 ([l,mid]) 中红点权值最大的，或者 (j) 是 ([mid+1,r]) 中蓝点权值最大的。
证明异常容易的，考虑反证法，假设对于 ([l,mid]) 中的红点 (i) 和 ([mid+1,r]) 中的蓝点 (j)，点对 ((i,j)) 是 ([L,R]) 询问的最优答案，但 (i) 不是 ([l,mid]) 中红点权值最大的，且 (j) 不是 ([mid+1,r]) 中蓝点权值最大的，那么我们考虑 (i,j) 在不在 ([L,R]) 中的状态，显然它们要么同时在 ([L,R]) 中要么同时不在，考虑 ([l,mid]) 中权值最大的红点 (X) 以及 ([mid+1,r]) 中权值最大的蓝点 (Y)，如果 (X,Y) 在不在 ([L,R]) 中的状态至少一者与 (i(j)) 相同，那么我们把其中一个点换成这个点答案肯定最大，否则 (X,Y) 关于 ([L,R]) 肯定相同，它们肯定会对答案产生更大的贡献。
这样点对数就降到了 (nlog n)，时间复杂度 (nlog^2n+qlog n)。
P6580 [Ynoi2019] 美好的每一天~ 不连续的存在
没听懂，先鸽着（
转载请注明原文链接：2022.1.24 WC2022 skip2004 讲课题目