HZOJ
写在前面
CSP后第一场。回归CSP前的手感，就是啥也不会。今年第一场4.5h的模拟赛，确实没有4h时间紧张了，还有大把时间犯困，可能是CSP破防了摆烂了吧。今天提前出成绩了，大概就是挂如分了，估计得卡着七钩线。祝我七钩吧。CCF少爷机有点实力在的，正确复杂度被卡，错误复杂度乱创。实在是没招了。只能安慰自己好歹有个一等。
这两天的月亮挺好看，那就放首和月亮有关的歌吧。其实想放《Dear Moon》或者《Straberry Moon》的，奈何找不到合适的歌词。
《Follow the Moon》
见上げれば 会えるはずと
いつだって I know you are there
缲り返す Illusions escape
火が灯る As I close my eyes
I follow the moon 夜空で
见失ったとしても 明日は会えるはずと
信じているの Oh-Woah ×3
星が照らす 道しるべ
神様がくれた仕挂け
I follow the moon 夜空で
见失ったとしても 必ず会えるはずと
信じているの Oh-Woah ×3
Whatever takes me there...
I follow the moon 夜空で
见失ったとしても 明日は会えるはずと
信じているの
A. 数字(math)
万年不见的高精度。赛时竟然写出来了高精乘高精。猜结论把样例都过了，然后因为没有剪枝挂了10pts。
B. 游戏(game)
题意是给出一个环形序列，两个人轮流选择取走一个数。除了第一个数外，其余数必须是之前取过的数的相邻数。求两个人都用最优策略的前提下先手的最大和是多少。
猜结论但假了。捆绑测试一分不得。考虑先手的以一个点\(x\) 为起点，则其能选的区间是\([L,R]\) 的一个连续区间。考虑后手的策略。由于总和一定，那么后手的策略就是要使先手的和尽量小。考虑先手在区间\([l,r]\) 和最小，那么后手就要使先手只能取那个区间内的数。考虑使先手起始点和后手起始点沿分界点的连线对称。这样如果先手往上选后手也往上选，反之亦然。那么考虑先手以每个位置为起点，该位置的答案就是可贡献区间和的最小值。答案就取最大的最小值即可。维护的话线段树build，区间求min即可。
C. 海报（posters)
不会，懒得改，咕了。正解是搜索加剪枝。
D. 环（ring)
特殊性质打了60pts。题意是给定一个序列，每个位置都在一个环上。有两种操作。对于操作1，给出区间左右端点，区间求和；对于操作2，给出环的编号，代表该环上的权值顺时针移动一个位置。
正解是根号分治。考虑到大小不大于\(\sqrt n\) 的环至多有\(\sqrt n\) 个，所以对于这些环上的修改直接暴力修改即可。对于大小大于了\(\sqrt n\) 的环，也至多有\(\sqrt n\) 个。我们考虑修改时维护一个标记，由于所有权值间的相对位置不发生改变，所以可以根据标记的大小推出实际的范围。对于询问，我们可以树状数组维护小环的和，log查询，大环就直接二分查找前缀和即可。复杂度\(O(q\sqrt n+q\sqrt nlogn)\)。