CVBB ACM Team

考场构造了两个小时也没玩明白

zyy: done

pmxm：从大到小煎饼即可，考虑 99,99,2 可以知道分成两次烤的煎饼是不会有问题的。

xsy：done （在 99 99 2 之前没搞明白怎么分成两次wa了一发）

pmxm：类似昨晚cf，把矩形都映射到$[0,d] \times [0,d]$上就好，每个矩形用四个端点各自映射一次方便code，然后只需要任选一个未被覆盖的点作为兔子的出发点就行。

zyy: done

zyy：是不是答案只有两个区间交 (WA了一发)

pmxm&zyy： 可以考虑若最后区间交是$n$段，那么转换成每个大区间恰好不包含某一个最终解里没有包含的段即可。 如$(a,b),(c,d),(e,f)$ 那么转换成 大区间为$U - (b,c), U - (d,e), U - (f,a)$即可。

zyy: done

xsy & pmxm : 猜想，奇度数的连通块从奇度数的点双删一个点就好了。（结果否定了自己）

原因：若删掉的是割点，直接判定割去后各个子连通块的奇偶性即可。

pmxm: done https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48397358

pmxm: 考场想到直接推期望就好了$x \oplus y > x$会被分成$\log$段，然后发现不会做每个概率都不一样的情况。

实际上转移方程是卷积的形式，所以用分治处理卷积转移的方式就可以了。

题意：强制在线，动态树上加点，询问子树内的某一个颜色的个数。

$n \log^2 n$ 做法，开颜色棵splay，splay的顺序为当前树的dfs序，那么子树问题变成splay上一段区间的查询问题，而子树查询还需要知道子树对应的区间的结尾和开头各是哪里，注意到$u$子树内一点$v$满足$lca(u,v) = u$，用这个性质可以寻找dfs序上最后一个满足该性质的点，故在splay上二分查询满足lca性质的最后一个点即可解决问题。

分块：设置块大小$BLK$，暴力建树、查询，树大小超过$BLK$就把这部分按dfs序加到序列中，查询时按$u$在树中和序列中两种情况处理。(邻接表用vector太慢了，实际上和log^2差不多)