ZROI 暑期高端峰会 A班 Day1 序列数据结构

FBI Warning:本文包含大量人类的本质之一

CF643G

维护一个序列,可以区间赋值,求区间中出现超过 \(p\%\) 的数。

允许输出不对的数,允许重复输出,但是所有对的数都一定要输出。而且个数不能超过 \(\lfloor\frac{100}{p}\rfloor\)。

\(n\le 1.5\times 10^5,p\ge 20\)。

假设就求超过 \(20\%\) 的数。

假如区间长度是 \(k\),那么找出区间第 \(\frac{i}{6}k(1\le i\le 5)\) 大。直接输出即可。

证明?想象把所有数排序后,称第 \(\frac{i}{6}k\) 的位置是关键位置。那么如果一个数至少出现了 \(20\%\),就会出现在至少一个关键位置。

所以输出所有关键位置的数就不会遗漏了。

然而有区间赋值操作……挂了……

考虑另一种做法。怎么线性求呢?

如果是要求至少 \(50\%\) 的,每次两个数打架,擂主被打倒了就换擂主。

\(20\%\) 同理。维护 \(5\) 个擂主,每次一个新数和每个擂主都打架。注意的是如果新数和擂主一样,生命值 \(+=4\)。

放到线段树上,每个节点维护 \(5\) 个擂主,pushup 时更新一下即可。

HDU6087

给两个序列 \(a,b\),初始 \(a,b\) 一样,支持区间求和,

for(int i=l;i<=r;i++) a[i]=a[i-k]
for(int i=l;i<=r;i++) a[i]=b[i]

这三种操作。

\(n,q\le 10^5\),内存限制 64M

明显是区间复制操作。

注意的是复制 \(m\) 次区间不能暴力做,可以类似快速幂的方式。

对于返回操作,复制个节点即可。

时间复杂度 \(O(q\log^2n)\)。

可以过一段时间就重构整棵树,同时垃圾回收,空间就不会炸了。

CF453E

长度为 \(n\) 的序列 \(s\),每过一个时刻 \(s_i+=v_i,s_i=\min(s_i,m_i)\)。

\(q\) 次操作,每次询问区间 \(s\) 的和,同时把 \(s\) 都置为 \(0\)。

\(n,q\le 10^5\)

先考虑每次操作都是全局的情况。(中间会有时刻没有操作,别想了!)

按 \(\lceil\frac{(m_i-s_i)}{v_i}\rceil\) 排序,也就是能量回复满的时间。每次询问二分一下即可。

对于任意区间呢?

发现序列会被分成若干段,每一段内的最后一次清零时间一样。每次操作就是多一个段,删掉完全被覆盖的段,边界段断开。段数的总个数是线性的。

回答询问时,因为段数线性,可以大暴力枚举覆盖的每一段,对每一段分别求。除了初始的一整段稍微注意一下,剩下的其实就是询问区间小于某个数的 \(\lceil\frac{m_i}{v_i}\rceil\) 的 \(v_i\) 的和,和大于某个数的 \(\lceil\frac{m_i}{v_i}\rceil\) 的 \(m_i\) 的和。主席树维护即可。

CF1172F

Ouuan 场 Div1 F 题。

题面太长,不写了。

没听懂,不写了。还是看 ouuan 的题解去。(所以就是咕了)

CF1178G

掉分好场 G 题。

给两个序列 \(a,b\),\(b\) 中都是非负整数。

两种操作:区间给 \(a\) 加一个正数,求区间 \(|a|\times b\) 最大值。

\(n,q\le 2\times 10^5\)。

\(a\) 会慢慢变大,总有一个时刻会从负变正。

把序列分块,对于零散块暴力,对于整块,(咕了,以后再说)

HDU 6337

以前讲过。好像是变成括号序列然后怎么搞的。

咕了。

ICPC2018 Beijing E

维护一个数组 \(a[0\dots 2^k-1]\):

  1. 对于 \(l\le i\le r\) 令 \(a_i'=a_{i\oplus x}\)
  2. 对于 \(l\le i\le r\) 令 \(a_{i\oplus x}'=a_i\)
  3. 对于 \(l\le i\le r\) 令 \(a_i'=a_i\oplus x\)
  4. 对于 \(l\le i\le r\) 求所有二进制中 1 的个数是奇数个的数的下标的异或和

假装 \(k\le 18\) 吧。

发现此时建线段树跟 01 Trie 很像。

对于区间 \([l,r]\) 会拆成一些区间。

对于操作 \(1\) 就相当于每个区间的子树变成了别的一棵长得一样的子树。可以可持久化 01 Trie。

对于操作 \(2\) 差不多。

对于操作 \(3\) 打个标记。

对于操作 \(4\) 记录一下子树奇数偶数的异或和就好了。

CF297E

这个图太**了,不写题面了。

对于两条线段,如果相交了连蓝边,否则连红边。那么要求的就是同色三角形个数。

可以变成求异色三角形个数。最后用总个数减。

可以变成求异色角个数。因为一个异色三角形会有两个异色角。

枚举顶点,分别计算一下蓝边数和红边数,乘起来就好了。

二维数点问题,可以瞎搞。

CF997E

原来不用析合树……

如果固定了一个区间,且 \(x,x+1\) 都在 \([l,r]\) 中,给 \(x,x+1\) 连一条边。点数-边数就是 \([l,r]\) 中的连续段个数。

(欸?不对吧???)

(于是开始思考……)

(于是掉线了)

咕了。

CF1034D

\(n\) 个区间 \([l_i,r_i]\),定义 \(f(l,r)\) 表示第 \(l\) 个区间到第 \(r\) 个区间的并的长度。求前 \(k\) 大的 \(f\) 的和。

\(n\le 3\times 10^5,k\le 10^9\)。

二分第 \(k\) 大的 \(f\) 的值,

(草又掉线了)

咕了。

CF896E

在做分块题前记得看看谁是出题人!

对每个块,每种权值维护链表。

修改时,如果 \(2x\ge len\)(\(len\) 是权值范围,一开始看成 \(10^5\)),暴力做。如果 \(2x\le len\),变成把 \(<x\) 的都 \(+x\),再打个 \(-x\) 的标记。然后更新块内权值范围。由于用链表,可以 \(O(1)\) 合并。

询问时,调用链表的长度即可。

时间复杂度:可以在 \(O(x)\) 时间内把一个块的权值范围减小 \(x\),所以如果把权值范围和 \(q\) 都看作和 \(n\) 同阶,复杂度是 \(O(n\sqrt{n})\)。

牛客4F

太长了,自己看去……

(就没上过线)

咕了。

CF1148H

升分好场 H 题。(草给我们 3600 难度的题几个意思……)

对一个初始时空的序列,支持 push_back,和询问多少个区间满足 \(\mathrm{mex}\) 为一个给定的数,强制在线。

看着难度就知道不可做。

咕了。

上一篇:ZROI 暑期高端峰会 A班 Day1 组合计数


下一篇:ZROI 菜鸡互啄杯 III