今天学习一道CF 2100+ 分的题目

原题链接： D. Monocarp and the Set

  题目的大概意思是：你有 1-n 这 n 个数字，每次从中选择一个数字加入一个原本是空的集合。除了第一次插入，如果加入的数字比当前集合内的最大值还要大，那么输出一个 '>' ；如果加入的数字比当前集合内的最小值还要小，那么输出一个 '<' ;不是上述两种情况，则输出一个 '?' 。插入所有数字之后，你会得到一个长度为 n-1 的字符串 s 。

  现在给你 n, m 个query（每个query会替换 s 中的一个字符）, 初始字符串 s 。求每次query后，有多少种插入的方式，能使最后得到输出是字符串 s 。

输入范围

2≤n≤3∗1052 \le n \le 3*10^{5}, 1≤m≤3∗1051 \le m \le 3*10^{5}

解题思路

  这道题其实入手挺难想的，正序思考这个题目会有很多的问题。

  因为集合最后的状态是确定的，即1-n都在集合中，所以这道题用逆序的思维去考虑会简单很多。

  之前也有类似的题目，这种插入和删除的题目都可以尝试逆向思考。

  逆序遍历字符串s，每个 '>' 和 '<' 都只能去掉集合中最大的数字和最小的数字，因此对答案都无影响，遍历到 '?' 时会从集合中间去掉一个数字，因此有 i-1 中选法，i 是当前位置的下标，从0开始，下同。

  在每一个query更新答案时，如果是 '>'or'<' -> '?'，那么答案应该乘以 i-1 ；如果是 '?' -> '>'or'<'，那么答案应该除以 i-1 。这里的 i 是修改的位置的下标。

  特殊情况，如果 s[0] 是 '?' ,这种情况可能得插入方式是0种，因为插入第2个数字时集合中只有一个元素，因此插入元素必须比该元素大或小，因此不可能是 '?' 。

  用到的两个小知识点：

  1. 取余之后应用除法需要用到 费马小定理
  2. 快速幂乘，详见代码中的 mypow 函数
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
#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;

ll mypow(ll a, ll b, ll mod){
    if(b == 0)
        return 1;
    if(b % 2 == 1){
        return (a * mypow((a*a)% mod, b/2, mod)) % mod;
    }
    return mypow((a*a) % mod, b/2, mod);
}

void solve(){
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    int mod = 998244353;
    ll ans = 1;
    for(int i=1;i<n-1;i++){
        if(s[i] == '?'){
            ans = (ans * i) % mod;
        }
    }
    if(s[0] == '?')
        cout << 0 << endl;
    else
        cout << ans << endl;
    while(m--){
        int i;
        char c;
        cin >> i >> c;
        if(i > 1) {
            if(s[i-1] == '?' && (c == '>' || c == '<')){
                ans = (ans * mypow(i-1, mod-2, mod)) % mod;
            }
            else if(c == '?' && (s[i-1] == '>' || s[i-1] == '<')){
                ans = (ans * (i-1)) % mod;
            }
        }
        s[i-1] = c;
        if(s[0] == '?')
            cout << 0 << endl;
        else
            cout << ans << endl;
    }
}

int main() {
    int fast_io = []() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        return 0;
    }();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}