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\) 进制倍增，这样复杂度变为 \(n\log_Bn\log_2n+qB\log_Bn\log 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 n\log v\)，因此总复杂度 \(n\log^2v+q\log n\log v\)，一脸过不去的样子。

考虑优化，我们注意到如果一个节点比较靠近叶子，那么这个长度为 \(128\) 的数组中，肯定几乎所有数最高的那些位都是 \(0\)，因此我们考虑将数组置换一下，即对于线段树上长度为 \(L\) 的区间，改维护一个长度 \(L\) 的数组，其中第 \(i\) 位表示等于 \(\sum\limits_{j=0}^{127}b_j\text{ 的第 }i\text{ 位}·2^j\)，合并就类别带进位的加法。这样我们 \(2\) 操作复杂度变为 \(\log^2n\)，而 \(1\) 操作向下搜索的复杂度可以用 \(\log v·\sum\limits\log len\) 来计算，后面的 \(\sum\) 的时间复杂度递推式为 \(T(n)=T(n/2)+\log n\)，根据主定理可知 \(T(n)=\mathcal O(n)\)，于是总复杂度就变为 \(n\log v+q\log^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]\)​ 的区间维护包含 \(l\sim r\)​ 中所有的点的最短路径，然后线段树上二分，找到最后一个满足存在一条路径覆盖了 \(0\sim i\) 中所有点的 \(i\)，合并可以通过 ST 表求 LCA 做到 \(\mathcal O(1)\)，时间复杂度 \(n\log 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]\) 加入候选集合。

时间复杂度 \(n\log 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]\) 肯定相同，它们肯定会对答案产生更大的贡献。

这样点对数就降到了 \(n\log n\)，时间复杂度 \(n\log^2n+q\log n\)。

P6580 [Ynoi2019] 美好的每一天~ 不连续的存在

没听懂，先鸽着（