{"problem":{"name":"BZOJ2989 数列/BZOJ4170 极光","description":{"content":"给定一个长度为 $n$ 的正整数数列 $a_i$，两个位置的 $\\text{graze}$ 值为两者位置差与数值差的和：$\\text{graze}(x,y)=|x-y|+|a_x-a_y|$。 你必须支持两种操作（$k$ 都是正整数）： - `Modify x k`，表示将第 $x$ 个数的值修改为 $k$； - `Query x k`，表示询问有几个 $i$ 满足 $\\text{graze}(","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10633"},"statements":[{"statement_type":"Markdown","content":"给定一个长度为 $n$ 的正整数数列 $a_i$，两个位置的 $\\text{graze}$ 值为两者位置差与数值差的和：$\\text{graze}(x,y)=|x-y|+|a_x-a_y|$。\n\n你必须支持两种操作（$k$ 都是正整数）：\n- `Modify x k`，表示将第 $x$ 个数的值修改为 $k$；\n- `Query x k`，表示询问有几个 $i$ 满足 $\\text{graze}(x,i) \\leq k$；\n\n询问不仅要考虑当前数列，还要考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的 $a_x$ 的 $\\text{graze}$ 值 $\\leq k$ 的对数。（某位置多次修改为同样的数值，按多次统计。）\n\n## Input\n\n第一行两个整数 $n,q$，表示数列长度与操作数；\n\n第二行 $n$ 个正整数，代表初始数列。\n\n第 $3\\sim q+2$ 行，每行一个操作。\n\n## Output\n\n对于每次询问操作，输出一个非负整数表示答案。\n\n[samples]\n\n## Note\n\n对于所有数据，保证 $1\\leq n\\leq 6\\times 10^4$，$1\\leq$ 修改操作数 $\\leq 5\\times 10^4$，$1\\leq$ 询问次数 $\\leq 6\\times 10^4$，$1\\leq a_i$ 的所有历史版本的最大值 $\\leq 10^5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10633","tags":["树状数组","cdq 分治","O2优化"],"sample_group":[["3 5\n2 4 3\nQuery 2 2\nModify 1 3\nQuery 2 2\nModify 1 2\nQuery 1 1","2\n3\n3"]],"created_at":"2026-03-03 11:09:25"}}