#P6899. 修电脑

    ID: 6730 传统题 10000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600差分约束线段树分治最短路栈队列模拟

修电脑

时间限制 10 秒,内存限制 512 MB。

题目背景

是谁惊艳了时光,然后埋没了年华。

题目描述

布莱克在 WC 考场上愉快的写代码的时候,脚一抖踢掉了电源线,于是他杯具了。

布莱克冷静的举手示意,结果被告知修电脑的人咕咕咕了,给他延长了十五分钟让他自行解决。

于是布莱克开始了操作,结果发现他的电脑电路好像非同一般。

一个完整的电路由 nn 行 mm 列的电路元件组成,可以用 (i,j)(i,j) 代表第 ii 行第 jj 列的元件。每个元件都需要被赋予一定量的电流 ei,je_{i,j} 才能够正常工作(当然电流不能是负的,否则这个元件就会 RERE 了)。

这么奇怪的电路,当然不可能这么简单就开始运作了。每一对横向相邻的元件在运作时的联系是非常紧密的,因此它们的电流之和不能过低或过高。为了保证这一点,电路中每一对横向相邻的元件之间连有一个接收器,连接 (i,j)(i,j) 和 (i,j+1)(i,j+1) 的接收器有两个属性 lowi,jlow_{i,j} 和 highi,jhigh_{i,j},代表它所连接的两个元件电流之和不得低于 lowi,jlow_{i,j} 且不得高于 highi,jhigh_{i,j},当不满足要求时接收器会自动将整个电路断电。

除此之外,每对纵向相邻的元件在运作时会有频繁的信息传输,因此理所当然的,两个元件的电流之差不能够太大,否则信息传输的代价会过于昂贵。所以电路中还在每一对纵向相邻的元件之间连接了一个限制器,连接 (i,j)(i,j) 和 (i+1,j)(i+1,j) 的限制器有一个属性 limi,jlim_{i,j},表示它所连接的两个元件电流之差的绝对值不得超过这个值,否则限制器也会将整个电路断电。

布莱克当然不希望他的电路会因为这些奇怪的原因无法运作,因此他想找出一种能够使电路运行起来的配置方案。然而他在研究的过程中发现接收器和限制器的参数有时会发生变化,为了维持电脑的工作,他决定将初始状态和每一次变化后的状态的配置方案求出,以拯救他的 WC。

输入格式

从 circuit.in 中读入数据。

输入有多组数据,第一行为一个整数 TT,表示数据组数。对于每组数据:

第一行两个整数 n,mn,m,代表这是一个 nn 行 mm 列的电路。

接下来 nn 行,每行 m−1m-1 个数,第 ii 行第 jj 列表示 lowi,jlow_{i,j}。

接下来 nn 行,每行 m−1m-1 个数,第 ii 行第 jj 列表示 highi,jhigh_{i,j}。

接下来 n−1n-1 行,每行 mm 个数,第 ii 行第 jj 列表示 limi,jlim_{i,j}。

接下来一行一个整数 qq,代表变化次数。

接下来 qq 行,每行四个整数 opt,i,j,xopt,i,j,x:

  • 如果 opt=1opt=1,代表 lowi,jlow_{i,j} 变为 xx。
  • 如果 opt=2opt=2,代表 highi,jhigh_{i,j} 变为 xx。
  • 如果 opt=3opt=3,代表 limi,jlim_{i,j} 变为 xx。

原赛使用随题发放的生成器 dmk,以不同的随机种子生成测试数据。

输出格式

输出数据到 circuit.out 中。

本题使用特殊评测。

约定初始状态为时刻 00,第 ii 次变化之后的状态为时刻 ii。

对于每组数据:

第一行一个整数 kk,代表没有合法配置方案的时刻数目。

接下来一行 kk 个严格递增的数,代表所有无解的时刻。如果 k=0k=0,则这一行为空。

接下来共 nmnm 行,其中第 (i−1)m+j(i-1)m+j 行描述元件 (i,j)(i,j)。对于每一行:

第一个整数为 cc,接下来是 cc 对整数 tell,xellt_ell,x_ell。每一对表示在时刻 tellt_ell,元件 (i,j)(i,j) 的电流设置为 xellx_ell。

你需要保证你的所有输出都在 3232 位带符号整数类型范围内。如果某个时刻是无解的,那么所有元件的答案无论为何值都是合法的。

样例

1
2 2
5
3
7
15
2 2
2
1 1 1 7
1 2 1 12
1
2
2 0 3 1 4
2 0 2 1 3
2 0 1 1 2
2 0 4 1 1

样例解释

输出样例给的时刻 00 的答案为:

[3214]\begin{bmatrix} 3 & 2 \\ 1 & 4 \end{bmatrix}

输出样例给的时刻 11 的答案为:

[4321]\begin{bmatrix} 4 & 3 \\ 2 & 1 \end{bmatrix}

时刻 22 要求第二行两元件的电流和至少为 1212。第一行的电流和至多为 77,两列各自的上下电流差至多为 22,所以第二行电流和至多为 7+2+2=117+2+2=11,无解。

数据规模与约定

数据编号 n,mn,m 其他约定 dmkdmk 编号
1−31-3 ≤3\le 3 s1s1 11
4−54-5 / 22
6−76-7 ≤50\le 50 s1s1 33
8−108-10 / 44
11−1311-13 / s1,s2s1,s2 55
14−1514-15 s1s1 66
16−2016-20 / 77

s1s1:q=0q=0。

s2s2:保证存在一种解使所有元件的答案 ≤1\le 1。

对于所有数据,T≤5T\le 5,2≤n,m≤1002\le n,m\le 100,0≤q≤100000\le q\le 10000,1≤opt≤31\le opt\le 3,0≤lowi,j,highi,j,limi,j,x≤200000\le low_{i,j},high_{i,j},lim_{i,j},x\le 20000。

原 PDF 题面