分类讨论。
二分。
题意：给定一个字符串 \(s\)。记 \(s_i\) 为将 \(s\) 删去 \(i\) 个字符，使得剩余字符串字典序最小得到的字符串。令 \(S=s_0+s_1+\dots+s_{sz-1}\)。现在要询问 \(S[pos]\) 是哪个字符。
通过一些取模，加减可以求出，我们是要求 \(s_{x}\) 的第 \(y\) 个字符。
要字典序最小，显然应该删去最靠前的，比后一个字符大的字符。
这个操作类似单调栈，我们就按单调栈依次加入字符，如果栈顶比现在的大，就 pop，同时记录删去了多少个字符。
一个字符串 \(s\)，初始为空。将 \(1\sim n\) 按某种顺序加入一个序列中，除了第一个元素外，执行以下操作：
-
如果新加入元素是最小值，在 \(s\) 末尾加一个
<； -
是最大值，加一个
>； -
否则加一个
?。
现在告诉你最后的 \(s\)，你需要回答有多少种加入顺序能满足 \(s\)。另外，还有 \(m\) 次单点修改，每次将 \(s\) 的一个字符改成 >,<,? 中一个。需要在每次修改后都回答一次答案。
将加入序列反过来，看作在 \(1\sim n\) 中删除元素。发现如果是 >,<，只有一种方案；而 ? 的方案数就是当前个数 - 2。所以若 \(s_i=?\)，则 \(ans\times (i-1)\) 即可。
还有个问题：若 \(s_1=?\)，\(ans=0\)。所以还需要记录 \(ans2\) 为 \(s_{2\sim n}\) 的答案。
标签：字符,CF1886,加入,sim,字符串,删去,个字符 From： https://www.cnblogs.com/FLY-lai/p/18007909