这里有一篇弱化版的题解,本题题意可以看弱化版。 这个做法复杂度是 O(nlog2n)O(n \log^2 n)O(nlog2n),能解决约束形如 0≤li≤ri≤n0 \le l_i \le r_i \le n0≤li≤ri≤n 的情况,即每个盒子要求放置球数的区间不同,且值域是 nnn。 本题 li=0,ri=1l_i = 0, r_i = 1li=0,ri=1,且 n≤2×105n \le 2 \times 10^5n≤2×105,按理来说是能跑过的,但是它很快就 T 了。 本题在 SPOJ 上的所有提交均不晚于 2016 年,最优解耗时 0.00s,且无法查看代码。
有没有好哥哥帮帮我,AC 本题~❤