ZigZagK的博客
[扫描线+双标记线段树]2020 ICPC EC-final G【Prof. Pang's sequence】题解
题目概述Prof. Pang's sequence解题报告首先根据经典套路,我们记录 $pre_i$ 表示 $i$ 上次的出现位置,这样的话对于一个左端点 $L$ ,只有 $pre_i<L...
[FWT+高维前缀和]2020 ICPC 沈阳 M【United in Stormwind】题解
题目概述United in Stormwind解题报告太久没做过这种题了,其实非常套路。题目里给出了 $n$ 个 $01$ 串,把两个串异或就可以得到两个串不同位置的集合。首先我们可以利用FWT...
[Trie+复杂度分析]2020 ICPC 济南 K【Kth Query】题解
题目概述Kth Query解题报告这道题给了我01 Trie的新思路QAQ。首先我们考虑没有限制的情况,我们对于每个节点 $x$ 维护 $MIN_{x,k}$ 表示 $x$ 子树中第 $k$ 小...
[思维+二分+ST表]2020-2021 ACM-ICPC Brazil Subregional Programming Contest M【Machine Gun】题解
题目概述CF GYM 102861M解题报告首先要仔细读题,题目保证了覆盖的点的个数总和不超过 $10^6$ ,因此只需要想办法快速找到被覆盖的点就行了。如果按照题目里的说法很难快速查找,因此我...