cf上 2200 左右的 ds 选做 (codeforces 2200-2300 ds list)
1. cf1045g AI robots
luogu 题目传送门 1
因为 \(k\leq 20\) , 所以考虑直接枚举能聊天的 robot 的 \(q\) 值 .
对于每个 \(q\) 维护一个 vector , 询问区间 \([x_i-r_i,x_i+r_i]\) 的时候，二分 \(x_i-r_i\) 的位置和 \(x_i+r_i\) 的位置即可 .
时间复杂度 : \(O(n\log n)\)
空间复杂度 : \(O(n)\)
2. cf862e Mahmoud and Ehab and the function
luogu 题目传送门 1
\[f(j)=|\sum\limits_{i=1}^{n}(-1)^{i-1}a_i-b_{i+j}| \]考虑把式子拆掉，
\[f(j)=|\sum\limits_{i=1}^{n}(-1)^{i-1}a_i-\sum\limits_{i=1}^{n}(-1)^{i-1}b_{i+j}| \]设 \(A=\sum\limits_{i=1}^{n}(-1)^{i-1}a_i,B=\sum\limits_{i=1}^{n}(-1)^{i-1}b_{i+j}\)
\(B\) 不会被修改是定值，\(A\) 每次修改后都有可能改变，但是对于所有的 \(f\) 来说，任意时刻都是相同的 ，而对于各自的 \(f\) 值来说，\(B\) 是不同的但是不变的 .
考虑将 \(B\) ，所以修改 \(A\) 之后，排序后的 \(B\) 的一段前缀取反是绝对值，剩下的后缀直接就是绝对值 .
所以，只需要每次二分出 \(B\) 的前缀取到多少取反 .
时间复杂度 : \(O(n\log n)\)
空间复杂度 : \(O(n)\)
3. cf165D Beard Graph
luogu 题目传送门 1
这是真的模板，害怕.
考虑用树链剖分维护当前树，白边记为 \(0\)，黑边记为 \(1\)，直接询问两个点之间的黑边个数即可 .
时间复杂度 : \(O(n\log^2n)\)
空间复杂度 : \(O(n)\)
4. cf731d 80-th Level Archeology
luogu 题目传送门 2
考虑对于相邻两个数列 \(a,b\)，必定是找到第一个不相同的位置 \(i\) .
如果 \(a_i
如果 \(a_i>b_i\) , 那么，可以执行的操作次数的范围为 \([c-a_i+1,c-b_i]\) .
考虑对于所有相邻序列的合法区间求交，如果交为空集，即是无解，否则是交的第一个数 .
不懂，感觉不需要任何 ds 的知识啊，迷惑 .
时间复杂度 : \(O(n)\)
空间复杂度 : \(O(n)\)
5. cf797d Broken BST
luogu 题目传送门 2
考虑维护每个节点会被访问到的区间 \([l,r]\)，如果 \(a_x\in [l,r]\), 此节点就会被访问到 .
对于当前节点 \(x\) 的值 \(a_x\) 传递到左右儿子，左边儿子的区间就会变成 \([l,a_x-1]\) 和 \([a_x+1,r]\) . 继续传递下去即可 .
感觉又不需要什么 ds 啊，害怕
时间复杂度 : \(O(n)\)
空间复杂度 : \(O(n)\)
6. cf899f Letters Removing
luogu题目传送门 1
考虑对于 a 到 z 每个都维护一个线段树，维护当前位置是否有字符 \(c\) .
考虑对于一个区间删除字符 \(c\) 就是将维护字符 \(c\) 的线段树区间赋值为 \(0\) .
最后查询的时候，每个位置对于每个线段树都单点查询一下即可求出 .
luogu题目传送门 3
看到 \(\oplus\) 想到可以建出 trie 树 .
遇到 \(k|gcd(v,x)\) 就相当于 \(k|v,\ k|x\) . 所以知道了 \(x\) 需要是 \(k\) 的倍数 .
此时想到对于每个树建立一棵 trie 树 .
插入操作时把 \(x\) 插入所有的因数的 trie 树中.
还有一个条件 \(v+x\leq s\)，所以考虑 trie 树上还要维护最小值 .
时间复杂度 : \(O(n\varphi(n)\log n)\)
空间复杂度 : \(O(n\varphi(n)\log n)\)
8. cf1093g Multidimensional Queries
luogu题目传送门 1
\(k\leq 5\) 想到可以状压，每一位表示当前这位是正还是负.
建立一棵线段树，每个节点上对于每一个状态维护 \(3\) 个值，最大值，最小值和曼哈顿距离的最大值 .
绝对值不用判断正负，因为要求的是最大值，如果当前维护的最大值减去最小值是负数的话，肯定不优.
9. cf500e New Year Domino
luogu题目传送门 3
当第 \(i\) 个骨牌落下时，能扑倒的骨牌是一定的，考虑为 \(r_i\) .
对于 \([i,r_i]\) 只会构成包含关系. 是一个树的形态.
考虑从后往前加入骨牌，加入的骨牌有可能会链接一些骨牌，有可能是一个独立的骨牌，当前的骨牌会分成一些连续段，只要最前面的骨牌倒了，整个连续段的骨牌都会倒.
\(X_i+L_i+a\geq X_j\) 得到 \(a\geq X_j-X_i-L_i\)
所以 \(X_j\) 是固定的，要最大化 \(X_i+L_i\)，所以求前缀最大值，离线询问，相当于求得一段前缀的最大值的和. 可以用线段树维护之.
时间复杂度 : \(O(n\log n)\)
空间复杂度 : \(O(n)\)
10. cf1251e1 Voting (Easy Version)
luogu题目传送门 0
考虑枚举枚举 \(a_i\leq i\) 的人是被贿赂的，\(\geq i\) 的人都要被贿赂, 如果人数不够 \(i\) 的话, sort 一下 \(\leq i\) 的 \(p_i\) 取出前面几个，直到取到 \(i\) 个.
时间复杂度 : \(O(n^2\log n)\) / \(O(n^2+n\log n)\)
空间复杂度 : \(O(n)\)
11. cf853c Boredom
luogu题目传送门 2
考虑处理出不相交的矩形个数，用总个数减去不相交的个数就是相交的个数.
此矩形将图形分成 \(9\) 个部分，用 \(0\leq x
很显然可以用在线可持久化线段树或者离线bit维护.
时间复杂度 : \(o(n\log n)\)
空间复杂度 : \(O(n)\)
12. cf1194e Count The Rectangles
luogu题目传送门 3
考虑枚举矩形的下边的编号 \(i\) ，枚举上边的编号 \(j\) ，需要求出 \(x_{k,1}\leq x_i\) 且 \(x_j\leq x_{k,2}\) 并且 \(\min(y_{i,1},y_{j,1})\leq y_k\leq \max(y_{i,2},y_{j,2})\) 的 \(k\) 的数量.
考虑用 \(\mathrm{bit}\) 维护，由于 \(x_i\) 固定，考虑枚举从小到大枚举 \(x_j\)，往下移动一行的时候在每一列加入相对于的值，\(\mathrm{bit}\) 上维护的是每一列对于的个数，由于方向相同的边不交，所以 \(\mathrm{bit}\) 中每一列只会有 \(0/1\) .
时间复杂度 : \(O(n^2\log n)\)
空间复杂度 : \(O(n)\)
13. cf1252k Addition Robot'
luogu题目传送门 3
对于这种 \(A,B\) 的转化，考虑矩阵 .
对于操作 A ,
对于操作 B
14. cf665e Beautiful Subarrays
luogu题目传送门 2
对于 \(\bigoplus\limits_{i=l}^{r} a_i\leq k\)，考虑维护 \(pre(i)=\bigoplus\limits_{i=1}^{r} a_i\)，那么这个式子就等于 \(pre(r)\bigoplus pre(l-1)\leq k\) .
异或，考虑建立 \(\mathrm{trie}\) 树，那么对于每个 \(pre(i)\) 在 \(\mathrm{trie}\) 树上二分一下即可.
时间复杂度 : \(O(n\log A)\)
空间复杂度 : \(O(n)\)
15. cf103d Time to Raid Cowavans
luogu题目链接 1
经典问题，考虑分治.
对于 \(k\geq \sqrt{n}\) 的部分，直接暴力就可以，跳不会超过 \(\sqrt n\) 次，单词询问为 \(\sqrt n\) 的.
对于 \(k\leq \sqrt{n}\) 的部分，可以考虑预处理，预处理出一个前缀和 \(sum(i,j)\) . 单词询问为 \(O(1)\) 的，预处理是 \(O(n\sqrt{n})\) 的.
时间复杂度 : \(O(n\sqrt{n}+m\sqrt{n})\)
空间复杂度 : \(O(n\sqrt{n})\)
16. cf827c DNA Evolution
luogu题目链接 3
考虑建出线段树，每个点维护对于 \(k,1\leq k\leq 10\) 的模数 \(p\) 和在当前模数上 A T G C 的个数.
单点修改，区间查询即可.
时间复杂度 : \(O(400n\log n)\)
空间复杂度 : \(O(400n)\)
17. cf538f A Heap of Heaps
luogu题目链接 2
考虑分治，对于每个 \(i\), 对于 \(k\) 为 \(1\) 到 \(\sqrt n\) 的情况，直接判断，对于后面的情况，很多不同的 \(k\) 会对应到相同的父亲节点上去，差分一下即可.
感觉细节比较多，思路比较套路，但是我还是被卡了好久.
时间复杂度 : \(O(n\sqrt n)\)
空间辅助带 : \(O(n)\)
18. cf85d Sum of Medians
luogu题目链接 2
做法1
其实直接 vector 可以草过去.
但是肯定要追求更好的做法.
做法2
\(\mathrm{treap}\) 的板子题. 但是我不会 \(\mathrm{treap}\).
做法3
离线离散化，线段树维护离散化之后的值，每个节点维护模 \(5\) 余 \(k\) 的数的和.
单点修改，区间查询
19. cf301d Yaroslav and Divisors
哆啦A梦的传送们 4
考虑用 \((i,j)\) 其中一个是另一个的倍数.
那么对于大的那个数，小的是它的因数.
但是不能对于所有 \(l\leq i\leq r\) 都做一遍. 所以考虑线段树分治，将 \([l,r]\) 对应到线段树上的 \(\log\) 个区间上去.
线段树上每个节点用一个线段树维护当前区间所有数的因数，然后线段树上左右两个区间合并的时候直接将一个区间的所有元素插入到另一个区间即可. 线段树的 size 可以直接开到 \(n\) ，因为考虑从左往右的操作，如果能合并就合并，最多相同时刻只会有 \(3\) 个线段树. 所以值需要开 \(3\) 个线段树即可.
查询的时候直接线段树上区间求值就可以了.
时间复杂度 : \(O(n\log^2n~n\log^3n)\)
空间复杂度 : \(O(n)\)
20. cf875d High Cry
哆啦a梦的传送门 2
考虑折半的分治，分别考虑最大值在左边或者右边.
依次考虑 \(a_i\) 二进制的每一位，从高位到低位考虑. 这样找到满足的最小一位.
或者直接 \(\mathrm{two\ pointers}\) 时间复杂度也是对的.
时间复杂度 : \(O(n\log A\log n)\)
空间复杂度 : \(O(n)\)
21. cf1295e Permutation Separation
哆啦a梦的传送门 2
因为 \(p\) 确定是一个排列.
所以考虑前半部分的序列一定也是一个排列. 考虑枚举前半部分最终长度，从 \(0\) 到 \(n\) .
考虑用一个线段树动态的维护当前如果选 \(k\) 从 \(1\) 到 \(n-1\) 对应的代价.
考虑加入当前的前半部分最终长度为 \(i\)，那么，对于 \(i\) 出现的位置设为 \(pos(i)\) .
对于 \([1,pos(i)]\) 的位置，加上 \(a_i\) .
对于 \([pos(i)+1,n]\) 的位置，减去 \(a_i\) .
每次询问找到最小值即可.
时间复杂度 : \(O(n\log n)\)
空间复杂度 : \(O(n)\)
22. cf522d Closest Equals
哆啦a梦的传送门
考虑对于每一个数 \(x\)，把 \(x\) 出现的位置处理出来. 考虑这些位置两两的距离，为一个个区间.
离线询问，考虑当前询问左端点需要 \(\leq i\) 的右端点需要 \(\geq j\) 的最小距离.
这个可以左端点从左往右扫到第 \(i\) 为，同时加入左端点在 \(i\) 的区间，在 \([r,n-1]\) 的区间修改. 同时删除右端点在 \(i\) 的区间，不对，线段树不可撤销啊. 不对，其实不需要删除，因为此时询问的区间是 \([r_i,n]\)，\(r_i\) 必然大于 \(i\) .
因为一位一位插入，想到这个东西其实可以可持久化线段树，带上区间取 min 操作. 之前还没有写过.
时间复杂度 : \(O(n\log n)\)
空间复杂度 : \(O(n)/ O(n\log n)\)
23. cf1208e Let Them Slide
哆啦a梦的传送门 1
考虑每个序列的最大值会被放置到除了前 \(k\) 个和后 \(k\) 个，这 \(2k\) 个可以直接处理出.
剩下的直接差分处理就可以了.
时间复杂度 : \(O(\sum n)\)
空间复杂度 : \(O(\sum n)\)
24. cf1092d2 Great Vova Wall (Version 2)
哆啦a梦的传送门 2
首先离散化，把相同的用一个并查集维护.
从小的网大的合并，每次合并之后的除了最大值的段落必须是偶数.
时间复杂度 : \(O(n\alpha(n))\)
空间复杂度 : \(O(n)\)
25. cf1187d Subarray Sorting
哆啦a梦的传送门 2
考虑第一个 \(a_i>a_{i+1}\) 的位置 \(pos\) .
\(s\) 和 \(t\) 的后面 \([pos,n-1]\) 必须相同，\(t\) 的前面 \([0,pos-1]\) 是 \(s\) 的有序.
时间复杂度 : \(O(n\log n)\)
空间复杂度 : \(O(n)\)