[BZOJ2138]stone | K-D Space

[EndSaH]

https://endsah.cf/blog/BZOJ2138-stone/#more

Description有 $n$ 堆石子，$m$ 次操作。第 $i$ 次操作是在 $[l, r]$ 这堆石子中选出至多 $k$ 个石子扔掉。问在保证前 $i - 1$ 次操作全部最优（即扔掉石子最多）的前提下，第 $i$ 次操作最多能扔出多少石子。 操作区间互不包含。 设 $a _i$ 表第 $i$ 堆石子数目，则有： $$1 \le m \le n \le 40000, 1 \le a _i \