byd放三道黑是吧本文于 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
没改动。
第二场：
没打呢。
