「OICon-02」maxiMINImax

Luogu

IDLGP10173

Time2000ms

Memory512MB

DifficultyP5

线段树O2优化笛卡尔树单调栈

给出一个长度为 $n$ 的排列 $a$。定义一个子区间 $[l,r]$ 中 $a_i$ 的最小值为 $\min_{[l,r]}$，$a_i$ 的最大值为 $\max_{[l,r]}$。对于所有子区间三元组 $([l_1,r_1],[l_2,r_2],[l_3,r_3])$ 使得 $1\leq l_1\leq r_1<l_2\leq r_2<l_3\leq r_3\leq n$，求 $\max(0,\min_{[l_2,r_2]}-\max_{[l_1,r_1]})\times\max(0,\min_{[l_2,r_2]}-\max_{[l_3,r_3]})$ 之和，对 $9712176$ 取模。 ## Input 第一行，一个正整数 $n$，表示排列的长度。第二行，$n$ 个正整数 $a$，表示给出的排列 $a$。 ## Output 一行，一个正整数，表示 $\max(0,\min_{[l_2,r_2]}-\max_{[l_1,r_1]})\times\max(0,\min_{[l_2,r_2]}-\max_{[l_3,r_3]})$ 之和，对 $9712176$ 取模。 [samples] ## Note ### 样例解释对于样例 $1$： * $([l_1,r_1],[l_2,r_2],[l_3,r_3])=([1,1],[2,2],[3,3])$：$\max(0,\min_{[l_2,r_2]}-\max_{[l_1,r_1]})\times\max(0,\min_{[l_2,r_2]}-\max_{[l_3,r_3]})=0$； * $([l_1,r_1],[l_2,r_2],[l_3,r_3])=([1,1],[2,2],[3,4])$：$\max(0,\min_{[l_2,r_2]}-\max_{[l_1,r_1]})\times\max(0,\min_{[l_2,r_2]}-\max_{[l_3,r_3]})=0$； * $([l_1,r_1],[l_2,r_2],[l_3,r_3])=([1,1],[2,2],[4,4])$：$\max(0,\min_{[l_2,r_2]}-\max_{[l_1,r_1]})\times\max(0,\min_{[l_2,r_2]}-\max_{[l_3,r_3]})=2$； * $([l_1,r_1],[l_2,r_2],[l_3,r_3])=([1,1],[2,3],[4,4])$：$\max(0,\min_{[l_2,r_2]}-\max_{[l_1,r_1]})\times\max(0,\min_{[l_2,r_2]}-\max_{[l_3,r_3]})=2$； * $([l_1,r_1],[l_2,r_2],[l_3,r_3])=([1,1],[3,3],[4,4])$：$\max(0,\min_{[l_2,r_2]}-\max_{[l_1,r_1]})\times\max(0,\min_{[l_2,r_2]}-\max_{[l_3,r_3]})=6$； * $([l_1,r_1],[l_2,r_2],[l_3,r_3])=([1,2],[3,3],[4,4])$：$\max(0,\min_{[l_2,r_2]}-\max_{[l_1,r_1]})\times\max(0,\min_{[l_2,r_2]}-\max_{[l_3,r_3]})=2$； * $([l_1,r_1],[l_2,r_2],[l_3,r_3])=([2,2],[3,3],[4,4])$：$\max(0,\min_{[l_2,r_2]}-\max_{[l_1,r_1]})\times\max(0,\min_{[l_2,r_2]}-\max_{[l_3,r_3]})=2$。所有 $([l_1,r_1],[l_2,r_2],[l_3,r_3])$ 的 $\max(0,\min_{[l_2,r_2]}-\max_{[l_1,r_1]})\times\max(0,\min_{[l_2,r_2]}-\max_{[l_3,r_3]})$ 总和为 $0+0+2+2+6+2+2=14$。 ### 数据范围 **本题采用捆绑测试。** | $\text{Subtask}$ | 特殊性质 | $\text{Score}$ | |:--:|:--:|:--:| | $1$ | $n\leq60$ | $5$ | | $2$ | $n\leq100$ | $9$ | | $3$ | $n\leq200$ | $9$ | | $4$ | $n\leq500$ | $9$ | | $5$ | $n\leq2000$ | $19$ | | $6$ | $n\leq6000$ | $11$ | | $7$ | $n\leq10^5$ | $19$ | | $8$ | 无特殊限制 | $19$ | 对于 $100\%$ 的数据：$1\leq n\leq10^6$，$1\leq a_i\leq n$，保证 $a$ 为 $\{1,2,\dots,n\}$ 的一个排列。

Samples

Input #1

4
1 3 4 2

Output #1

Input #2

10
1 3 6 2 7 9 4 10 8 5

Output #2

API Response (JSON)

{
  "problem": {
    "name": "「OICon-02」maxiMINImax",
    "description": {
      "content": "给出一个长度为 $n$ 的排列 $a$。定义一个子区间 $[l,r]$ 中 $a_i$ 的最小值为 $\\min_{[l,r]}$，$a_i$ 的最大值为 $\\max_{[l,r]}$。对于所有子区间三元组 $([l_1,r_1],[l_2,r_2],[l_3,r_3])$ 使得 $1\\leq l_1\\leq r_1<l_2\\leq r_2<l_3\\leq r_3\\leq n$，求 $\\max(0,",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10173"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给出一个长度为 $n$ 的排列 $a$。定义一个子区间 $[l,r]$ 中 $a_i$ 的最小值为 $\\min_{[l,r]}$，$a_i$ 的最大值为 $\\max_{[l,r]}$。对于所有子区间三元组 $([l_1,r_1],[l_2,r_2],[l_3,r_3])$ 使得 $1\\leq l_1\\leq r_1<l_2\\leq r_2<l_3\\leq r_3\\leq n$，求 $\\max(0,...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments