官方题解

题目大意

最初有一个长度 $n$ 的序列 $a$ 和 $q$ 个数对 $(p_i,v_i)$ ，对于每个数对有两种方式执行操作：

• 将 $a_1,a_2,\cdots,a_{p_i}$ 替换为 $v_i$ ，次操作前提是 $a_1,a_2,\cdots,a_{p_i}$ 都小于或等于 $v_i$ 。
• 将 $a_{p_i},a_{p_i+1},\cdots,a_{n}$ 替换为 $v_i$ ，次操作前提是 $a_{p_i},a_{p_i+1},\cdots,a_{n}$ 都小于或等于 $v_i$ 。

问有多少种不同的操作序列，如果不能全部都执行，则输出 0 。

解题思路

首先我们观察到 $q\leq 5000$ ，因此可以尝试使用 $O(q^2)$ 的做法实现。

我们称第 $i$ 个数对操作为 $i$ 操作，选择第一种执行方式称为向左操作，选择第二种执行方式成为向右操作。

考虑所有两两数对 $(i,j)$ 操作之间的关系，有 $1\leq i< j\leq q$ ，有以下几种情况：

• 当 $v_i \leq v_j$ 时，任意选择即可。
• 当 $v_i>v_j$ 并且 $p_i=p_j$ 时，此时这两个操作直接矛盾，答案为 $0$ 。
• 当 $v_i>v_j$ 并且 $p_i<p_j$ 时，操作 $i$ 必须向左操作，操作 $j$ 必须向右操作。
• 当 $v_i>v_j$ 并且 $p_i>p_j$ 时，操作 $i$ 必须向右操作，操作 $j$ 必须向左操作。

对于第三、四种情况，可能会出现不同数对间接矛盾的情况，此时答案也为 $0$ 。

我们将所有数对操作的可能情况用 $-1,0,1$ 进行表示，其中 $-1$ 表示向左向右都可，$0$ 表示只能向左，$1$ 表示只能向右。

如果所有操作之间没有矛盾，那么答案至少为 $1$ ，对于那些上述 $-1$ 的操作，都有两种选择，其他都只有一种选择，不妨设 $-1$ 的操作数为 $cnt$ ，那么答案为 $2^{cnt}$ 。注意取模。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
const int mod = 998244353;

// dir[i]: 标记第 i 个位置是的方向。
// -1 -- 两个方向都可; 0 -- 向左; 1 -- 向右
int dir[N];

void work(int pos,int x){
    if(dir[pos]==-1) dir[pos]=x;
    if(dir[pos]!=x){
        cout<<0<<endl;
        exit(0);
    }
}

int main(){
    int n,q;cin>>n>>q;
    vector<int>p(q+1),v(q+1);
    for(int i=1;i<=q;i++){
        cin>>p[i]>>v[i];
        dir[i]=-1;
    }

    for(int i=1;i<=q;i++){
        for(int j=i+1;j<=q;j++){
            // 1. v[i]<=v[j]: i,j 两个位置都可做两种操作
            if(v[i]<=v[j]) continue;
            // 2. v[i]>v[j] and p[i]=p[j]: 矛盾, 输出0
            if(p[i]==p[j]){
                cout<<0<<endl;
                return 0;
            }
            // 3. v[i]>v[j] and p[i]>p[j]: i 向右, j 向左 唯一确定
            if(p[i]>p[j]){
                work(i,1);
                work(j,0);
            }
            // 4. v[i]>v[j] and p[i]<p[j]: i 向左, j 向右 唯一确定
            else{
                work(i,0);
                work(j,1);
            }
        }
    }

    int res=1;
    for(int i=1;i<=q;i++){
        if(dir[i]==-1) res=res*2%mod;
    }
    cout<<res<<endl;
    
    return 0;
}