#P6881. duke

    ID: 6712 传统题 500~2000ms 512MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>难度分类提高+/省选-图论Tarjan 强连通分量算法缩点线段树优化建图CF2300

duke

Duck

题目描述

有 NN 个元素,编号为 11 至 NN。你需要把它们排成一个排列。

对于元素 ii,如果至少有一个编号属于闭区间 [li,ri][l_i,r_i] 的元素排在它前面,就计入贡献 viv_i。如果不存在这样的元素,贡献为 00。即使有多个符合条件的元素,viv_i 也只计入一次。viv_i 可以为负,条件满足时必须计入。元素 ii 本身不会排在自己前面。

求所有排列中贡献之和的最大值。

输入格式

第一行一个整数 NN。

接下来 NN 行,第 ii 行三个整数 li,ri,vil_i,r_i,v_i。

输出格式

输出一行一个整数,表示最大总贡献。答案可以为负数。

样例

2
2 2 1
1 1 2
2
2
2 2 -1
1 1 -1
-1

样例 2 中,无论如何排列,后一个元素的贡献均为 −1-1。

数据范围

1≤N≤2×1051\le N\le2\times10^5,1≤li≤ri≤N1\le l_i\le r_i\le N,∣vi∣≤104|v_i|\le10^4。

测试集 分值 NN 的上界
1 25 5
2 10
3 20
4 10 10310^3
5 5×1045\times10^4
6 2×1052\times10^5

本 Hydro 训练版补充保证

考虑只包含 vi<0v_i<0 的元素的有向图。若 i≠ji\ne j 且 j∈[li,ri]j\in[l_i,r_i],则这两点之间有一条 i→ji\to j 的边。每个测试点中,这张图的每个强连通分量至少符合下列一种情况:

  1. 大小不超过 2020。
  2. 分量内每个点恰有一条出边,构成一个有向环。
  3. 分量内每条边都有反向边。将分量内的点按原编号排序,给每个点补上指向自身的边后,每个点的出邻居占据连续的一段。

只对既不符合第 2 条也不符合第 3 条的分量计算 ∑C∣C∣2∣C∣\sum_C |C|2^{|C|}。每个测试点这一总量至多为 3×1073\times10^7。上述保证只限制测试数据的结构,排列和计分规则如题意所述。