526互联

CF1886D Monocarp and the Set 题解

发布时间 2024-01-09 20:28:40作者: FOX_konata

Monocarp and the Set - 洛谷

Problem - D - Codeforces

  • 非常之降智

  • 加入一个数让他满足他是最大值需要判断前面加入的那些数中最大的是哪个，但删除一个数让他满足是最大值只需要直接把他删掉即可

  • 因此我们要反着考虑这个问题：

    • 如果当前是 <，则删除最小的数，有一种方案

    • 如果当前是 >，则删除最大的数，有一种方案

    • 如果当前是 ?，则删除不是最大和最小的数，有 \(i-2\) 种方法

  • 特殊的，如果第一个位置为 ? 肯定不可能，直接输出 \(0\)

  • 修改即预处理逆元可做到 \(O(n)\)