ds 合集的 Part 2，此合集包含分治问题和位问题。
分治问题
CF452F
枚举 \(i\)，考虑差为 \(k\)，即 \(a_i - k,a+k\) 是否在不同的两侧。把在 \(i\) 前面的 \(a_j\) 设为 \(1\)，就是要找以 \(i\) 为中心半径在 \(\min(a_i,n-a_i + 1)\) 的串是否是回文串。线段树维护即可。复杂度 \(\Theta(n\log n)\)。
CF480E
倒序加点处理，设 \(f_{i,j}\) 为 \((i,j)\) 能往上走几步，\(g_{i,j}\) 往下。每次加点 \((x,y)\) 只会影响 \(f_{i,y},g_{i,y}\)，可以 \(\Theta(nk)\) 修改。考虑每次对答案的增加，显然是枚举 \(x\) 这一行，然后 \([l,r]\) 合法当且仅当 \(\min\limits_{k\in [l,r]} f_{x,k} + \min\limits_{k\in[l,r]} g_{x,k} - 1 \ge r - l + 1\)。由于答案是单调的，所以直接枚举上次答案 \(ans+1\)，作为 \(r-l+1\)，做一个滑动窗口就行。复杂度 \(\Theta(nk)\)。
CF549F
考虑分治，枚举最大值的一边，设最大值在左边，那么枚举 \(i\)，也就是问有多少个 \(j\) 满足 \(j\in [mid+1,r],sum_{mid} - sum_{j} \equiv sum_{mid} -sum_{i-1}-\max\limits_{p\in[i,mid]} a_p \pmod{k}\)，可以考虑双指针实现。复杂度 \(\Theta(n\log n)\)。
CF750E
考虑 \([1,n]\) 怎么做，设 \(f_{i,0/1/2/3/4}\) 为前 \(i\) 个匹配到 \(\empty,2,0,1,7\) 的最小代价。转移为设当前字符是 \(x\)（第 \(x\) 个），那么有 \(f_{i,x-1} = f_{i-1,x-1}+1,f_{i,x}=\min{f_{i-1,x},f_{i-1,x-1}},f_{i,j}=f_{i-1,j}(j\neq x \and j\neq x-1)\)。特别地，如果这一位是 \(6\)，那么有 \(f_{i,3}=f_{i-1,3}+1,f_{i,4}=f_{i-1,4}+1\)。区间询问使用广义矩乘做就行，可以倍增做。复杂度 \(\Theta(nk^3 \log n)\)，其中 \(k=5\)。
CF763E
跟 CF811E 类似，由于一个点只会连与它距离不超过 \(k\) 的点，所以如果一个联通块最左、最右是 \(l,r\)，并且 \([l-k,l-1],[r+1,r+k]\) 都没有跟这个联通块相连的，那么再往外就不可能有与它相连的了。所以也考虑线段树维护 \([l,r]\)，记录 \([l,r]\) 的联通块个数，并且维护 \([l,l+k-1],[r-k+1,r]\) 每个点所在的联通块。合并直接开个 \(4k\) 大小空间的并查集合并这些点就好了，注意区间小的时候还要更新左边和右边的 \(k\) 个点。复杂度 \(\Theta(nk^2 \log n)\)。
CF848C
套路地将最后一次出现的下标描述成 \(nxt_i >r\) 的 \(i\)。那么答案就是 \(\sum\limits_{i=l}^r i[nxt_i > r]-\sum\limits_{i=l}^r i[pre_i < l]\)。那么考虑一个 \((i,nxt_i)\)，将 \([1,i][i,nxt_i - 1]\) 区间加上 \(i\)，把 \((i,pre_i)\) 的 \([pre_i + 1,i][i,n]\) 矩阵减去 \(i\)。再开 \(\Theta(V)\) 个 set 维护每个值出现位置，每次单点修改只用更新 \(\Theta(1)\) 个值。所以就要支持矩阵加，单点求值。在线就可以树套树，离线可以 cdq 三维数点。复杂度 \(\Theta(n\log^2 n)\)。
CF1004F
经典 trick 是前缀或和不超过 \(\log V\) 段。所以线段树上直接维护被完全包含在当前区间的答案和前缀、后缀的或和 段。合并的时候，后缀从右边继承，再接上左边，前缀同理。答案是左边加上右边，然后再做个双指针，左边从 \(mid\) 往左扫，右边从 \(mid+1\) 往右扫即可，合并复杂度 \(\Theta(\log V)\)。单点改就直接改。所以总复杂度就说 \(\Theta(n\log n \log V)\)。
CF1140F
注意到满足要求的肯定是一个缺一个角的矩形，补上去会形成一个完整的矩形。然后再考虑一直这样做最后会形成什么，就是会形成一堆矩形，且它们的行列都是不同的。这启发我们找一个联通块，然后就会注意到如果对于每个点，把它的行列连边，最后得出来的每个联通块就会形成一堆矩形。考虑线段树分治，并查集维护连通性和行列数量即可。复杂度 \(\Theta(n\log^2 n)\)。
CF1316F
即求每个子序列的代价和，考虑对每个相邻点对 \((a_i, a_{i+1})\) 求贡献。考虑线段树维护值域，对每个区间 \([l,r]\) 记录只保留值在 \([l,r]\) 的点的所有点对值乘方案的和，每个点的 \(p_i \times 2^{L_i}\) ，\(L_i\) 为 \(i\) 左边的点数，和 \(p_i \times 2^{R_i}\)，记作 \(suml,sumr\)，还有区间中的点数 \(cnt\) 。合并时，\(ans=ans_{ls} \times 2^{cnt_{rs}} + ans_{rs} \times 2^{cnt_{ls}}+suml_{ls} \times sumr_{rs}\)，\(suml = suml_{ls} +suml_{rs}\times 2^{cnt_{ls}},sumr=sumr_{ls} \times 2^{cnt_{rs}} + sumr_{rs},cnt=cnt_{ls}+cnt_{rs}\)。 因为有重复的值，所以对所有可能出现的数排序放到下标就行。复杂度 \(\Theta(n\log n)\)。
CF1371F
考虑线段树维护每个区间正着和反着的信息。考虑答案需要记录什么，要知道从一端走能到达哪里，要知道两端溢出了多少球。于是线段树记录 \(ans,tL,tR,L,R\) 分别表示此区间的答案，左边溢出的球，右边溢出的球，（从左边加球能到达的位置，那个位置的球数量），右边同理。转移是简单的。
c.tL = (R.se == l ? tL + b.tL : tL), c.tR = (b.L.se == b.r + 1 ? b.tR + tR : b.tR);
c.L = (L.se == b.l ? make_pair(tR + b.L.fi, b.L.se) : make_pair(L.fi + (R.se == L.se ? b.tL : 0), L.se));
c.R = (b.R.se == b.l ? make_pair(b.tL + R.fi, R.se) : make_pair(b.R.fi + (b.R.se == b.L.se ? tR : 0), b.R.se));
c.l = l, c.r = b.r;
区间取反直接打标记，交换正反信息即可。复杂度 \(\Theta(n\log n)\)。
CF1373G
一个点如果一直往第 \(k\) 行走，设它最前能到达的格子为 \(x\)，那么它可以被放到 \([x,n]\) 这些格子里。那么要把一堆点都能放完的话，设 \(suf_i\) 为 \([i,n]\) 有多少个 \(x\)，条件就是 \(\forall i,suf_i \le m-i+1\) 即 \(suf_i + i - 1\le m\)，最小的 \(m\) 即 \(suf_i + i - 1\) 的最大值。
考虑动态修改，使用线段树维护，每次插入一个 \(x\) 把 \([1,x]\) 加 \(1\)，删除减 \(1\)，查全局最大即可。复杂度 \(\Theta(n\log n)\)。
CF1379F2
考虑相邻两行，注意到每相邻两行 \((2x+1,2x+2)\) 直接最多只能放 \(m\) 个，又因为只有 \(2n\) 行，所以每相邻两行必须放 \(m\) 个。显然，这 \(m\) 个如果能放到 \(2x+1\) 这行肯定最优，否则就是 \(2x+1\) 这行有个地方挡住了，只能放到 \(2x+2\) 行，那么上面就是一个前缀，下面就是一个后缀，分别对应 \(1\) 到 \(2x+1\) 这行第一个空缺的位置 \(x\)，\(2x+2\) 行最后一个空缺的位置 \(y\) 到 \(2m\)，所以这里要求 \(x> y\)，设上面那行是在第 \(t\) 个放完后终止的，那么 \(t\in [\dfrac{y}{2},\dfrac{x-1}{2}]\)。并且要求 \(\forall i,t_i \ge t_{i+1}\)。
问题转化为，给定 \(n\) 个区间，动态修改区间，要求在每个区间中取一个数，且这个数不能大于上次取的。由于拓展区间不好做，不妨使用线段树分治把动态修改区间改为动态缩减区间。贪心的想法是每个区间尽量往右取，那么每取完一个 \(x\) 就直接对后面所有区间的 \(r\) 对 \(x\) 取 \(\min\) 即可，如果碰到一个 \(l>r\) 就是不合法的了。
复杂度 \(\Theta(n\log^2 n)\)。
CF1439C
看到形如 \(y \ge a_i,y\to y-a_i\) 的形态，第一时间想倍增分块。注意到这个 \(a\) 无论何时都是不增的，这也就避免了倍增分块中要考虑 \(<2^k\) 的和的情况。
那么现在思路就明确了，若现在在 \(x\)，设能连续取的极长长度为 \(len\)，也就是能连续取完 \([x,x+len-1]\)。若 \(len < n-x+1\)，那么 \(y\) 必定会减半，因为若不减半，最后一个取的一定小于 \(\dfrac{y}{2}\)，后一个依然小于 \(\dfrac{y}{2}\)，那么显然可以再取一个。
考虑怎么跳，显然直接在线段树上二分找到下一个位置即可。考虑修改，如果直接吉司机当然可以，但是每必要，也是直接二分找到第一个 \(<y\) 的位置即可。
复杂度 \(\Theta(n\log n \log V)\)。
CF1386C
首先观察奇环怎么处理，只需要找到一棵生成树然后对于每个非树边看看和树边形成的环是否为奇环即可，可以使用带权并查集维护。具体地，当连接一条边时，由于并查集上的边不是真实的边，所以找到 \((x,y)\) 到 \((rt_x,rt_y)\) 的边权异或和，将其异或 \(1\) 然后作为 \((rt_x,rt_y)\) 的边权。每次查询 \((x,y)\) 直接找到 \((x,y)\) 到根的边权异或和异或起来是 \(0\) 即可。
- 解法一 \(\Theta(n\sqrt{n})/\Theta(n\sqrt{n}\log n)\)
考虑把边的序列复杂一边接到后面，然后每次询问就是用一个区间的边。使用不删除莫队，直接维护即可。复杂度可能带个 \(\log\)，由于要撤销并查集，不能使用路径压缩。
- 解法二 \(\Theta(n\log n)/\Theta(n\log^2 n)\)
考虑令 \(nxt_i\) 为以 \(i\) 作为左端点，最远的 \(r\) 使得删掉 \([i,r]\) 这段区间还有奇环。显然 \(nxt_i\) 是随 \(i\) 单调不降的。考虑使用分治优化决策单调性，设 \(f(l,r,L,R)\) 为处理 \([l,r]\) 的 \(nxt\)，并且值域（即决策点）在 \([L,R]\) 范围内。递归到 \(f(l,r,L,R)\) 时，应先加入所有除了 \([l,R]\) 的边，然后令 \(mid = \lfloor\dfrac{l+r}{2}\rfloor\)，考虑从 \(R\) 往 \(L\) 依次加入每条边，一旦有奇环那么 \(nxt_{mid}\) 就设为当前枚举的边。然后就递归地调用 \(f(l,mid-1,L,nxt_{mid})\)，注意此时不需要撤销 \([nxt_{mid}+1,R]\) 的边。然后处理完左边后撤销掉 \([nxt_{mid} + 1,R]\) 的边，加入 \([l,mid]\) 的边，再做 \(f(mid+1,r,nxt_{mid},R)\)。返回的时候再撤销掉即可。复杂度也会多个 \(\log n\)，因为并查集。
CF1442D
先观察一下最后答案长什么样，发现一定是一堆整串再加上至多一个前缀。因为若有两个前缀，可以考虑把下一个数较大的前缀往后取一位，另一个最后删一位，一定是更优的。所以问题转化为有 \(n\) 个物品，每个重量 \(len_i\)，价值 \(sum_i\)，且能额外取一个前缀，要求取的重量不超过 \(n\)。
朴素的想法是枚举那个前缀在的串，然后其他的用个背包，但因为是最优化，所以不能可撤销背包来搞。既然不能直接删除一个物品，那么考虑不用删除物品的分治。当在做 \(f(l,r)\) 的时候，若下一步做 \(f(l,mid)\)，那么先把当前的背包值记录下来，然后加入 \([mid+1,r]\) 这些物品，再递归下去。返回的时候还原之前记录的背包数组，然后加入 \([l,mid]\)，再做右边 \(f(mid+1,r)\)。这样的话一个节点的复杂度是 \(\Theta(len\cdot k)\)。
总复杂度为 \(\Theta(nk\log n)\)。
CF1648D
考虑一个朴素 dp，设 \(f_i\) 为走到 \((2,i)\) 的最大价值，\(sum_i\) 为第二行的前缀和，\(a_i\) 为第一行的前缀和，\(b_i\) 为第三行的后缀和。转移有 \(f_i = sum_i + \max\limits_{j<i}(\max(f_j-sum_{j},a_j-sum_{j-1}) -\min\limits_{l_x \le j \le r_x} k_x)\) 。重点在于 \(-\min\limits_{l_x \le j \le r_x} k_x\)。
考虑分治，用 cdq 的思想，先把左边的 \(f\) 处理出来，然后通过 \(j\in [l,mid]\) 去更新 \(i\in [mid+1,r]\)，先对左边 \([l,mid]\) 记录后缀最大 \(suf_i = \max\limits_{j=i}^{mid} \max(f_j-sum_{j},a_j-sum_{j-1})\)。考虑把 \((l,r,k)\) 分为两种。
- \(r_x \in [mid+1,r]\) 那么可以对 \(i\in [mid+1,r_x]\) 的 \(f_i\) 对 \(suf_{\max(l_x,l)} - k_x\) 取最大。由于每个这样的 \((l,r,k)\) 只会出现 \(\Theta(\log n)\) 次，复杂度 \(\Theta((n+q)\log n)\)。
- \(r_x>r\) 那么这样的 \((l,r,k)\) 一定是在当前节点的祖先是出现在第一种的，并且是递归到了左边。那么考虑在那个祖先的地方递归到左边的时候在 \(l_x\) 处插入一个 \(k\)。
- 若 \(l_x \ge l\) 在做 \(suf_i\) 的是时候直接找到 \([l,i]\) 中最小的 \(k_x\) 即可，用它更新所有 \([mid+1,r]\)。
- 否则的话一定是上面那种递归到右端点的，这时候的分治区间被 \([l_x,r_x]\) 完全包含，所以记录最小那个即可。
总复杂度为 \(\Theta((n+q)\log n)\)。
CF1654F
考虑异或的性质，若第 \(i\) 位为 \(1\)，那么就是将原序列以 \(2^{i-1}\) 为一块分成若干块，奇数块和偶数块交换。设 \(f(x,i)\) 为异或 \(x\) 形成的新序列的前 \(2^i\) 个形成的序列，那么显然 \(f(x,i)=f(x,i-1)+f(x\oplus 2^{i-1},i-1)\)。设 \(g(x,i)\) 为异或 \(x\) 形成的新序列的前 \(2^i\) 个数在异或 \([0,2^n -1]\) 形成的所有新序列中的排名，那么直接以 \((g(x,i-1),g(x\oplus 2^{i-1},i-1))\) 为关键字排序即可得到 \(g(x,i)\)。复杂度 \(\Theta(n\log^2 n)\)。
CF1693D
首先观察一下，发现无解的充要条件是存在一个四元组 \((a,b,c,d)\) 满足 \(a<b<c<d\) 使得 \(p_b > p_a > p_d > p_c\) 或 \(p_c > p_d > p_a > p_b\)。因为这两种形态满足它们都是两个上升或下降子序列组成的且都不相交。然后考虑统计，设 \(pre_i\) 为 \(i\) 之前最大的 \(j\) 满足区间 \([j,i]\) 无解，考虑第二种形态，设 \(L_i\) 为 \(i\) 前面第一个大于 \(p_i\) 的点，\(R_i\) 为 \(i\) 后面第一个小于 \(p_i\) 的点。所以 \(pre_i\) 就是最大的 \(j\) 满足 \(R_j < L_i,p_j<p_i\)，直接二维偏序，bit 维护即可。第一种形态可以直接把序列变成 \(n-p_i + 1\) 再做一遍就行。复杂度 \(\Theta(n\log n)\)。
CF1730E
先预处理每个位置是最大值的区间 \([L_i,R_i]\) 满足 \(\forall j \in [L_i,i-1],a_j < a_i \land \forall j\in [i+1,R_i],a_j \le a_i\)，再预处理每个数前面第一个比它小的和后面第一个比它小的位置 \(pre_i,suf_i\)，可以单调栈 \(\Theta(n)\) 预处理。
考虑枚举最大值的位置 \(i\)，枚举 \(a_i\) 的因数 \(x\)。找到 \(i\) 前面 \(x\) 第一个出现的位置 \(lst\) 和 \(i\) 后面第一次出现的位置 \(nxt\)。讨论 \([lst,i]\) 和 \([i,nxt]\) 是否最小值是 \(x\)。若 \([lst,i]\) 最小值为 \(x\)，那左端点可以取到 \([\max(L_i,pre_{lst}),lst]\)，否则若 \([i,nxt]\) 最小值是 \(x\)，那么左端点可以取到 \((suf_{lst},i]\)，右端点可以取到 \([nxt,\min(R_i,suf_{nxt})]\)。右边同理。若 \(lst\) 不存在，左端点可以取到 \([pre_{nxt},i]\)，右端点同上。\(nxt\) 不存在同理。
设值域为 \(m\)，复杂度 \(\Theta(m\log m + nd(m))\)。
位问题
CF241B
考虑先找到第 \(m\) 大的两两异或值。二分答案 \(x\)，然后对每个数 \(a_i\) 找到所有 \(j<i,a_i\oplus a_j \le x\) 的 \((i,j)\) 对数，可以用 trie 实现，这部分复杂度 \(\Theta(n\log^2 a)\)。
然后可以先找到前 \(m\) 大有多少个 \(x\)，可以用 \(m\) 减去异或和 \(\le x-1\) 的对数得到。那么就是求 \(\sum\limits_{i=1}^n \sum\limits_{j=1}^{i-1} [a_i \oplus a_j < x] (a_i \oplus a_j)\)。也可以用 trie 实现，查询 \(i\) 时，可以先找到 trie 上哪些子树里的数是合法的，然后拆位算贡献，对于 trie 上每个节点记录它子树中第 \(j\) 位是 \(0/1\) 的数的个数，异或上 \(x\) 对应位即可。复杂度也是 \(\Theta(n\log^2 a)\)。
总复杂度 \(\Theta(n\log^2 a)\)。
CF633G
注意到 \(m\) 很小，可以对每个点记录子树中每个值的出现情况。设 \(f_{i,j}\) 表示值 \(j\) 是否在 \(i\) 子树中出现，对 \(i\) 子树加 \(v\) 相当于将其向右循环移位 \(v\) 次。但是由于子树加 \(v\) 还会影响祖先的 \(f\) 值，所以不能这样维护。
考虑换种方式，查的时候直接将子树里的值或起来就行。使用线段树 + dfn 序列维护，每次相当于区间循环移位，区间求或，可以套个 bitset，复杂度 \(\Theta(\dfrac{m(n+q\log n)}{w})\)。
CF796F
考虑操作 \(1\)。
- 若 \([l,r]\) 中已确定的最大值为 \(x\)，则表示剩下的区间中的每个数都小于等于 \(x\)。
- 若 \([l,r]\) 中已确定的都小于 \(x\)，那么剩下的区间中每个数都小于等于 \(x\)，且存在一个数为 \(x\)。
现在问题转化为，给定若干个限制（可能达到 \(\Theta(n^2)\) 级别）表示一个区间的数小于等于一个数，或者一个区间的数小于等于一个数且存在一个数等于。那么按照 \(x\) 从小到大排序，显然只用考虑所有之前没覆盖的位置，如果是第二种限制，那就先随便钦定一个位置为 \(x\)，若还有剩下位置没钦定，那么设之前自己确定的所有位置或和为 \(sum\)，从高到低枚举每个位置，若 \(sum\) 这个位置为 \(0\) 且加上后不超过 \(x\) 就加上，显然最多确定两个数就能到达目前的最优了。
那么还有一个问题，就是限制是 \(\Theta(n^2)\) 级别的，该如何优化？注意到每次操作只会改一个点，那么处理出来每个点什么时候第一次被改即可，套上个线段树分治，每次直接找每个包含 \(t\) 的在 \([l,r]\) 中的点删掉即可。
复杂度 \(\Theta(n\log^2 n)\)。
CF1511G
题目就是要求 \(\oplus_{i=l}^r (a_i - l)\)，\(a_i\) 是值是 \(i\) 的所有数异或和。考虑倍增，设 \(f_{i,j}\) 为 \(l=i\) 时 \([i,i+2^{j} -1]\) 区间的异或和，此时这个区间里所有数减 \(i\) 的第 \(j\) 位都必定是 \(0\)。那么转移的时候，由于 \([i+2^{j-1},i+2^j - 1]\) 这段区间减 \(i+2^{j-1}\) 的第 \(j-1\) 位也是，所以可以直接异或上 \(2^{j-1}cnt_{i+2^{j-1},i+2^j-1}\)，即 \(f_{i,j}=f_{i,j-1}\oplus f_{i+2^{j-1},j-1}\oplus (2^{j-1}\times (cnt_{i+2^{j-1},i+2^j - 1} \operatorname{mod} 2))\)。
回答询问也是类似搞即可。复杂度 \(\Theta((m+q)\log m)\)。
CF1730F
先求出 \(p\) 的逆排列 \(pos\)，然后就是把每个数 \(i\) 填到 \(p\) 里面，满足 \(i\) 出现在 \(j\) 前面时 \(i \le j+k\)，求 \(pos_i\) 的逆序对最大。
对于任意的 \(i\)，\(q\) 前 \(i\) 个数中所有 \(\le i-k\) 的数都必须存在。
证明：若存在 \(x\le i-k\) 且 \(x\) 不在 \(q\) 中前 \(i\) 个数，则 \(q\) 中前 \(i\) 个数的最大值 \(t \ge i+1\)，由于 \(x\) 不在前 \(i\) 个中，所以 \(t\le x + k \le i\)，又因为 \(t\ge i+1\)，故矛盾。
对于任意的 \(i\)，\(q\) 前 \(i\) 个数中所有 \(>i+k\) 的数都不能存在。
证明：若存在 \(x>i+k\) 在 \(q\) 前 \(i\) 个数中，则 \(q\) 中前 \(i\) 个数中第一个没出现的数 \(t \le i\)，由于 \(x\) 在 \(t\) 前面，所以 \(x\le t+k\)，即 \(t>i\)，矛盾。
那么可以得出前 \(i\) 个数中不确定是否存在的数只有 \([i-k+1,i+k]\) 这 \(2k\) 个。
对于任意的 \(i\)，\(q\) 前 \(i\) 个数肯定是一段连续的值域再加上 \([i+1,i+k+1]\) 的某些数
这是显然的。
设 \(f_{i,j}\) 为加入了前 \([1,i]\) 这些数，\([i+1,i+k+1]\) 的出现情况是 \(j\) 的最小逆序对个数，枚举转移即可。复杂度 \(\Theta(n^2 + nk2^k)\)。
标签：nxt,log,复杂度,mid,II,Part,区间,Theta,ds From： https://www.cnblogs.com/MiniLong/p/18474387