思路

首先因为电视台比广告多一个信息，所以通常来说枚举电视台是更有前途的。

因此枚举每一个电视台，考虑所有广告的贡献。对于一个电视台，\(c_i\) 是定值，也就是找到所有广告与电视台所表示区间交得最多的那一个。

假设枚举的电视台控制了 \([L,R]\) 区间，则广告 \([l,r]\) 会有三种方式对 \([L,R]\) 有交：

1. \(L \leq l \leq r \leq R\)。
2. \(l \leq L \leq r \leq R\)。
3. \(L \leq l \leq R \leq r\)。

特别的，在这里我们把 \(l \leq L \leq R \leq r\) 归于第二种或者第三种均可。

对于第二、三种情况太平凡了。定义 \(Min_i\) 表示所有右端点为 \(i\) 的广告最左的左端点的位置；\(Max_i\) 表示所有左端点为 \(i\) 的广告最右的右端点位置。

第二种情况，因为 \(l \leq L\) 我们只关心右端点能最远拓展到哪里，因此查询 \([1,L - 1]\) 区间 \(Max_i\) 的最大值；第三种情况同理，查询 \([R + 1,n]\) 区间 \(Min_i\) 的最小值。