分数: 300 点
问题陈述
问题F和F2是相同的问题,但约束条件不同 M。在问题F2中, M = 5.
给你一个正整数 M。考虑以下问题。
桶给你一个正整数 N 和非负整数序列 A=(A_1,A_2,\dots,A_N) 和 B=(B_1,B_2,\dots,B_N) 长度 N。的所有元素 A 和 B 之间 0 和 M,包括在内。
有 N 桶已编号 1 to N。每个桶最多可容纳 M 升水。最初,桶 i 包含 A_i 升水。
您可以多次执行以下操作。
- 选择两个不同的桶 i 和 j。继续从桶里倒水 i 放入桶中 j 只要满足以下两个条件:
- 桶 i 仍有水剩余。
- 桶中的水量 j 小于 M 升。
您的目标是准确地 B_i 桶里的水升 i 对于所有人 i。确定目标能否实现。
给定一个非负整数矩阵 X=(X_{i,j})(0 \le i,j \le M) of (M+1) 行和 (M+1) 列。处理以下查询 Q 次。
- 给你非负整数 i,j,Y 与 0 \le i,j \le M。改变 X_{i,j} to Y。然后,获取非负整数序列 A 和 B 通过以下过程。
- 初始化非负整数序列 A 和 B 作为空序列。
- 对于 i = 0,1,\dots,M 按此顺序:
- 对于 j = 0,1,\dots,M 按此顺序:
- 这样做 X_{i,j} 次:追加 i 到年底 A 和 j 到年底 B.
- 解决 桶 对于非负整数序列 A 和 B 长度 N = \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j}.
约束
- M = 5
- 1 \le Q \le 10^6
- 0 \le X_{i,j},Y \le 10^{17}
- 0 \le i,j \le M
- \sum_{i=0}^{M} \sum_{j=0}^{M} X_{i,j} \ge 1 随时。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
M Q
X_{0,0}\ X_{0,1}\ \dots\ X_{0,M}
X_{1,0}\ X_{1,1}\ \dots\ X_{1,M}
\vdots
X_{M,0}\ X_{M,1}\ \dots\ X_{M,M}
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询均按以下格式给出:
i\ j\ Y
输出
输出 Q 行。的 i- 第行应包含 Yes 如果目标能够在 \mathrm{query}_i,和 No 否则。
示例输入 1
5 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 4 0 1 1 5 1
示例输出 1
Yes No Yes
序列 每次查询得到的 A 和 B 如下:
- 处理第一个查询时: A=(0,3,3),B=(0,1,5)
- 处理第二个查询时: A=(0,3,3,4),B=(0,1,5,0)
- 处理第三个查询时: A=(0,1,3,3,4),B=(0,5,1,5,0)
示例输入 2
5 10 61717749303507807 83849626163233111 84388501405824055 8514730661576685 8408052512772637 42085112989954358 33333333333333333 70477132070314067 43546706335438313 61370380435458585 99101823689638606 77669930608921552 33333333333333333 21459633523757247 8151410984806542 14183403125185219 68299186110683565 35549692732468863 98146856836553017 53630682913685434 12400422817799555 29967281381593348 67521547136428867 48353536740933612 97356055491517734 55777507072845580 59235925940735000 6228770338558507 41778108608223669 60544364859700647 5960356361755846 59147828067221624 65687376011190687 33333333333333333 31563848832259443 98724011871535047 2 3 1333175914347793 3 4 80371774347266293 2 1 20920094361040152 2 3 793636751630698 0 5 68209364995103050 2 0 98643963346205063 3 2 7931291059115265 0 1 79380494404548821 2 5 6440038070576840 2 3 88122600737306767
示例输出 2
No No No No No Yes No Yes No Yes