ABC256

ABC256

• A

随便搞，标题即答案

• B

为啥每次 B 的 statement 都那么怪/fn

成功看错题意 WA 了一发

大概做法就搞个前缀和数组 $s$，如果 $s_n-s_{i-1}>3$ 就说明第 $i$ 个棋子被移出了，$\Theta(n)$

• C

好像是数学里幻方的一种变形，大概填几个就会发现任意 $4$ 个不存在三点共线（这里的线指水平线和竖直线）的位置就能唯一确定一个 $3\times3$ 方格

譬如选择 $a,b,d,e$，由 $a,b$ 得 $c$，由 $a,d$ 得 $g$，由 $e,b$ 得 $h$，由 $d,e$ 得 $f$，由 $c,f$ 得 $i$，只需验证 $g,h,i$ 即可确定取舍，$\Theta(n^4)$

• D

好无聊的模拟题 原题

按左括号排序，排完后从左到右扫

• 扫到左边界小于等于合并后大区间的右边界的，将该区间并入，右边界取大区间和此区间的最大值
• 扫到左边界大于合并后大区间的右边界的，输出大区间，以此区间为新的大区间

最后输出最后一个大区间即可

接下来有趣了起来

• E

This problem is a bit difficult

说句闲话，出题人都说难了

确实是一道非常有趣的图论题

将其转化为一个图，即每个点出度为 1 的一张有向图

在这样的一张图中，对于每一个连通子图（每一个点均能到达其他所有点的图），这个连通子图必定是一个环

感性理解一下肯定是对的，就不作严谨证明了

扔个官方题解的数学归纳法证明，大概就是对入度进行分类讨论

所以就得出一个结论：如果没有环，那么答案就是 0

如果有环，就得将环切成链，这时就会有人不高兴了（“gains frustration ”，姑且译为不高兴吧，总比某些译为仇恨颓丧什么的好一点）

有几个人？怎么剖？

答案是有一个，因为只会切掉一条边，那么对于一个环，如果它的节点为 $v_1,v_2,···v_m$，那么切环的总不高兴值即 $\min\limits_{i=1}^m C_{v_i}$

找到环跑一下即可

• F

推式子：

对于每一个 $x$,$A_x$ 在 $B_y,C_y,D_y(x\leq y)$ 中各要算几次（不妨记为 $f(B_y),f(C_y),f(D_y)$）：

$f(B_y)=1$

$f(C_y)=\sum\limits_{i=x}^yf(B_i)=y-x+1$

$f(D_y)=\sum\limits_{i=x}^yf(C_i)=\dfrac{(y-x+2)·(y-x+1)}2$

所以就有

$D_x=\frac12\sum_{i=1}^xi^2A_i-\frac{2x+3}2\sum_{i=1}^xiA_i+\frac{(x+1)(x+2)}2\sum_{i=1}^xA_i$

然后线段树单点修改单点求值，维护 $i^2A_i,iA_i,A_i$，单次 $\Theta(\log n)$，总共 $\Theta(n\log n)$，连 pushdown 都不用写

所以我的推式子实在是太菜了呜呜

• G

DP

然而并没有看懂什么，更不懂 $\Theta(D\log N)$ 是什么

• Ex

哈哈官方题解有汉字/se吉老师线段树！珂朵莉树！

显然的，操作 1 没法用 lazytag 进行区间维护，所以用普通的线段树肯定不行

但是对于每次操作 1，其区间和至少被减半了，有些数甚至变成 0，这是解题的关键

法一：

搞一棵珂朵莉树 link，可以用 assign 实现操作 2，随便把 calP 函数改改就能实现操作 3

现在是操作 1 的问题

考虑遍历整棵树，对于一段区间，其值是一样的，于是除完之后的结果也是一样的，也就是说，操作 1 并没有改变集合的个数

考虑一个优化，如果一段区间的数被除成 0，就可以删掉了，所以操作 1 可以减小集合的个数

这样就很 easy 了，我珂朵莉树天下无敌！

https://atcoder.jp/contests/abc256/submissions/32582498 不优化的珂朵莉树，可见只剩 4 个点了，优化完后可能会 TLE*2（https://atcoder.jp/contests/abc256/submissions/32626831），然后就过不掉了，哈哈

这时候就得套一棵线段树，维护普通的区间和，区间除（确保区间内的数都是一样的，即在珂朵莉树操作 1 的时候 update 一下 it->l,it->2,it->v/w）这样复杂度就正确了，$\Theta((N+Q)\log N\log \max(A))$

法二

吉老师线段树，可是我并不会...

https://codeforces.com/blog/entry/57319各位神仙自己看吧/kk