省选联考 2020 游记

#### Upd 挂了三十五分 坐标 CQ，考 A 卷。 ## Day 1 上来花了两个小时打 t1 的 $n^2$ 暴力，不知道自己怎么想的（当然中间去把 t2 30，t3 15 写了） 然后发现 $n\log ^2 n$ 很好写就写了。最开始写的线段树，后来大概在 11:00 时换成了树状数组。之后发现稍微转化一下就能 $O(n\log n)$ 就开写了。大约在 12:30 时过了自己的数据。跑了下极限数据，发现要 7s…… 加了快读快输就 2.5s 了。 12:50 时 发现要离散化，就匆忙加了个。还是很慌，不知写对否。极限数据要 2.8s。 期望得分 $100+30+15=145$。遗憾是没做出来 t2。我省选前一天才搬过一样的题啊啊啊啊啊啊 希望不要挂分（ ## Day 2 先把三题 $30+10+50$ 暴力写了。写完大概十点了 。 然后去搞 t2。发现可以转化成区间加区间 xor 但是似乎是不可做的……然后发现树的特性很有用，可以直接继承重儿子信息，于是就转化成了全局加 1，全局 xor。这不就是 AGC044 的 Strange Dance 吗？从低位往高位建 Trie 树上面打个 xor 标记就能维护了。 写完调完大概十二点了，极限数据要 3s。加了快读快输，vector 换成邻接表就 1.4s 了。 然后试图搞 t1，没有成功。 期望得分 $30+100+50=180$。被吊着打 /kk