2019暑期金华集训 Day1 数据结构
自闭集训 Day1
数据结构
CF643G
用类似于下面的方法,搬到线段树上。
如何合并两个集合?先全部放在一起,每次删掉最小的\(cnt_i\),然后把其他所有的\(cnt\)都减去\(cnt_i\),直到还剩下\(k\)个。
\(O(n)\)众数
如果众数出现次数大于\(n/2\),那么搞一个\(cnt\)和一个\(ans\)。从左往右扫,如果与\(ans\)相同那么\(++cnt\),否则\(--cnt\)。如果\(cnt<0\)那么更换\(ans\)。
如果大于\(n/3\),那么搞两个。如果相同那么++,否则两个都--。
以此类推。
更正:似乎如果有\(cnt=0\)的直接先换,否则才减。
HDU6087
可持久化平衡树,用类似于快速幂的东西支持复制。
CF453E
如果恒定\(l=1,r=n\),那么可以想到把马按恢复时间排序,每次查询的时候一定会有一个前缀全部恢复完,后面的则是\(t\sum v\)。
拓展到一般情况,可以发现对于上一次清0的时间,序列会分成若干个区间,而且区间总变化量\(O(n)\),所以可以主席树记录区间内\(v\)在某个区间的个数,暴力扫一遍要查询的区间,最后合在一起。
CF1172F
维护分段函数\(f(x)\)表示\(x\)进去后会变成\(f(x)\),显然最后函数复合在一起段数不超过\(r-l+1\)。
使用线段树,求出每个节点对应的分段函数。
合并左右儿子的时候直接two pointers,可以证明复杂度是对的。
最后询问的时候把\(\log n\)个节点拖出来,在每一个节点二分得到出来的函数值。
复杂度\(O(n\log n+m\log^2 n)\)。
CF1178G
先不考虑绝对值。分块,每个块中维护\((a_i,a_i\times b_i)\)的凸包。每次求答案的时候相当于求\(\max\{y+tx\}\),直接做即可。
考虑绝对值的做法大同小异?
ICPC 2018 Beijing E
可以发现\([l,r]\oplus x\)仍然对应一个区间,只不过下标顺序有所改变。
所以可持久化线段树。
CF297E
CTSC 图腾
连续段的做法
- 分治(?)
- \(\max-\min=r-l\)
- 对\(r\)维护点数-边数/连续段个数(?)
第三种:对于区间\([l,r]\),如果\(x,x+1\)都出现在里面,那么连一条边,于是当且仅当点数减边数为1时是连续段。
\(r\)从左往右扫,维护\(cnt_l\)表示点数-边数。如果\(a_r+1,a_r-1\)出现过那么在某个区间-1。
CF997E
先离线,然后用上面方法开始搞。
如果能维护\(ans_l\)表示做到当前\(r\)时\(cnt_l\)有多少次是1,那么就很容易得到答案。
使用线段树,设\(tag_x=k\)表示对\(x\)区间最小值位置加\(k\)。
发现这个\(tag\)非常优秀,各种操作都可以支持,就做完了。
CF1034D
二分第\(k\)大的价值是多少,显然\(l\)有单调性可以two pointers。维护每个地方\([1,r]\)中最晚是什么时候被覆盖,那么加区间就是一个区间赋值。由于区间改变量\(O(n)\),所以可以直接\(set\)维护区间,很容易得到当前颜色为\(x\)的长度,于是有\(O(n\log^2 n)\)的做法。
由于区间的改变量与外层二分的东西无关,所以可以先跑一遍,然后每次二分的时候\(O(n)\)判。
计算总和也可以用类似的方法。
CF896E
分块。
在每个块内,如果改的是\(x\),且值域\(\le 2x\),那么把大的那些连到小的去;否则小的连到大的去,且打一个减\(x\)的标记。
于是可以用\(O(x)\)的复杂度使得值域范围减小\(O(x)\),所以总复杂度\(n\sqrt{n}\)。
CF1148H
把恰好为\(k\)改成至少为\(k\)。
假设可以离线。
对于一个\(r\),我们要求最小的\(r'\),使得在\(r'\)时\(k\)前缀最小值大于等于\(l\)。此时答案就是从\(r'\)到\(r\)所有版本里面\(\min-l+1\)之和。
然后……就不会了……
最新文章
- Atom
- [技术学习]js接口继承
- ztree插件(JQuery Tree)
- Burp Suite详细使用教程
- spring mvc+myBatis配置详解
- flask学习
- 转】Eclipse在线安装SVN
- CSS让图片垂直居中的几种技巧 三种方法介绍
- Linux系统编程(12)——shell基础
- Linux平台下使用rman进行oracle数据库迁移
- asp.net core中负载均衡场景下http重定向https的问题
- Redis -->; 为redis分配新的端口
- 关于伪类after后续追加,实现js事件(如点击事件)
- 支持“XXX”上下文的模型已在数据库创建后发生更改。请考虑使用 Code First 迁移更新数据库(http://go.microsoft.com/fwlink/?LinkId=238269)。
- 【LOJ#6283】数列分块7
- django序列化 serializers
- ldconfig命令
- 【JMeter】1.9上考试jmeter测试调试
- MUI --- h.js无效
- ASP.NET中数据绑定表达式