本文于 github 博客同步更新。

今天打两场

byd放三道黑是吧。

第一场：

A：

CF1261F

将区间拆分为 \([x2^{i},(x+1)2^{i})\) 的形式，发现两个区间中的数两两异或后形成的仍为一个区间，将 A,B 都拆分后区间两两异或会得到 \(O(n^2\log^2n)\) 个区间，取并即为答案，但复杂度无法接受。

发现对于两个区间 \([x2^i,(x+1)2^i),[y2^j,(y+1)2^j),i>j\)，其异或后得到的结果仍是高位固定，后 \(i\) 位任意取，也就是第二个区间中有一段是不用考虑的，这是因为这一段在第一个区间中是任意取的。在线段树上就是只用考虑同一深度的区间，这样得到的区间个数就为 \(\mathcal O(n^2\log n)\) 了。

用线段树来实现即可，dfs 的过程中记录当前高位的异或值，当有区间被完全覆盖后就返回。

B：

CF1268E

首先考虑一棵树的情况，设一开始 \(f[i]=1\)。

把边按边权从大到小插入，假设插入边 \((u,v,i)\)。

显然 \(f[u]=f[v]=f[u]+f[v]\)。

考虑仙人掌的情况，先考虑一个环，无非就是链接最小边的时候，最大边两端的会被多算一次，减掉即可。

设 \(g[i]=f[u]+f[v]\)：

那么就是 \(f[u]=f[v]=f[u]+f[v]-g[\max(C)],g[i]=f[u]+f[v]\)，\(\max(C)\) 表示当前环上的最大边。

C：

P7729

没改动。

第二场：

没打呢。