题目大意 最初有一个长度 nnn 的序列 aaa 和 qqq 个数对 (pi,vi)(p_i,v_i)(pi ,vi ) ，对于每个数对有两种方式执行操作： * 将 a1,a2,⋯ ,apia_1,a_2,\cdots,a_{p_i}a1 ,a2 ,⋯,api 替换为 viv_ivi ，次操作前提是 a1,a2,⋯ ,apia_1,a_2,\cdots,a_{p_i}a1 ,a2 ,⋯,api 都小于或等于 viv_ivi 。 * 将 api,api+1,⋯ ,ana_{p_i},a_{p_i+1},\cdots,a_{n}api ,api +1 ,⋯,an 替换为 viv_ivi ，次操作前提是 api,api+1,⋯ ,ana_{p_i},a_{p_i+1},\cdots,a_{n}api ,api +1 ,⋯,an 都小于或等于 viv_ivi 。 问有多少种不同的操作序列，如果不能全部都执行，则输出 0 。 解题思路 首先我们观察到 q≤5000q\leq 5000q≤5000 ，因此可以尝试使用 O(q2)O(q^2)O(q2) 的做法实现。 我们称第 iii 个数对操作为 iii 操作，选择第一种执行方式称为向左操作，选择第二种执行方式成为向右操作。 考虑所有两两数对 (i,j)(i,j)(i,j) 操作之间的关系，有 1≤i<j≤q1\leq i< j\leq q1≤i<j≤q ，有以下几种情况： * 当 vi≤vjv_i \leq v_jvi ≤vj 时，任意选择即可。 * 当 vi>vjv_i>v_jvi >vj 并且 pi=pjp_i=p_jpi =pj 时，此时这两个操作直接矛盾，答案为 000 。 * 当 vi>vjv_i>v_jvi >vj 并且 pi<pjp_i<p_jpi <pj 时，操作 iii 必须向左操作，操作 jjj 必须向右操作。 * 当 vi>vjv_i>v_jvi >vj 并且 pi>pjp_i>p_jpi >pj 时，操作 iii 必须向右操作，操作 jjj 必须向左操作。 对于第三、四种情况，可能会出现不同数对间接矛盾的情况，此时答案也为 000 。 我们将所有数对操作的可能情况用 −1,0,1-1,0,1−1,0,1 进行表示，其中 −1-1−1 表示向左向右都可，000 表示只能向左，111 表示只能向右。 如果所有操作之间没有矛盾，那么答案至少为 111 ，对于那些上述 −1-1−1 的操作，都有两种选择，其他都只有一种选择，不妨设 −1-1−1 的操作数为 cntcntcnt ，那么答案为 2cnt2^{cnt}2cnt 。注意取模。 参考代码