[LMXOI Round 2] Disaster

Luogu

IDLGP10807

Time1000ms

Memory512MB

DifficultyP3

动态规划 DPO2优化

给定 $n$ 个点，每个点给出了一组限制 $l_i,r_i(0 \le l_i < i < r_i \le n+1)$，定义一个划分是好的当且仅当对于每个点 $i$，$l_i,r_i$ 在划分后均不与 $i$ 在同一区间内，求好的划分的个数，答案对 $998244353$ 取模。补充：在本题中，一组划分表示将 $n$ 个点分为若干个区间，使得每个点恰好在一个区间内，$l_i=0$ 和 $r_i=n+1$ 可以视为无限制。 ## Input 第一行一个整数 $n$ 表示点的个数。接下来 $n$ 行，第 $i$ 行两个整数 $l_i,r_i$。 ## Output 第一行一个整数，表示答案对 $998244353$ 取模后的值。 [samples] ## Background LMX 和 HQZ 在一起研究点的划分。 ## Note **样例解释 #1** 样例的 $8$ 种合法划分区间分别是： $[1,2],[3,5]$ $[1,1],[2,2],[3,5]$ $[1,2],[3,3],[4,5]$ $[1,1],[2,2],[3,3],[4,5]$ $[1,2],[3,4],[5,5]$ $[1,1],[2,2],[3,4],[5,5]$ $[1,2],[3,3],[4,4],[5,5]$ $[1,1],[2,2],[3,3],[4,4],[5,5]$ 对于所有数据，$1 \le n\le 2 \times 10^6$，$0 \le l_i < i < r_i \le n+1$。 | 子任务编号 | $n$ | 特殊性质 | 分值 | | :--------: | :----------------: | :------------: | :--: | | Subtask #1 | $\le 20$ | 无 | $5$ | | Subtask #2 | $\le 500$ | 无 | $10$ | | Subtask #3 | $\le 5000$ | 无 | $20$ | | Subtask #4 | $\le 5 \times 10^5$ | $l_i=0$ | $10$ | | Subtask #5 | $\le 5 \times 10^5$ |无 | $25$ | | Subtask #6 | $\le 2 \times 10^6$ |无 | $30$ |

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[LMXOI Round 2] Disaster",
    "description": {
      "content": "给定 $n$ 个点，每个点给出了一组限制 $l_i,r_i(0 \\le l_i < i < r_i \\le n+1)$，定义一个划分是好的当且仅当对于每个点 $i$，$l_i,r_i$ 在划分后均不与 $i$ 在同一区间内，求好的划分的个数，答案对 $998244353$ 取模。 补充：在本题中，一组划分表示将 $n$ 个点分为若干个区间，使得每个点恰好在一个区间内，$l_i=0$ 和 $r_i",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10807"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $n$ 个点，每个点给出了一组限制 $l_i,r_i(0 \\le l_i < i < r_i \\le n+1)$，定义一个划分是好的当且仅当对于每个点 $i$，$l_i,r_i$ 在划分后均不与 $i$ 在同一区间内，求好的划分的个数，答案对 $998244353$ 取模。\n\n补充：在本题中，一组划分表示将 $n$ 个点分为若干个区间，使得每个点恰好在一个区间内，$l_i=0$ 和 $r_i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments