D. Monocarp and the Set

题目大意，给你一个表示排列元素的序列，包括 <?> , 其中 < 表示在之前是最小的 > 表示在之前是最大的，否则就是 ? ，有 mm 次操作 ,每次可能修改下标的值，你这个表示序列的序列最多能表示多少种排列。

先不考虑修改，对于最初始的序列，第一个绝对不能是问号，然后从后往前看，如果不是问号就只能填一种东西，是问号可以填 x−2x-2 (假设当前下标为 xx ) 个数。以此可以统计答案。

修改也同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=300300;
const int modp=998244353;

int n,m,a[maxn];

int ksm(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1) ans=ans*x%modp;
		x=x*x%modp;
		y>>=1;
	}
	return ans;
}

void solve()
{
	cin>>n>>m;
	int ans=1;
	for(int i=1;i<n;i++)
	{
		char tmp;
		cin>>tmp;
		if(tmp=='?') a[i]=1;
		else a[i]=0;
	}
	for(int i=n-1;i>1;i--)
	{
		if(a[i]) ans=(1ll*ans*(i-1))%modp;
	}
	if(a[1]) cout<<0<<'\n';
	else cout<<ans<<'\n';
	for(int i=1;i<=m;i++)
	{
		int x;
		char tmp;
		cin>>x>>tmp;
		int tans=ans;
		int looker=(tmp=='?');
		if(x!=1) 
		{
			if(looker&&!a[x]) tans=tans*(x-1)%modp;
			else if(!looker&&a[x]) tans=tans*ksm((x-1),modp-2)%modp;
		}
		a[x]=(tmp=='?');
		ans=tans;
		if(a[1]) cout<<0<<'\n';
		else cout<<tans<<'\n';
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	int T=1;
//	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}