A.
没想到是暴力,做的很晚
B.
手玩一下即可
C. Medium Design
给定一个长为 \(n\) 的数组 \(a\) ,和若干条线段 \([l_i,r_i]\) ,你可以选择这其中的任何若干条线段,并让 \(a_l\sim a_r\) 均 \(+1\).请你计算可以得到的 \(\max(a)-\min(a)\) .
这题本来想的是先把所有的加进去,得到最大值后删去不包含最大值的线段,但是可能有多个最大值,这就很难搞了.
\(Solution\)
我们找 \(1\sim m\) 中任意一点 \(x\) ,假如这个点是要求的最大值的点,那么删去其他不包含该点的点不影响结果,所以我们可以只考虑包含了这个点的线段,一定有 \(a_i\geq a_1 ,i\in [1,x]\) , 并有 \(a_i\geq a_m ,i\in [x+1,m]\) ,那么答案一定是 \(\max(a_x-a_1,a_x-a_m)\) ,但是注意,这时候的 \(a_1,a_m\) 显然是删去了我们前面说的那些不必要的边后的 \(a_1,a_m\) ,如果对每一个 \(x\) 我们都判断一遍线段,刨除不包含 \(a_x\) 的线段,那会使得时间复杂度达到 \(O(n^2)\) ,这是显然不可行的.
可以提前把所有的 \(a_1,a_m\) 上的边删掉,删掉了包含 \(a_1\) 且不包含 \(a_x\) 的边,同时包含 \(a_1\) 和 \(a_x\) 的边被删掉并不会影响答案.此时答案就是 \(\max(a_i)\)
标签：904,包含,max,线段,删掉,Codeforces,删去,Div,最大值 From： https://www.cnblogs.com/oijueshi/p/17786534.html