Description

给出一个\(1-N\)的排列，允许不超过\(k\)次操作，每次操作交换相邻两个数，求最大字典序排列

Constraints

  • \(1 \le N \le 10^5\)
  • \(0 \le k \le 10^9\)

Solution

贪心局部解，先决定第一大的数尽量大，处理好后继续决定第二大。只需维护每步操作在\(O(logn)\)内

Code

忘记线段树怎么写了唉

51NOD-1364 最大字典序排列