310778: CF1886D. Monocarp and the Set
Description
Monocarp has $n$ numbers $1, 2, \dots, n$ and a set (initially empty). He adds his numbers to this set $n$ times in some order. During each step, he adds a new number (which has not been present in the set before). In other words, the sequence of added numbers is a permutation of length $n$.
Every time Monocarp adds an element into the set except for the first time, he writes out a character:
- if the element Monocarp is trying to insert becomes the maximum element in the set, Monocarp writes out the character >;
- if the element Monocarp is trying to insert becomes the minimum element in the set, Monocarp writes out the character <;
- if none of the above, Monocarp writes out the character ?.
You are given a string $s$ of $n-1$ characters, which represents the characters written out by Monocarp (in the order he wrote them out). You have to process $m$ queries to the string. Each query has the following format:
- $i$ $c$ — replace $s_i$ with the character $c$.
Both before processing the queries and after each query, you have to calculate the number of different ways to order the integers $1, 2, 3, \dots, n$ such that, if Monocarp inserts the integers into the set in that order, he gets the string $s$. Since the answers might be large, print them modulo $998244353$.
InputThe first line contains two integers $n$ and $m$ ($2 \le n \le 3 \cdot 10^5$; $1 \le m \le 3 \cdot 10^5$).
The second line contains the string $s$, consisting of exactly $n-1$ characters <, > and/or ?.
Then $m$ lines follow. Each of them represents a query. Each line contains an integer $i$ and a character $c$ ($1 \le i \le n-1$; $c$ is either <, >, or ?).
OutputBoth before processing the queries and after each query, print one integer — the number of ways to order the integers $1, 2, 3, \dots, n$ such that, if Monocarp inserts the integers into the set in that order, he gets the string $s$. Since the answers might be large, print them modulo $998244353$.
ExamplesInput6 4 <?>?> 1 ? 4 < 5 < 1 >Output
3 0 0 0 1Input
2 2 > 1 ? 1 <Output
1 0 1Note
In the first example, there are three possible orderings before all queries:
- $3, 1, 2, 5, 4, 6$;
- $4, 1, 2, 5, 3, 6$;
- $4, 1, 3, 5, 2, 6$.
After the last query, there is only one possible ordering:
- $3, 5, 4, 6, 2, 1$.
Output
Monocarp有n个数字1, 2, ..., n，并有一个初始为空的集合。他将这些数字以某种顺序加入集合n次，每次加入一个之前未在集合中出现过的数字，即加入数字的序列为长度为n的一个排列。
除了第一次之外，每次Monocarp向集合中加入元素时，他都会写出一个字符：
- 如果要插入的元素成为集合中的最大元素，Monocarp写出字符">"；
- 如果要插入的元素成为集合中的最小元素，Monocarp写出字符"<"；
- 如果都不是，Monocarp写出字符"?"。
给你一个由n-1个字符组成的字符串s，代表Monocarp写出的字符（按他写的顺序）。你需要处理m个关于字符串的查询。每个查询的格式如下：
- i c —— 将s_i替换为字符c。
在处理查询前以及每次查询后，你需要计算有多少种不同的方式对整数1, 2, 3, ..., n进行排序，使得如果Monocarp按照这个顺序将整数插入集合，他将得到字符串s。由于答案可能很大，结果对998244353取模输出。
输入输出数据格式：
输入：
- 第一行包含两个整数n和m（2 ≤ n ≤ 3 * 10^5; 1 ≤ m ≤ 3 * 10^5）。
- 第二行包含一个由'<', '>', '?'组成的字符串s，恰好有n-1个字符。
- 接下来m行，每行代表一个查询，包含一个整数i和一个字符c（1 ≤ i ≤ n-1; c是'<', '>', 或'?'中的一个）。
输出：
- 在处理查询前以及每次查询后，输出一个整数，表示有多少种排序方式，使得Monocarp按这个顺序插入整数得到字符串s。结果对998244353取模输出。题目大意： Monocarp有n个数字1, 2, ..., n，并有一个初始为空的集合。他将这些数字以某种顺序加入集合n次，每次加入一个之前未在集合中出现过的数字，即加入数字的序列为长度为n的一个排列。 除了第一次之外，每次Monocarp向集合中加入元素时，他都会写出一个字符： - 如果要插入的元素成为集合中的最大元素，Monocarp写出字符">"； - 如果要插入的元素成为集合中的最小元素，Monocarp写出字符"<"； - 如果都不是，Monocarp写出字符"?"。 给你一个由n-1个字符组成的字符串s，代表Monocarp写出的字符（按他写的顺序）。你需要处理m个关于字符串的查询。每个查询的格式如下： - i c —— 将s_i替换为字符c。 在处理查询前以及每次查询后，你需要计算有多少种不同的方式对整数1, 2, 3, ..., n进行排序，使得如果Monocarp按照这个顺序将整数插入集合，他将得到字符串s。由于答案可能很大，结果对998244353取模输出。 输入输出数据格式： 输入： - 第一行包含两个整数n和m（2 ≤ n ≤ 3 * 10^5; 1 ≤ m ≤ 3 * 10^5）。 - 第二行包含一个由'<', '>', '?'组成的字符串s，恰好有n-1个字符。 - 接下来m行，每行代表一个查询，包含一个整数i和一个字符c（1 ≤ i ≤ n-1; c是'<', '>', 或'?'中的一个）。 输出： - 在处理查询前以及每次查询后，输出一个整数，表示有多少种排序方式，使得Monocarp按这个顺序插入整数得到字符串s。结果对998244353取模输出。