D. Monocarp and the Set

题目要求

• 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 ?

就是从左往右插入数据如果插入后在当前排最大的话就是>,最小的话就是<,其他?

求有多少种插入数据的方法

可以从后往前看，如果是>就删除当前所有数据中最大的数,<删除最小的数   两个都只有1种选择

?就删除最大最小数除外任意一个数  设当前有x个数 就有x-2种选择

最后再把选择数乘一下就行了

同时第一个数一定不能是？

#define int long long
const int mod = 998244353;
int qpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res;
}
signed main()
{
	ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	int n;
	int q;
	string s;
	cin >> n >> q >> s;
	int ans = 1;
	for (int i = 1; i < n - 1; i++) {
		if (s[i] == '?') {
			ans = ans * i % mod;
		}
	}
	auto res = [&]() {
		cout << (s[0] == '?' ? 0 : ans) << '\n';
	};
	res();
	while (q--)
	{
		int i;
		char c;
		cin >> i >> c;
		i--;
		if (i != 0 && s[i] == '?') {
			ans = ans * qpow(i, mod - 2) % mod;
		}
		s[i] = c;
		if (i != 0 && s[i] == '?') {
			ans = ans * i % mod;
		}
		res();
	}
}