[COTS 2024] 双双决斗 Dvoboj

Luogu

IDLGP10680

Time2000ms

Memory1024MB

DifficultyP5

2024O2优化ST 表根号分治COTS（克罗地亚）

Jusuf 手里有 $N$ 张卡牌，从左到右编号为 $1$ 到 $N$。每张卡牌的力量为 $p_i$。由于 Jusuf 即将参加比赛，他想要在脑中想象战斗。有时候，他也会更改卡牌的力量值。Jusuf 总共会做 $Q$ 次操作，每个操作属于以下两种类型之一： 1. `1 i r`：Jusuf 将位于位置 $i$ 的卡牌的力量设为 $r$，即 $p_i\gets r$。 2. `2 l k`：Jusuf 在脑中想象一场战斗。这场战斗使用从第 $l,l+1,\cdots,l + 2^k − 1$ 张，共 $2^k$ 张卡牌。战斗将会进行 $k$ 轮。每轮中，Jusuf 将第 $(2i-1)$ 和第 $2i$ 张卡牌分成一组（例如第 $1$ 张和第 $2$ 张卡牌为一组）。对于每组卡牌，Jusuf 比较它们的力量。不妨设两张卡牌的力量分别为 $A$ 和 $B$，力量更大的卡牌将获胜，且获胜卡牌的力量变为 $|A − B|$，另一张卡牌被移除。特别地，如果 $A=B$，则这场战斗的结果无法确定，将会随机一张卡牌获胜，力量变为 $0$。注意到，在 $k$ 轮后，只会剩下一张卡牌，Jusuf 想要知道此时它的力量大小。由于 Jusuf 只是在脑中想象战斗，所以实际上牌的数量不会改变，$p_i$ 也不会改变。 ## Input 第一行，两个正整数 $N,Q$，含义见题面。第二行，$n$ 个整数，第 $i$ 个整数表示 $p_i$。接下来 $Q$ 行，每行 $3$ 个正整数，描述一个操作。 ## Output 对于每个操作 $2$，输出一行一个整数，表示所求的力量大小。 [samples] ## Background 译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D1T1。$\texttt{2s,1G}$。 > Two pharaonic yellow lines turned into an eye... ## Note #### 样例解释对于样例 $1$ 的第一个询问，有： $$(\bold{\textcolor{red}{4}},8,\bold{\textcolor{red}{2}},0)\to (\bold{\textcolor{red}{4}},2)\to(2)$$ 对于样例 $1$ 的第二个询问，有： $$ (\bold{\textcolor{red}{8}},2)\to(6)$$ #### 数据范围对于 $100\%$ 的数据，保证： - $2\le N\le 200\, 000$，$1\le Q\le 200\, 000$； - $0\le p_i\le 10^9$； - $1\le i\le N$，$0\le r\le 10^9$； - $1\le l\le N$，$1\le l+{2^k}-1\le N$。 | 子任务编号 | 分值 | 约束 | |:-----:|:------:|:-------:| | $1$ | $11$ | $N, Q \leq 1000$ | | $2$ | $13$ | $N=2^k$ | | $3$ | $16$ | $0\le p_i,r\le 1$ | | $4$ | $17$ | 不含修改操作 | | $5$ | $43$ | 无额外约束 |

Samples

Input #1

Output #1

2
6

Input #2

8 6
1 2 3 4 5 6 7 8
2 1 3
1 4 1
1 7 3
2 1 3
1 2 100
2 2 2

Output #2

0
3
93

Input #3

9 5
1 0 2 0 4 1 3 2 8
2 2 3
2 1 3
1 5 1
1 6 4
2 4 2

Output #3

2
1
0

API Response (JSON)

{
  "problem": {
    "name": "[COTS 2024] 双双决斗 Dvoboj",
    "description": {
      "content": "Jusuf 手里有 $N$ 张卡牌，从左到右编号为 $1$ 到 $N$。每张卡牌的力量为 $p_i$。由于 Jusuf 即将参加比赛，他想要在脑中想象战斗。有时候，他也会更改卡牌的力量值。Jusuf 总共会做 $Q$ 次操作，每个操作属于以下两种类型之一： 1. `1 i r`：Jusuf 将位于位置 $i$ 的卡牌的力量设为 $r$，即 $p_i\\gets r$。 2. `2 l k`：Ju",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10680"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Jusuf 手里有 $N$ 张卡牌，从左到右编号为 $1$ 到 $N$。每张卡牌的力量为 $p_i$。由于 Jusuf 即将参加比赛，他想要在脑中想象战斗。有时候，他也会更改卡牌的力量值。Jusuf 总共会做 $Q$ 次操作，每个操作属于以下两种类型之一：\n\n1. `1 i r`：Jusuf 将位于位置 $i$ 的卡牌的力量设为 $r$，即 $p_i\\gets r$。\n\n2. `2 l k`：Ju...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments