{"problem":{"name":"[COCI 2023/2024 #2] Zatopljenje","description":{"content":"Mr. Malnar 有一张地形图，上面画着一个区域内每个位置的海拔高度。具体的，有 $n$ 个位置排成一排，第 $i$ 个位置高出海平面 $h_i$ 米。 海平面可能会上升。给定 $q$ 次询问，对于第 $i$ 次询问你需回答：如果海平面高度上升 $x_i$ 米，那么 $[l_i,r_i]$ 区间中会形成多少个岛？一个岛的定义为一个极长的，每个位置的高度都大于 $x_i$ 的段。 ![](h","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9912"},"statements":[{"statement_type":"Markdown","content":"Mr. Malnar 有一张地形图，上面画着一个区域内每个位置的海拔高度。具体的，有 $n$ 个位置排成一排，第 $i$ 个位置高出海平面 $h_i$ 米。\n\n海平面可能会上升。给定 $q$ 次询问，对于第 $i$ 次询问你需回答：如果海平面高度上升 $x_i$ 米，那么 $[l_i,r_i]$ 区间中会形成多少个岛？一个岛的定义为一个极长的，每个位置的高度都大于 $x_i$ 的段。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/mffg52xn.png)\n\n上图分别表示了样例 1 的第一组询问以及样例 2 的第二组询问。左图 $[2,5]$ 区间中有 $[2,2],[4,5]$ 两个岛，而右图中有 $[1,1],[4,4],[8,8],[10,10]$ 四个岛。\n\n## Input\n\n第一行两个整数 $n,q$。\n\n第二行 $n$ 个整数 $h_{1\\sim n}$ 表示每个位置的初始海拔。\n\n接下来 $q$ 行每行 $3$ 个整数 $l_i,r_i,x_i$ 表示一次询问。\n\n## Output\n\n输出 $q$ 行，第 $i$ 行一个整数表示第 $i$ 次询问的答案。\n\n[samples]\n\n## Note\n\n### 数据范围\n|$\\text{Subtask}$|分值|特殊性质|\n|:-:|:-:|:-:|\n|$1$|$10$|$n,q\\le 2000$|\n|$2$|$20$|$l_i=1,r_i=n$|\n|$3$|$20$|存在 $p\\in [1,n]$ 满足 $h_1\\ge h_2\\ge \\cdots \\ge h_p\\le h_{p+1}\\le \\cdots \\le h_n$|\n|$4$|$60$|无|\n\n对于所有数据，$1\\le n,q\\le 2\\times 10^5$，$0\\le h_i,x_i\\le 10^9$，$1\\le l_i\\le r_i\\le n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9912","tags":["线段树","2023","O2优化","分块","COCI（克罗地亚）","离线处理"],"sample_group":[["6 3\n2 4 2 3 4 1\n2 5 2\n3 5 3\n3 4 4","2\n1\n0"],["10 3\n5 0 3 4 2 0 1 6 3 5\n3 9 1\n1 10 3\n1 10 2","2\n4\n3"]],"created_at":"2026-03-03 11:09:25"}}