====== Summer Tranning Week 5 ====== ===== 比赛简记 ===== ===== Max.D. ===== ==== 专题 ==== 本周暂无 ==== 比赛 ==== 百度之星复赛（凉凉，只写了两题没拿到衣服） 一场cf div2，rating小涨 ==== 题目 ==== 暂无 ===== Hardict ===== ==== 专题 ==== 无 ==== 比赛 ==== 百度之星一场 ==== 题目 ==== 暂无 ===== MountVoom ===== ==== 专题 ==== 无 ==== 比赛 ==== 求求来点正常cf div1 遇见类似原题的题不要被轻易影响 ==== 题目 ==== 无 ====== 个人总结 ====== ===== 陈铭煊 Max.D. ===== 补题+学习 ===== 龙鹏宇 Hardict ===== 补题+整理板子 ===== 肖思炀 MountVoom ===== 该补点难题了 ====== 本周推荐 ====== ===== 陈铭煊 Max.D. ===== ===来源：=== [[https://ac.nowcoder.com/acm/contest/5674/C|牛客2020多校训练第九场 C Groundhog and Gaming Time]] ===标签：=== 区间，动态规划，线段树 ===题意：=== 给出$n$个区间$[L_i,R_i]$，等概率取其中一个子集$a$，得到的贡献为$|[L_{a_1},R_{a_1}]\cap[L_{a_2},R_{a_2}]\cap...\cap[L_{a_m},R_{a_m}]|^2$，求贡献的期望值（模$998244353$意义下）。 $1\le n\le 5\times 10^5,0\le L_i\le R_i\le 10^9$ ===题解：=== 这里给出两个方法，一种是大家用的比较多的方法；另一种是$dp$通解，也就是不仅可以做平方贡献，随便和区间有关的贡献都可以。 问题首先转化为所有子集的贡献和。 将区间交的平方，看作是区间交里面元素两两配对的个数，进一步，是左点。那么问题就是每一对元素，要求出其被区间交覆盖的总次数。我们将所有区间按左端点从小到大排序，按顺序加入区间$i$，这样我们看每个离散化后的原子区间，被区间覆盖的次数，就是左到右不递增了。那么必包含区间$i$时，每个原子区间的每个配对右点在区间交中带来的贡献数的和，就是$（原子区间长度乘以左边的点的个数的和的两倍+原子区间长度平方）\times（2^{覆盖数}-1）$。 这些信息，包括次数和乘积等，可以用线段树加以维护，每一次区间更新，然后区间查询即可。 第二种方法是题解的方法： - 线段的交取决于最大的左端点以及最小的右端点，同时维护两个东西比较困难。 - 所以我们先按照线段左端点从大到小排序，那么排序后的线段的交取决于最小的右端点，以及第一个被选 择的线段的左端点。 - 考虑到直接维护右端点比较麻烦，所以考虑在一开始就钦定一个点 X 作为最小的右端点。 - 所有右端点大于等于 X 的线段都可以选择，反之不能选择。 - 其次被选择的线段中至少有一个线段的右端点等于 X 那么这个方案就是合法的。 所以可以写出一个$O(n^2)$的$dp$： - $dp[i][j][0/1]$代表前$i$个线段中钦定的$X$为$j$，是/否有一个线段的右端点为$X$ - $dp[i][j][0/1]=dp[i-1][j][0/1]\ (jR[i])$ - $dp[i][j][0]=dp[i-1][j][0]\times 2+(j-L[i])^2,dp[i][j][1]=dp[i-1][j][1]\times 2\ (L[i]\le j