Codeforces Round 588
大意
n个人 有值1~n
有m条无向边
求 图中 满足 值i>值j>值k 有多少对
q次操作 每次指定一个人 使它的值+n,并求在新的图中有多少对
数据范围
1<=n<=100000, 0<=m<=100000,0<=q<=100000
4s
256MB
题解
首先 题目的数值保证了不会有相等的值出现
显然如果根据值的大小，把无向边改成有向边 多少对 = sum{每个点 出度 * 入度}
那么如何处理更新
如果裸更新 可能遇到聚点 时间复杂度可能有O(m * q)
然后 官方题解
如果我们把点 按照 总度从大到小，从左到右排列
那么每个点和它左边点相连的个数 小于等于(根号2m)
反证， 如果存在 一个和左侧连接个数大于 (根号2m)
那么 有 左侧点个数 大于 根号2m,也有 左侧点的度 > 该点的度 >= 该点于左侧点的连接数 > 根号2m
边 >= 有左侧点度的总数 (根号2m) * (根号2m) = 2m 矛盾
???? 怎么就 q 根号2m了 TODO 官方题解这里没有看懂
cf群里的证明
感谢RUSH_D_CAT 和 QAQAutoMaton大佬
以下忽略等号的描述 sqrt(m)都视作非整数[因为在意的是复杂度,是否精确讨论等号 对复杂度没有影响
提供的把点分为大点和小点
大点 度> sqrt(m)
小点 度< sqrt(m)
同上的反证法可以得到 大点的个数 < sqrt(m)
每次更新一个小点 时间复杂度 sqrt(m)
对于一个大点 总的时间复杂度 O(m+q)
因为只有第一次更新大点会达到 O(m)的复杂度
对于非第一次更新大点 最多更改的点 = 上一次更改到当前更改的点 = O(q)
所以总的时间复杂度
O(n*sqrt(m) + sqrt(m) * (m+q))
常数优秀的话能过 10**^7.5 = 31622776.60168379
注意的是 m+q 这个上界 也是难达到的? (怎么证一个更小的范围)
代码
这题难点不在代码 在证明
因为我看完题也就脑糊了这个算法估计能过，但不知道怎么证明