补了一些讲过的远古题和近期的 CF 2000分以上的部分题。
CF1764H
题意：有序列 \(a_n\)，初始 \(a_i=i\)，给定 \(m\) 个修改操作 \([l_i,r_i]\)，修改方式是把区间内所有数赋值成左端点的值。求修改操作在循环下，对于每一个 \(x\)，依次进行操作 \([x,x+k-1]\) 之后序列不同数的个数。\(n,m\le 2\times 10^5\)。
首先对于没有覆盖的位置，扫描线时计算答案是简单的。对于覆盖的位置，只有每个询问的左端点可能产生贡献。
产生贡献的充要条件如下：
-
设上一个覆盖左端点 \(l_i\) 的操作是 \(f_i\)，则显然当 \(x > f_i\) 时有贡献。
-
设 \(g_i\) 表示区间全被覆盖掉的最早时刻，\(v_x\) 表示 \(x\) 位置从当前开始最早什么时候会被覆盖，则有 \(g_i=\max_{k=l_i}^{r_i}(v_k)\)，更新第 \(i\) 个修改区间的覆盖也比较简单。只需要将左端点的 \(v_{l_i}\) 赋成 \(g_i\)，区间剩余部分赋成 \(i\) 即可。
CF1764G
有长度为 \(n\) 的排列，可以查询 \(query(l,r,k)\)，交互库会告诉你 \(\lfloor \frac{a_i}{k} \rfloor,i\subset[l,r]\) 的不同值数量，在 30/21/20 次询问内确定 \(1\) 的位置，\(n\le 1000\)。
考虑将 \(2x+1,2x\) 看成一个 pair，考虑统计 \(f(l,r)\) 表示满足如下条件的 pair 个数：区间内部外部个包含一个值。
这个统计是 easy 的，因为你可以用 \(query(l,r,2)\) 算出来，满足条件的 pair 个数就是 \(2\times query(l,r,2)-(r-l+1)\)。
对于 \(n\) 是奇数的情况，判断 \(1\) 是否在某个区间内，只需查询区间内，外的满足条件 pair 个数，如果内部大于外部就是这个区间，否则就是二分的另一个区间包含 1。
对于 \(n\) 是偶数，发现 \(n\) 也特殊（无配对），所以只需确定 n 的位置即可。
通过 \(query(l,r,n),l<r\) 是否大于 1，可以判断出区间是否存在 \(n\)。
于是一种 naive 的做法是二分出 \(n\)，但是发现这样不如玩原神。
其实可以正常二分过程中，发现左右区间的 pair 数都和外面相等了，就判一下 \(n\) 在哪个区间内即可。
这样就只需 21 次查询。
考虑再杀掉一次查询。
发现二分到区间长度等于二后，还需两次查询才能赢。
试图压缩成一次。
显然如果此时 \(n\) 还没有区分出来，那询问一次 \(n\) 在哪边即可。
其他情况，因为已知 \([1,l-1],[1,r],[l,n],[r+1,n]\) 的答案，通过分类讨论可以压缩一次查询。
设两个数中一个是 1，另一个是 \(x\)。
具体地，考虑设 \(g(l,r)\) 表示区间内 pair 的个数，那么显然我们二分过程中知道了 \(g(1,l-1),g(1,r),g(l,n),g(r+1,n)\) 的答案。
那么当 \(g(1,l-1)=g(1,r)\) 的时候，显然与 \(x\) 配对的另一个数在 \([1,l-1]\) 中。否则在 \([r+1,n]\) 中。
那么对于在左区间的的情况，查询一次 \([1,l]\)，判断 \(g(1,l)\) 是否恰好等于 \(g(1,l-1)-1\)，是则 \(r\) 是 1，否则 l 是 1。
在右区间的情况是类似的。
CF453E
显然颜色段均摊。首先用个 Set 维护颜色段。然后除掉 ODT，接下来的问题就是询问一段区间从 0 开始经过一段时间后的 sum。发现题目的 \(m\) 值域是 \(10^5\)，所以分块之后对于每个块预处理下每个前缀和即可。
对于初值，可以在颜色是 0 的那些段暴力扫，是 \(O(n)\) 的。
CF1789D
傻逼构造。能不能s一s啊。简单题，但是位运算和垃圾的输出方式容易把人整晕。
设前面的位是高位。那么首先判掉一些显然的特殊情况，例如 \(a=b\) 无需操作，\(b=0\)，\(a=0\) 显然无解。
剩余情况必然有解。考虑构造解。此时 \(a,b\) 都包含至少一个 \(1\)。
可以用 bitset 模拟操作。注意 bitset 操作时要随时把被 remove 掉的位干掉，避免影响答案。同时 bitset 的左移右移只能为非负。
首先设 \(mx1\) 是 \(a\) 的最高位，\(mx2\) 是 \(b\) 的最高位，那么如果 \(mx2\le mx1\)，显然是容易构造出解的。只需先通过对 \(mx1\) 的左移异或（若 \(mx1=mx2\) 不用管）将 \(a\) 的 \(mx2\) 位变成1，然后从前往后按位考虑，当前的位和 \(b\) 不相同就将最高位 \(mx2\) 拉过来异或一下，否则不管。
那么就解决了 \(mx2\le mx1\) 的情况。
剩余情况 \(mx1 < mx2\)，考虑转化成刚刚的情况。
此时如果 \(a\) 中只有一个 1，需要新开一个 1 方便操作，这个 1 要开在 \(mx2\) 的位置，这样 \(mx2\) 这位就省下了操作，保证总操作数不会大于 \(n\)。
然后取最低一位的 1，从 \(mx2-1\) 向最前面枚举，发现当前位是 \(1\) 就把最低位的 1 拉过来异或。
这样就消掉了高位的 1，转化到了上面的情况。
不难发现操作数严格不超过 \(n\)。
CF1789E
简单小数学题。
首先考虑 \(s_n\) 的因数 \(x\)，这部分显然只有 \(x|s_i\) 的 \(i\) 贡献答案，枚举一下就好了。
然后考虑其他数。做过整除分块的都知道 \(\lfloor \frac{s_n}{x} \rfloor = y\) 的 \(y\) 一共只有 \(O(\sqrt{s_n})\) 种取值。
于是做一个整除分块。然后对于一个 \(y\)，答案显然是满足 \(ay+b=s_i,b\le a\) 的 \(i\) 的个数。这部分可以预处理出值域上前缀和然后计算 \([py,py+p],p < y\) 的答案。而大于 \(y^2\) 的显然全部满足限制。
然后整除分块中可能把因数也算进去，枚举一下每个除数 \(x\) 看是否是因数，是就减掉他的答案即可。
复杂度不太会算，但是远比 \(O(\sum s_n \ln s_n)\) 小，应该是接近 \(O(\sum s_n)\) 的。
CF1789F
牛逼乱搞题。
类似于根号分治，我们考虑出现次数小于 5 的，显然这时只有出现两次和三次的是有用的（四次的被两次的覆盖了）。
那么枚举序列断点，求 LCS 即可。复杂度 \(O(n^5+n^3)\)，而且常数极其极其小。
对于出现次数大于等于 5 的，发现如果把序列劈成五部分，则最优串一定是某部分的子序列。
这时每段长度是不超过 16 的，枚举子序列暴力全串匹配即可做到 \(O(5\times 2^{\frac{n}{5}}\times n)\)。
CF1796E
首先，如果根是确定的，做法显然，只需要二分答案 \(x\) 就容易判断合法性。具体地，设 \(f_i\) 表示 \(i\) 子树内最短链的长度，则转移是 \(f_i=\min(f_v)\)，其中 \(v\) 是 \(i\) 的儿子。
若有不小于两个 \(v\) 满足 \(f_v < x\)，则直接不合法。
那么根不确定呢？当 1 不合法的时候，就是存在一个不合法的节点 \(u\)，满足 \(u\) 至少有两个儿子 \(v1,v2\)，使得 \(f_{v1},f_{v2} < x\)，那么显然你必须以 \(v1,v2\) 最短那条链的叶子节点中的任意节点为新根，若都不合法就彻底摆烂。为什么是对的？因为你用其他子树的或者子树外的，则这两棵子树内的答案必然不变，仍然是寄的。
而如果根节点的 \(f\) 小于 \(x\)，此时只需以其 \(f\) 值小于 \(x\) 的那个点对应的叶子节点检查一遍即可。
复杂度 \(O(n \log n)\)。
CF1795F
二分答案+树上贪心。
首先这种不好直接求的东西，而且满足二分性的，肯定要二分答案。先二分 1-k 这些人总共能走几步，再二分剩下一轮中 \(1-i\) 的人走一步。
考虑贪心。dfs 的过程中，我们先递归完子树，处理完子树内部的人的走步，然后考虑自己。那么显然，如果子树内走完之后剩下的树，能够向下走的步数不小于要求步数，那么直接向下走显然是优的，因为他不会影响到剩余人的走步（因为他自己就占了位，子树外的点不可能走到子树里来），而如果向下走不够，我们只能尝试向父亲走，于是过程中如果父亲被占了或者到根步数还不够，就不合法。
实现的话每个点可以打一个 tag，表示是否有人覆盖这个位置，如果是的话已经走了几步，这样就可以直接做两种二分了。
CF1795G
必然有解，于是考虑把每个点的度数减掉 \(a_i\) 之后做拓扑排序，并按拓扑序把边重定向，那么点对是好的当且仅当其不能在新的有向图上互达。于是问题就在于求可以相互到达的点对数量。
直接开 bitset 按拓扑序逆序更新可达点集合即可。但是空间开不下，于是考虑一次更新整张图所有点和 \([L,R]\) 中点的可达性，\(R-L+1\) 取一个适中的数即可。
也可以不用 bitset，改用 ull 压位，这时 \(R-L+1=64\)，但 bitset 就是 ull 压位，二者实际上是一个东西。
复杂度 \(O(\frac{n^2}{64})\)。
标签：二分,mx2,显然,即可,答案,区间,杂题 From： https://www.cnblogs.com/infinities/p/17197075.html