{"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$；\n2. $\\max(a_l,a_{l+1},\\ ... \\ ,a_r)=a_r$。\n\n请你解决这样一个问题：对于每一个 $i \\ (1 \\le i \\le n)$，有多少个好的区间 $[l,r]$ 满足 $l \\le i \\le r$。\n\n## Input\n\n第一行两个整数 $n,k$。\n\n第二行 $n$ 个整数，第 $i$ 个数表示 $a_i$。\n\n## Output\n\n$n$ 行，每行一个整数，第 $i$ 行的数表示序列中有多少个好的区间 $[l,r]$ 满足 $l \\le i \\le r$。\n\n[samples]\n\n## Background\n\nupd：时间限制改为 400ms\n\n[加强版题目推荐](https://www.luogu.com.cn/problem/P11291)\n\n## Note\n\n### 样例解释\n\n对于样例 $1$，满足条件的区间有：\n\n1. $[1,2]$；\n2. $[2,4]$；\n3. $[3,4]$。\n\n故当 $i=1,2,3,4$ 时，分别有以下区间满足 $l\\leq i\\leq r$（根据上述的区间编号）：\n\n1. $1$ 区间；\n2. $1,2$ 区间；\n3. $2,3$ 区间；\n4. $2,3$ 区间。\n\n### 数据范围\n\n**本题采用捆绑测试。**\n\n| $\\text{Subtask}$ | 特殊性质 | $\\text{Score}$ |\n| :----------: | :----------: | :----------: |\n| $1$ | $n \\le 200$ | $5$ |\n| $2$ | $n\\leq 2000$ | $10$ | \n| $3$ | $\\{a\\}$ 递增 | $10$ |\n| $4$ | $k\\leq 5$ | $12$ |\n| $5$ | $k=n$ | $13$ |\n| $6$ | $n \\le 3 \\times 10^5$ | $20$ |\n| $7$ | 无特殊限制 | $30$ |\n\n对于 $100\\%$ 的数据：$1\\leq k\\leq n\\leq 10^6$，$0\\leq a_i\\leq 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10174","tags":["线性数据结构","O2优化","树论","单调栈"],"sample_group":[["4 2\n1 3 2 4","1\n2\n2\n2"]],"created_at":"2026-03-03 11:09:25"}}