ZigZagK的博客
[二进制分块]2021牛客暑期多校训练营3 I【Kuriyama Mirai and Exclusive Or】题解
题目概述Kuriyama Mirai and Exclusive Or解题报告第一种操作没什么好讲的,我们关注第二种。这种加法和异或混合的一般都只能考虑按位统计贡献。考虑 $[L,R]$ 第 $...
[扫描线+双标记线段树]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...
ICPC2020沈阳区域赛现场赛游记
Day [-n,-2]考前天天gym VP,感觉状态神神鬼鬼的,我的发挥比较看题目。某天晚上梦见飞机坠机了,可能是某种预兆(迫真)。Day -1本来还想考前最后一场VP,结果队长睡过头了,所以就...
[仙人掌DP]BZOJ4316【小C的独立集】题解
题目概述图论小王子小C经常虐菜,特别是在图论方面,经常把小D虐得很惨很惨。这不,小C让小D去求一个无向图的最大独立集,通俗地讲就是:在无向图中选出若干个点,这些点互相没有边连接,并使取出的点尽量...
[仙人掌+圆方树]BZOJ2125【最短路】题解
题目概述给一个 $n$ 个点 $m$ 条边的连通无向图,满足每条边最多属于一个环,有 $Q$ 组询问,每次询问两点之间的最短路径。解题报告不难想到建出圆方树,然后将距离转化为圆方树上的距离。给定...
[Splay维护序列]Codeforces GYM103145F【Permutation】题解
题目概述CF GYM103145F解题报告其实两个反转操作是独立的,我们可以用两棵Splay来维护位置的序列(A树)以及数值的序列(B树)。每次询问位置 $i$ 的时候,我们先找到 $i$ 位置...