饼干交换大会¶

参考时间限制：0.5 秒（参考环境：评测环境与性能；仅供预估）
实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
内存限制：1024 MB

背景故事¶

茶会上的每位来宾都带了饼干，也报了自己最多能吃多少块。主持人宣布：“既然叫交换大会，就别坐下来把自己带的那盒吃完。”

于是，每块饼干只能从主人手中直接交给另一位来宾，不能转手，更不能绕一圈回到自己嘴里。来宾们不时修改携带数量和食量，主持人还会选一段相邻座位，估算这几个人内部最多能分掉多少块饼干。

这些都是纸上排练。每次估算结束，饼干一块也不会少。

(本故事由GPT-6 Astra重写)

形式化问题描述¶

有 \(n\) 个参与者，依次编号为 \(1\) 至 \(n\) . 参与者 \(i\) 的接收上限为 \(d_i\)（Demand），提供上限为 \(s_i\)（Supply），单位均为物品个数。物品只能从提供者直接交给接收者，且二者必须不同。两项上限都可以不全部使用。

按顺序处理 \(m\) 次操作，每次属于以下三类之一：

1 x d ：令 \(d_x=d\) .
2 x s ：令 \(s_x=s\) .
3 l r ：只允许编号在 \([l,r]\) 内的参与者互相提供物品，求最大交付总量。

形式化地，对当前询问的每对不同参与者 \(i,j\) ，选择非负整数 \(f_{ij}\) 表示从 \(i\) 交付给 \(j\) 的物品数。要求每个提供者满足 \(\sum_{j\ne i}f_{ij}\le s_i\) ，每个接收者满足 \(\sum_{i\ne j}f_{ij}\le d_j\) ，并最大化 \(\sum_{i\ne j}f_{ij}\) . 这里所有下标及求和均限定在 \([l,r]\) 内。

同一参与者可以同时提供和接收，两个不同参与者也可以互相提供。询问不消耗任何数量；只有前两类操作会修改状态。

输入格式¶

第一行两个整数 \(n,m\) .

第二行 \(2n\) 个整数 \(d_1,s_1,d_2,s_2,\ldots,d_n,s_n\) .

接下来 \(m\) 行，每行三个整数，表示一条操作。

输出格式¶

对每个第三类操作输出一行一个整数。若没有第三类操作，则不输出任何内容。

样例 1¶

输入¶

3 5
1 1 2 2 2 3
3 1 3
3 1 2
1 1 2
3 1 3
3 1 2

输出¶

解释¶

第一次询问可以交付 \(5\) 块饼干：参与者 \(1\) 向 \(2\) 交付一块，参与者 \(2\) 向 \(3\) 交付两块，参与者 \(3\) 分别向 \(1\) 和 \(2\) 各交付一块。

修改后，参与者 \(1\) 的接收上限变成 \(2\) ，两个范围的最大交付量分别增为 \(6\) 和 \(3\) .

样例 2¶

输入¶

2 4
100 100 1 1
3 1 2
3 1 1
1 2 100
3 1 2

输出¶

2
0
101

解释¶

第一次询问只有两人，双方各向对方交付一块饼干，总量为 \(2\) . 单人范围不能向自己交付，答案为 \(0\) .

修改后，参与者 \(1\) 可以向 \(2\) 交付 \(100\) 块，参与者 \(2\) 仍可以向 \(1\) 交付一块，因此最后一次询问的答案为 \(101\) .

数据范围与保证¶

\(1\le n,m\le300\,000\) .
\(0\le d_i,s_i,d,s\le1\,000\,000\,000\) ，均为整数。
修改操作满足 \(1\le x\le n\) .
询问满足 \(1\le l\le r\le n\) .

数据分组¶

分值比例	额外条件
10%	\(n,m\le10\) ，所有数量不超过 \(50\)
10%	\(n,m\le100\)
20%	\(n,m\le300\)
20%	\(n,m\le3\,000\)
20%	\(n,m\le50\,000\)
20%	无额外条件