Warning: session_start(): open(/tmp/sess_3308ca3eba83360a6993936432d1ea92, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 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