1. CF 438D The Child and Sequence
大意: n元素序列, m个操作: 1,询问区间和. 2,区间对m取模. 3,单点修改
维护最大值, 取模时暴力对所有>m的数取模. 因为取模后至少减半, 复杂度$O(nlognlogC)$
2. CF 431E Chemistry Experiment
大意: n个试管, 第$i$个试管有$a_i$单位水银, m个操作: 1, 修改$a_x$改为$v$. 2, 将$v$单位水倒入试管, 求一种方案使得有水的试管水银与水总量的最大值最小, 输出最小值 (操作2独立)
二分出一个最小的$x$, 使得$sum[x]+v \le (x+1)cnt[x]$, 答案即为$\frac{sum[x]+v}{cnt[x]}$
3. CF 429D Tricky Function
大意: 给定序列, 求$f(i,j)=(j-i)^2+(sum[j]-sum[i])^2$的最小值
裸的平面最近点对, 可以用分治很容易求出
4. CF 420D Cup Trick
大意: 初始有一个排列, 顺序未知, m个操作, 每次将位置在$y_i$处权值为$x_i$的数移到排列最前面, 求恢复原排列.
很明显的splay模拟题, 按顺序操作, 最后再逆序恢复就可以了, 然后就完美的T掉了....主要这题数据量太大, 感觉最慢的点可能跑了5s.....参考了一下其他dalao的代码, 通过一些技巧转化为查询第k大, 然后可以线段树二分, 这样常数会小很多
5. CF 413E Maze 2D
大意: 2*n棋盘, m次询问, 查询两点最短路.
线段树维护2*2的转移状态矩阵.
6. CF 418E Tricky Password
大意: n*n的矩阵, 只给出第一行, 对于第$i(i\ge 2)$行, $a_{i,j}$为$a_{i-1,j}$在第$a_{i-1,1},...a_{i-1,j}$中的出现次数. 给定m个操作, 1,第一行单点修改. 2,查询某位置的值
打个表发现第二行以后每两行一循环, 然后分块.
7. CF 436E Cardboard Box
大意: n个盒子, 从第$i$个盒子拿一颗糖消耗$a_i$, 两颗消耗$b_i$, 求拿$w$颗糖最小花费.
按照b从小到大排序, 假设最优解选择最大的$b$位置为$k$, 容易证明$[1,k]$一定至少拿一块糖. 然后枚举k, 用权值线段树暴力模拟即可. 看了下CF大神的做法, 直接用$multiset$维护一颗糖和两颗糖最小值贪心..
8. CF 436F Banners
大意:
9. CF 444C DZY Loves Colors
大意: 给定n元素序列, 每个元素有一个颜色和权值, m个操作, (1)区间染色x, 每个位置权值增加|x-y|, y为原色 (2)区间询问权值和.
线段树维护权值和, 对于异色区间暴力递归下去, 直到同色时打标记修改, 考虑复杂度证明.
注意到产生额外复杂度的只有异色区间数, 并且每个异色区间每次至多产生1次贡献(因为查询后立刻被改为同色), 并且每次查询时边界处会再额外产生$O(log)$个异色区间, 再加上初始异色区间数$O(n)$, 总的复杂度就为$O(n+mlogn)$.
10. CF 446C DZY Loves Fibonacci Numbers
大意: 区间加斐波那契, 区间求和模1e9+9
这题模数比较特殊, 可以发现5模1e9+9的二次剩余恰好存在, 就有$F_n \equiv 276601605(691504013^n-308495997^n) \space (mod\space 1e9+9)$, 用线段树维护等比数列和.
还有一种不依赖二次剩余的解法, 若$b_1=x,b_2=y,b_n=b_{n-2}+b_{n-1}$, 那么$b_n=xf_{n-2}+yf_{n-1},\sum b_n=xf_n+yf_{n+1}-b_{2}$, 可以用线段树维护每一段的$x,y$
11. CF 452E Three strings
大意:给定三个字符串$s_1,s_2,s_3$, 对于每个长度$x$, 输出有多少个三元组$(i_1,i_2,i_3)$, 满足$s_k[i_1,i_1+1,...,i_1+x-1]$相同.
后缀自动机以后补.
12 CF 452F Permutation
大意: 给定n排列, 判断是否存在等差子序列.
跟FFT字符串匹配差不多. 假设存在等差$a_i,a_j,a_k$, 枚举$a_j$.
对于$a_{j-1},a_{j-2},...,1$和$a_{j+1},a_{j+2},...,n$分别维护一个二进制数, 二进制为$1$表示在$a_j$的左侧, 那么只要两个数二进制数不相等即存在一个等差. 用二进制压位$O(\frac{n^2}{\omega})$, 或者线段树维护哈希$O(nlogn)$.
13. CF 453E Little Pony and Lord Tirek
大意: n只小马, 第$i$匹马初始能量$s_i$, 每秒增长$r_i$, 最大能量$m_i$, 每次询问$t$时刻$[l,r]$区间小马能量和, 并将$[l,r]$区间小马能量清零.
把每个位置最后操作时间看做颜色, 每次操作相当于一个区间染色, 跟444C一样, 用线段树维护区间能量和, 对异色暴力, 只考虑同色情况. 对于连续一段同色区间按每只马充满时间排好序, 可以二分出第一个未充满的位置, 预处理出前缀和可以很容易计算答案, 复杂度$O(mlog^2n)$. 看了其他dalao题解, 发现可以用$splay$或者$set$分离合并相同的区间, 这样每次杂色区间最多产生2个, 复杂度是$O(mlogn)$
14. CF 455D Serega and Fun
大意: 给定序列a, m个操作, (1)[l,r]区间循环右移. (2)求[l,r]区间多少个元素等于k
裸的分块, 每个块内维护一个deque循环右移即可. 还可以用$splay$来做
15. CF 455E Function
大意: 定义f(1, j) = a[j], f(i, j) = min(f(i - 1, j), f(i - 1, j - 1)) + a[j], 给定a数组, m个询问f(x,y)的值
找下规律发现转移都是先向下再向左下, 也就是说$f(x,y)=\min\limits_{t}((x-y+t)a[t]+s[y]-s[t])$, 并且向下转移的a[t]的值一定是递减的, 所以可以离线后斜率优化.
16. CF 461C Appleman and a Sheet of Paper
大意: 初始一张长n的纸, 2种操作, (1)最左侧往右折叠p个单位. (2)询问[l,r]共多少层纸.
水题, 模拟折纸, 用树状数组求和, 若折叠超过右侧的话, 可以看做是将右侧折向左侧然后翻转了一下.
17. CF 464E The Classic Problem
大意: n节点, m条边无向图, 边权为2的幂, 求s->t的最短路.
线段树维护每个二进制位, 相加相当于区间修改, 比较大小用hash判断.
18. CF 471E MUH and Lots and Lots of Segments
大意: 给定平面上n条与坐标轴平行的线段, 求删除一部分, 使得剩余部分连通且无环, 输出剩余部分最大长度.
每个连通块的最大长度为点的个数-1, 然后扫描线不太会......... 这题以后再补 QAQ
19. CF 472G Design Tutorial: Increase the Constraints
大意: 给定两个01字符串a,b, m个询问, 给出$(p1,p2,len)$, 求$a_{p1}a_{p1+1}...a_{p1+len-1}$与$b_{p2}b_{p2+1}...b_{p2+len-1}$多少个对应位置的字符不同.
这题时限很大, 可以直接$bitset$水过去... 正解的话是分块+FFT, 以后再补 QAQ
20. CF 474F Ant colony
大意: n只蚂蚁, 第i只权值$a_i$, 每次询问只考虑区间$[l,r]$, 每只蚂蚁能整除其余蚂蚁那么加一分, 求多少蚂蚁得分不是r-l.
等价于求区间多少元素不等于区间gcd, 直接线段树维护.
21. CF 475F Meta-universe
22. CF 477E Dreamoon and Notepad
23. CF 480E Parking Lot
大意: 给定01矩阵, 单点赋值为1, 求最大全0正方形.
将询问倒序处理, 那么答案一定是递增的, 最多增长$O(n)$次, 对于每次操作暴力判断答案是否增长即可, 也就是说转化为判断是否存在一个边长$x$的正方形包含给定点, 可以维护左右两侧第一个1的位置, 从上往下滑动窗口即可$O(n)$判断, 总复杂度$O(n^2)$
24. CF 482E ELCA
大意:
25. CF 484E Sign on Fence
大意:给定序列, m个询问, 对于[l,r]区间, 求所有长为$w$的区间最小值的最大值
最小值最大要记着想二分! 对于每个权值$x$建一颗线段树, 把所有>=x的数添进线段树里, 维护最大连续区间长度, 然后每次询问二分出最大的>=w的权值.
26. CF 487D Conveyor Belts
大意:
27. CF 487E Tourists
大意:
28. CF 490F Treeland Tour
大意: 求树上LIS
这题数据范围过小, 我们考虑N<=1e5的做法, 线段树维护lis,lds, 合并的时候更新一下答案即可.
29. CF 494E Sharti
大意:
30. CF 498D Traffic Jams in the Land
大意: n+1个城市, i和i+1相距$a_i$, 若到第i个城市花费时间为$x$, 且$x|a_i$那么到$i+1$用时2, 否则用时1. m个操作, 单点修改a, 询问两城市花费时间
线段树维护模lcm(1,2,3,4,5,6)的花费时间.
31. CF 500E New Year Domino
大意: n个多米诺骨牌, 可以任选一块增高1, 每次询问求推倒$x$能传递到$y$所需要增高最少次数.
每块骨牌能到达的区间用线段树覆盖, 那么每次答案就为没有覆盖到的区间长度和. 为了避免前面骨牌的影响可以离线或者在线主席树. 该题也可以离线后用并查集合并区间.
32. CF 501D Misha and Permutations Summation
大意:ord(P)为排列P的字典序, perm(n)为第n大排列(从0开始), 给定排列p,q, 求perm((ord(p)+ord(q))%n!)
康托展开板子, 线段树二分$O(nlogn)$
33. CF 515E Drazil and Park
大意: 给定环, 每个点有高度h, 第i与i+1距离$d_i$, 每次询问考虑不属于[a,b]的部分, 求2(hx + hy) + dist(x, y)的最大值.
环翻倍后转成链, dist转成前缀, 相当于区间求$2h[x]-sum[x]+2h[y]+sum[y]$的最大值, 线段树可以很容易维护.
34. CF 519E A and B and Lecture Rooms
大意: 给定树, 每次询问给出两点$x,y$, 求树上多少个点到$x,y$距离相同.
两点距离为奇数显然不存在距离相同的点, 偶数的话求出中点, 中点不在树链的子树大小即为答案.
35. CF 522D Closest Equals
大意: 给定序列$a$, 每次询问区间[l,r]内相同元素的最近距离.
对于一个数$a_x$, 他会对$[1,pre[a_x]]$产生$x-pre[a_x]$的贡献, 可以用树状数组离线或主席树在线.
36. CF 524E Rooks and Rectangles
大意: 给定n*m棋盘, k个点有车, m个询问, 求矩形(x1,y1,x2,y2)区域内的车是否能攻击到所有位置.
等价于询问一个矩形内每行至少有一个车或每列至少有一个车, 可以离线, 询问按$x2$排序后, 求出[y1,y2]的范围内车的位置最小值是否>=x1. 对于[x1,x2]同理.
37. CF 524F And Yet Another Bracket Sequence
大意: 给定括号序列, 可以在任意位置添加括号任意次, 可以循环右移任意次, 求一种方案使得括号匹配且总长度最短且字典序最小.
括号题不会做, 这题看题解了.
38. CF 526F Pudding Monsters
大意: n*n棋盘, n个点有怪兽, 求有多少边长为k的正方形内恰好有k只怪兽, 输出k=1,...,n时的答案和.
等价于给定n排列, 对于任意一个长为$k$的区间, 若最大值最小值的差恰好为k, 则产生1贡献, 求贡献和.考虑分治, 问题就转化为如何$O(n)$求出跨越$mid$的贡献, 可以讨论最大值最小值的位置, 双指针求出.
39. CF 536E Tavas on the Path
大意:给定树, 有边权, m个询问(u,v,l), 对于路径u->v的所有边, 构造一个01串, 边权>=l为1, 对于每一段连续的1, 假设长为$x$, 则产生$f[x]$的贡献, 求贡献和.
离线, 按边权排序, 从大到小添边, 树剖+线段树维护答案.
40. CF 533D Landmarks
大意:
41. CF 538F A Heap of Heaps
大意: 给定序列$a$, 定义一棵有根树的不稳定度为: 所有非根结点$v$的个数, 满足$a_v<a_{fa[v]}$. 求将序列a组成1,...,n-1叉树的不稳定度.
n节点k叉树非叶节结点数是$O(\frac{n}{k})$的, 问题就转化为$O(nlogn)$个询问(l,r,x), 求[l,r]内有多少<x的数, 可以用主席树或树状数组实现.
42. CF 540E Infinite Inversions
大意: 初始有一个无限长的排列{1,2,3,....}, 求进行n次交换后排列的逆序对数.
把连续未改变的点合并一下, 然后归并或树状数组.
44. CF 543E Listening to Music
大意: 定义f(l,x)为区间[l,l+m-1]小于x的个数, q个询问(l,r,x), 每次回答$\min\limits_{i=l}^r f(i,x)$
按权值升序排列, 建主席树, 贡献转为区间加单点求最小值即可.
关键这题只有64MB, 学习了下卡空间技巧
(1)标记永久化
(2)叶节点不额外开点, 直接存在父亲上
(3)结构体用unsigned long long分3个位域存
45. CF 547E Mike and Friends
大意: 给定n个字符串, m个询问(l,r,k), 求$s_k$在$s_l,s_{l+1},...,s_{r}$的出现次数.
46. CF 549F Yura and Developers
大意: 给定序列a, 求区间个数, 满足除去最大元素后的和被k整除.
建出笛卡尔树后重链剖分, 复杂度$O(nlogn)$
47. CF 551E GukiZ and GukiZiana
48. CF 571D Campus
50. CF 573D Bear and Cavalry
神题
51. CF 573E Bear and Bowling
52. CF 575I Robots protection
53. CF 576E Painting Edges
54. CF 580E Kefa and Watch
大意: 给定字符串, m个操作, (1)区间赋值. (2)查询[l,r]区间周期是否为d
线段树维护哈希, 判断[l,r-d]与[l+d,r]是否相同即可
55. CF 587C Duff in the Army
56. CF 587E Duff as a Queen
57. CF 587F Duff is Mad
58. CF 594D REQ
大意: 给定序列a, m个询问, 求$\prod\limits_{i=l}^{r}a_i$
时限很大, 莫队随便过. 也可以用主席树或离线树状数组, 枚举右端点只保留最接近右端点的素数. 类似于HH的项链
59. CF 601D Acyclic Organic Compounds
大意: 给定树, 每个节点有字符, 定义dif(x)为以x为起点在x的子树内能得到的不同字符串数, 求$dif(x)+c_x$最大值及最大值个数.
可以直接字典树合并复杂度$O(26n)$, 或者hash+dsu on tree $O(nlogn)$
60. CF 610D Vika and Segments
大意: 给定平面n条水平或垂直的线段, 求占了多少个点.
相当于求宽度为1的矩形面积并, 离散化后扫描线.
60. CF 610E Alphabet Permutations
大意: 给定排列