[ROI 2018] Decryption

Luogu
IDLGP9290
Time1000ms
Memory512MB
DifficultyP4
动态规划 DP2018线段树分治单调栈ROI(俄罗斯)
研究表明,汉字的顺序并不一定能影响阅读。科学家们对数列进行了类似的研究。 给一个正整数数列,若数列首项为数列中所有数的最小值,末项为数列中的最大值,则我们称这是个正确的数列。例如,序列 $[1, 3, 2, 4]$ 和 $[1, 2, 1, 2]$ 是正确的,但序列 $[1, 3, 2]$ 不是。 给出长度为 $n$ 的序列 $[a_1, a_2, \ldots, a_n]$。对于该序列的某个片段 $[a_l, a_{l+1}, \ldots, a_r]$, 若该片段的首项为该片段中的最小值,末项为该片段中的最大值,则我们称这是个正确的片段。 对于给定的序列,请求出该序列至少需要被分成多少段,才能使得每个片段均为正确的片段。序列 $[2, 3, 1, 1, 5, 1]$ 可以分为三个正确的段:$[2, 3]$ 和 $[1, 1, 5]$ 和 $[1]$。 需要编写一个程序,该程序按给定的顺序确定可以划分的最小正确段数。 ## Input 第一行一个整数 $n$。 接下来一行 $n$ 个数,分别为 $a_1,a_2,\ldots,a_n$。 ## Output 输出可以划分的最小正确段数。 [samples] ## Background 译自 [ROI 2018 Day2](https://neerc.ifmo.ru/school/archive/2017-2018.html) T1. [Расшифровка](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf) ([Decryption](https://codeforces.com/gym/102154/problem/B))。 ## Note - 子任务 1(30 分),$1 \leq n \leq 500$。 - 子任务 2(30 分),$1 \leq n \leq 5000$。 - 子任务 3(40 分),$1 \leq n \leq3 \times 10^5$。 对于所有数据,$1 \leq n \leq3 \times 10^5$,$1\leq a_i \leq 10^9$。
Samples
Input #1
5
5 4 3 2 1
Output #1
5
Input #2
4
1 3 2 4
Output #2
1
Input #3
6
2 3 1 1 5 1
Output #3
3
API Response (JSON)
{
  "problem": {
    "name": "[ROI 2018]  Decryption",
    "description": {
      "content": "研究表明,汉字的顺序并不一定能影响阅读。科学家们对数列进行了类似的研究。 给一个正整数数列,若数列首项为数列中所有数的最小值,末项为数列中的最大值,则我们称这是个正确的数列。例如,序列 $[1, 3, 2, 4]$ 和 $[1, 2, 1, 2]$ 是正确的,但序列  $[1, 3, 2]$ 不是。 给出长度为 $n$ 的序列 $[a_1, a_2, \\ldots, a_n]$。对于该序列的某",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9290"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "研究表明,汉字的顺序并不一定能影响阅读。科学家们对数列进行了类似的研究。\n\n给一个正整数数列,若数列首项为数列中所有数的最小值,末项为数列中的最大值,则我们称这是个正确的数列。例如,序列 $[1, 3, 2, 4]$ 和 $[1, 2, 1, 2]$ 是正确的,但序列 \n$[1, 3, 2]$ 不是。\n\n给出长度为 $n$ 的序列 $[a_1, a_2, \\ldots, a_n]$。对于该序列的某...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments