「OICon-02」Great Segments

Luogu

IDLGP10174

Time400ms

Memory512MB

DifficultyP5

线性数据结构O2优化树论单调栈

给定一个长度为 $n$ 的无重复元素序列 $a$。对于一个区间 $[l,r]$，我们定义它是好的，有以下条件： 1. 定义一个序列 $b=\{ a_l,\max(a_l,a_{l+1}),\max(a_l,a_{l+1},a_{l+2}),\ ...\ ,\max(a_l,a_{l+1},\ ... \ ,a_r)\}$，将该序列进行去重操作后，该序列的长度不超过 $k$ 且大于 $1$； 2. $\max(a_l,a_{l+1},\ ... \ ,a_r)=a_r$。请你解决这样一个问题：对于每一个 $i \ (1 \le i \le n)$，有多少个好的区间 $[l,r]$ 满足 $l \le i \le r$。 ## Input 第一行两个整数 $n,k$。第二行 $n$ 个整数，第 $i$ 个数表示 $a_i$。 ## Output $n$ 行，每行一个整数，第 $i$ 行的数表示序列中有多少个好的区间 $[l,r]$ 满足 $l \le i \le r$。 [samples] ## Background upd：时间限制改为 400ms [加强版题目推荐](https://www.luogu.com.cn/problem/P11291) ## Note ### 样例解释对于样例 $1$，满足条件的区间有： 1. $[1,2]$； 2. $[2,4]$； 3. $[3,4]$。故当 $i=1,2,3,4$ 时，分别有以下区间满足 $l\leq i\leq r$（根据上述的区间编号）： 1. $1$ 区间； 2. $1,2$ 区间； 3. $2,3$ 区间； 4. $2,3$ 区间。 ### 数据范围 **本题采用捆绑测试。** | $\text{Subtask}$ | 特殊性质 | $\text{Score}$ | | :----------: | :----------: | :----------: | | $1$ | $n \le 200$ | $5$ | | $2$ | $n\leq 2000$ | $10$ | | $3$ | $\{a\}$ 递增 | $10$ | | $4$ | $k\leq 5$ | $12$ | | $5$ | $k=n$ | $13$ | | $6$ | $n \le 3 \times 10^5$ | $20$ | | $7$ | 无特殊限制 | $30$ | 对于 $100\%$ 的数据：$1\leq k\leq n\leq 10^6$，$0\leq a_i\leq 10^9$。

Samples

Input #1

4 2
1 3 2 4

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「OICon-02」Great Segments",
    "description": {
      "content": "给定一个长度为 $n$ 的无重复元素序列 $a$。 对于一个区间 $[l,r]$，我们定义它是好的，有以下条件： 1. 定义一个序列 $b=\\{ a_l,\\max(a_l,a_{l+1}),\\max(a_l,a_{l+1},a_{l+2}),\\ ...\\ ,\\max(a_l,a_{l+1},\\ ... \\ ,a_r)\\}$，将该序列进行去重操作后，该序列的长度不超过 $k$ 且大于 $1$； ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 400,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10174"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个长度为 $n$ 的无重复元素序列 $a$。\n\n对于一个区间 $[l,r]$，我们定义它是好的，有以下条件：\n\n1. 定义一个序列 $b=\\{ a_l,\\max(a_l,a_{l+1}),\\max(a_l,a_{l+1},a_{l+2}),\\ ...\\ ,\\max(a_l,a_{l+1},\\ ... \\ ,a_r)\\}$，将该序列进行去重操作后，该序列的长度不超过 $k$ 且大于 $1$；\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments