BZOJ2989 数列/BZOJ4170 极光

Luogu

IDLGP10633

Time1000ms

Memory512MB

DifficultyP5

树状数组cdq 分治O2优化

给定一个长度为 $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}(x,i) \leq k$；询问不仅要考虑当前数列，还要考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的 $a_x$ 的 $\text{graze}$ 值 $\leq k$ 的对数。（某位置多次修改为同样的数值，按多次统计。） ## Input 第一行两个整数 $n,q$，表示数列长度与操作数；第二行 $n$ 个正整数，代表初始数列。第 $3\sim q+2$ 行，每行一个操作。 ## Output 对于每次询问操作，输出一个非负整数表示答案。 [samples] ## Note 对于所有数据，保证 $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$。

Samples

Input #1

3 5
2 4 3
Query 2 2
Modify 1 3
Query 2 2
Modify 1 2
Query 1 1

Output #1

2
3
3

API Response (JSON)

{
  "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}(...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments