今天打两场

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

没改动。

第二场：

A：

二分安全系数，每个点的 $L,R$ 可以看成赋值 $0/1$ ，对不能同时选的的点对进行约束，2-SAT 即可。

B：

令 $f[i]$ 表示从 $[L, R]$ 中选择出不完全相同的 $N$ 个数，$GCD$ 为 $i\times K$ 的方案数，

则：

$$f[i]=(\lfloor\frac{R}{Ki}\rfloor-\lfloor\frac{L-1}{Ki}\rfloor)^N$$

其中完全相同的和 $i\times K|GCD$ 的方案数为：$(R-L+1)+\sum\limits_{i|j,i\neq j}^{j\times K<R-L}f[j]$

这部分是重复的，容斥，得：

$$f[i]=(\lfloor\frac{R}{Ki}\rfloor-\lfloor\frac{L-1}{Ki}\rfloor)^N-(R-L+1)-\sum\limits_{i|j,i\neq j}^{j\times K<R-L}f[j]$$

从大到小枚举 $i$ 进行 $DP$ 即可，结果即为 $f[1]$，但是需要特判掉 $K\in[L,R]$ 的情况。

$N$ 比较大，快速幂需要用一下欧拉定理。

C：

将每个点点权转为到根路径和，查询即为查询子树内最大值，修改为子树内加减，树剖 + 线段树即可。