{"problem":{"name":"[DTCPC 2024] mex,min,max","description":{"content":"给定序列 $\\{a_n\\}$ 和 $k$，求有多少子区间 $[l,r]$ 满足 $\\operatorname{mex}\\{a_l,a_{l+1},\\dots,a_{r-1},a_r\\}+\\min\\{a_l,a_{l+1},\\dots,a_{r-1},a_r\\}+k\\geq \\max\\{a_l,a_{l+1},\\dots,a_{r-1},a_r\\}$。 $\\operatorname{mex}$ 定","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10169"},"statements":[{"statement_type":"Markdown","content":"给定序列 $\\{a_n\\}$ 和 $k$，求有多少子区间 $[l,r]$ 满足 $\\operatorname{mex}\\{a_l,a_{l+1},\\dots,a_{r-1},a_r\\}+\\min\\{a_l,a_{l+1},\\dots,a_{r-1},a_r\\}+k\\geq \\max\\{a_l,a_{l+1},\\dots,a_{r-1},a_r\\}$。\n\n$\\operatorname{mex}$ 定义为集合内没有出现过的最小的**非负整数**。\n\n## Input\n\n第一行两个整数 $n,k$（$1\\leq n\\leq 5\\times 10^5,0\\leq k\\leq n$）。\n\n第二行 $n$ 个非负整数，第 $i$ 个表示 $a_i$（$0\\leq a_i\\leq n$）。\n\n## Output\n\n一行一个数，表示满足条件的子区间个数。\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10169","tags":["线段树","2024","颜色段均摊（珂朵莉树 ODT）","洛谷月赛","单调栈"],"sample_group":[["3 0\n1 0 2","5"]],"created_at":"2026-03-03 11:09:25"}}