Atcoder abc324
https://atcoder.jp/contests/abc324
G - Generate Arrays
给定一个 1~n的排列p
S[0] = p
q个操作
- 1类，选定S[s_i]把 idx>= x_i的删除
- 2类，选定S[s_i]中 所有 值 > v_i的删除
- 操作后 让S[i]=删除的原顺序的序列，并输出S[i]的长度
n 2e5
q 2e5
6s
1024mb
我的思路
二维平面点 (i,p[i]) 然后 每个序列对应一个矩形
每个操作对应一次矩形分割
用 vector<map>的fenwick
但是 似乎多写了一层二分，多了log 导致acx36,tle x25
我这个似乎是$Q(\log N)^3+N(\log N)^2$
题解
反向合并技术
如果倒着看,合并两个长度$a,b$的序列，$O(1+\min(a,b)\log\min(a,b))$
// 也就是拆分的时候时间复杂度为 拆分后两个中短的那个
总复杂度为$O(Q+N(\log N)^2)$
考虑基于$std::set$ (平衡二叉树)来管理$(i,a_i)$和$(a_i,i)$
所以, 实现逻辑就是
每次 操作判断操作的多还是剩下的多来决定实际操作的是少的部分
而实际操作的内容，是通过for 元素 + 每次$O(\log N)$的操作
啊？好有道理！
核心的原理 和 做启发式合并 小的向大的合并的有点像，这是每次拆，都是拆小的那一半，所以第一次最多能操作n/2的，第2+3次最多操作n/2,第4+5+6+7次最多操作n/2,每个单元素是O(log N)操作
总结
G:
啊 不是 洛谷一堆人用神奇高级数据结构 单log过题了？？？？
然后学了一下
std::set.emplace_hint,可以指定位置的插入set减少插入后排序的消耗
noexcept 保证不抛出异常
std::size
1 | template< class C > |
啊 这个官方题解的想法 回过头来看竟然如此简单，又很有道理！！？？