JZTXT

CF1085F

发布时间 2023-11-19 16:34:12作者: HBWH_zzz

\(n\) 个人排成一排，每个人有石头剪刀布中一个手势，每次选择相邻两人石头剪刀布，若分出胜负则将负者剔除序列，否则选择一人剔除，问有多少人可能成为最后剩下的人。\(q\) 次询问，每次单点修改。\(n,q\leq 2\times 10^5\)。

简单题。手推一下发现一个人胜利条件等价于两边均满足以下条件之一：

  • 有小于他的手势
  • 全是和自己一样的手势

然后拿线段树维护一下三种手势第一次出现，最后一次出现，最长前缀，最长后缀，区间和即可。