AT_arc234_a.Reverse, Recurse

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given a permutation P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N) of (1,2,⋯ ,N)(1,2,\cdots,N). For integers L,RL,R satisfying 1≤L≤R≤N1\leq L\leq R\leq N, define the procedure f(L,R)f(L,R) as performing the following two steps in order.

  • If PL>PRP_L > P_R, reverse PL,PL+1,⋯ ,PRP_L, P_{L+1}, \cdots,P_R. That is, replace them with PR,PR−1,⋯ ,PLP_R, P_{R-1},\cdots, P_L.
  • If L<RL<R, execute f(L,R−1)f(L,R-1) and then execute f(L+1,R)f(L+1,R).

Find the number of reversals performed when f(1,N)f(1,N) is executed, modulo 998244353998244353.

给你一个 (1,2,⋯ ,N)(1,2,\cdots,N) 的排列 P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N)。对于满足 1≤L≤R≤N1\leq L\leq R\leq N 的整数 L,RL,R,定义过程 f(L,R)f(L,R) 按顺序执行以下两个步骤:

  • 若 PL>PRP_L > P_R,则将子数组 PL,PL+1,⋯ ,PRP_L, P_{L+1}, \cdots,P_R 反转。即,将其替换为 PR,PR−1,⋯ ,PLP_R, P_{R-1},\cdots, P_L。
  • 若 L<RL<R,则先执行 f(L,R−1)f(L,R-1),再执行 f(L+1,R)f(L+1,R)。

求执行 f(1,N)f(1,N) 过程中总共发生的反转次数,对 998244353998244353 取模的结果。

输入格式

The input is given from Standard Input in the following format:

NN
P1P_1 P2P_2 …\ldots PNP_N

输入从标准输入中按以下格式给出:

NN
P1P_1 P2P_2 …\ldots PNP_N

输出格式

Output the answer.

输出答案。

输入输出样例

  • 输入#1

    3
    3 1 2

    输出#1

    2
  • 输入#2

    2
    1 2

    输出#2

    0
  • 输入#3

    40
    4 23 40 37 2 35 33 5 3 16 34 13 14 15 11 10 18 7 26 1 22 21 32 25 12 39 8 19 28 20 17 24 38 31 30 29 36 9 27 6

    输出#3

    143250188

说明/提示

Sample 1 Explanation:
Initially, P=(3,1,2)P=(3,1,2). The procedures are called in the following order.

  • f(1,3)f(1,3): Since P1>P3P_1>P_3, a reversal is performed, resulting in P=(2,1,3)P=(2,1,3).
    • f(1,2)f(1,2): Since P1>P2P_1>P_2, a reversal is performed, resulting in P=(1,2,3)P=(1,2,3).
      • f(1,1)f(1,1): Since P1>P1P_1>P_1 does not hold, no reversal is performed.
      • f(2,2)f(2,2): Since P2>P2P_2>P_2 does not hold, no reversal is performed.
    • f(2,3)f(2,3): Since P2>P3P_2>P_3 does not hold, no reversal is performed.
      • f(2,2)f(2,2): Since P2>P2P_2>P_2 does not hold, no reversal is performed.
      • f(3,3)f(3,3): Since P3>P3P_3>P_3 does not hold, no reversal is performed.

A total of 22 reversals are performed, so the answer is 22.

Constraints

  • 2≤N≤3×1052 \le N \le 3 \times 10^5
  • 1≤Pi≤N1 \le P_i \le N
  • PP is a permutation of (1,2,⋯ ,N)(1,2,\cdots,N).
  • All input values are integers.

样例 1 解释:
初始时,P=(3,1,2)P=(3,1,2)。各过程按如下顺序被调用:

  • f(1,3)f(1,3):由于 P1>P3P_1>P_3,执行一次翻转,得到 P=(2,1,3)P=(2,1,3)。
    • f(1,2)f(1,2):由于 P1>P2P_1>P_2,执行一次翻转,得到 P=(1,2,3)P=(1,2,3)。
      • f(1,1)f(1,1):由于 P1>P1P_1>P_1 不成立,不执行翻转。
      • f(2,2)f(2,2):由于 P2>P2P_2>P_2 不成立,不执行翻转。
    • f(2,3)f(2,3):由于 P2>P3P_2>P_3 不成立,不执行翻转。
      • f(2,2)f(2,2):由于 P2>P2P_2>P_2 不成立,不执行翻转。
      • f(3,3)f(3,3):由于 P3>P3P_3>P_3 不成立,不执行翻转。

总共执行了 22 次翻转,因此答案为 22。

限制条件

  • 2≤N≤3×1052 \le N \le 3 \times 10^5
  • 1≤Pi≤N1 \le P_i \le N
  • PP 是 (1,2,⋯ ,N)(1,2,\cdots,N) 的一个排列。
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页