TB5X - Problem

这是一道交互题。

二维平面上初始有 $n$ 个点 $(i,p_i)$，每个点有权值 $d_i$，$0\le i < n$；

共 $m$ 次操作，操作编号为 $0$ 到 $m-1$，按编号升序执行；

编号为 $w$ 的操作给出 $x_1,x_2,y_1,y_2$，满足 $0 < x1 < x2 < n$，$0 < y1 < y2 < n$。

一个点 $(x,y)$ 的网格坐标被定义为 $((x\ge x1)+(x\ge x2),(y\ge y1)+(y\ge y2))$。

依次进行以下步骤：

查询网格坐标为 $(X,Y)$ 的点的权值之和，记录在 $ans[X][Y]$。
对每个网格坐标为 $(X,Y)$ 的点，进行修改 $o[X][Y]$。
所有点的坐标同时发生改变，对于一个网格坐标为 $(X,Y)$ 的点，它的坐标从 $(x,y)$ 变为 $(x+dx[X],y+dy[Y])$；其中 $dx[0]=0$，$dx[1]=n-x2$，$dx[2]=x1-x2$。 $dy[0]=0$，$dy[1]=n-y2$，$dy[2]=y1-y2$。 $x1,x2,y1,y2,o,ans$ 都是数组，下标对应操作的编号。

其中 $d_i$ 属于抽象的数据类型 $D$，$o[X][Y]$ 属于抽象的数据类型 $O$；

$D$ 上定义了抽象的运算 $+:D\times D\to D$；

$D,O$ 上定义了抽象的运算 $\cdot:O\times D\to D$；

$O$ 上定义了抽象的运算 $\cdot:O\times O\to O$；

$\epsilon_D$ 是 $D$ 中的一个特殊的元素，称为单位元；

$\epsilon_O$ 是 $O$ 中的一个特殊的元素，称为单位元；

这些操作满足性质：

对任意 $a,b,c\in D$，有 $a+b=b+a$，$(a+b)+c=a+(b+c)$，$a+\epsilon_D=\epsilon_D+a=a$；

对任意 $u,v,w\in O$，有$(u\cdot v)\cdot w=u\cdot(v\cdot w)$，$u\cdot\epsilon_O=\epsilon_O\cdot u=u$；

对任意 $u,v\in O$，$a,b\in D$，有$(u\cdot v)\cdot a=u\cdot (v\cdot a)$，$u\cdot (a+b)=(u\cdot a)+(u\cdot b)$，$\epsilon_O\cdot a=a$，$u\cdot \epsilon_D=\epsilon_D$；

执行每次 $+$ 或 $\cdot$ 运算有一定的代价，具体地，在计算 $a+b$ 或 $a\cdot b$ 时如果 $a,b$ 都不是 $\epsilon_D$ 或 $\epsilon_O$，则代价为 $1$，否则代价为 $0$。你需要保证每个答案正确，且总代价不能超过当前子任务的代价上限。

实现细节

你需要引用 data.h 头文件。

头文件中定义了数据类型 Data （$D$）和 Operation （$O$），你可以使用以下已定义的成员函数对类型为 Data 和 Operation 的数据进行操作：

void Data::add_eq(const Data &a)

w.add(a) 计算 $w+a$，并将结果保存在 $w$，每次调用的代价在 $w,a$ 都不是单位元时为 $1$，否则为 $0$；

void Data::add(const Data &a,const Data &b)

w.add(a,b) 计算 $a+b$，并将结果保存在 $w$，每次调用的代价在 $a,b$ 都不是单位元时为 $1$，否则为 $0$；

void Data::clr()

w.clr() 可以将 $\epsilon_D$ 保存在 $w$，每次调用的代价为 $0$；

bool Data::empty()const

w.empty() 判断 $w$ 是否为 $\epsilon_D$，若是则返回 $\mathrm{true}$，否则返回 $\mathrm{false}$，每次调用的代价为 $0$；

void Operation::apply(Data &a)const

w.apply(a) 计算 $w\cdot a$，并将结果保存在 $a$，每次调用的代价在 $w,a$ 都不是单位元时为 $1$，否则为 $0$；

void Operation::apply(Operation &u)const

w.apply(u) 计算 $w\cdot u$，并将结果保存在 $u$，每次调用的代价在 $w,u$ 都不是单位元时为 $1$，否则为 $0$；

void Operation::clr()

w.print() 可以将 $\epsilon_O$ 存储在 $w$，每次调用的代价为 $0$；

bool Operation::empty()const

w.empty() 判断 $w$ 是否为 $\epsilon_O$，若是则返回 $\mathrm{true}$，否则返回 $\mathrm{false}$，每次调用的代价为 $0$；

另外，你还可以使用 Data 或 Operation 类型的赋值运算符、拷贝构造函数或无参构造函数，以 Data 类型为例：

w=u 可以将 $u$ 复制一份存储在 $w$，每次调用的代价为 $0$；

Data w(u); 或 Data w=u; 可以将 $u$ 复制一份存储在新定义的 $w$，每次调用的代价为 $0$；

Data w; 可以将 $\epsilon_D$ 存储在新定义的 $w$，代价为 $0$；

Operation w; 可以将 $\epsilon_O$ 存储在新定义的 $w$，代价为 $0$；

除了以上描述的对 Data 或 Operation 的操作外，其余操作根据情况可能被视为攻击评测系统。

sizeof(Data) 和 sizeof(Operation) 都不超过 $64$，此外交互库还需要不超过 64MB 的空间。时间和空间限制包括交互库使用的时间和空间。仅使用赋值、构造函数、apply 和 add 就可以写出正确的程序，其它函数可能可以提供便利。

你需要实现以下函数：

void solve(
    const int n,
    const int m,
    const int p[],
    const Data d[],
    const int x1[],
    const int x2[],
    const int y1[],
    const int y2[],
    const Operation o[][3][3],
    Data ans[][3][3])

$n$：点的个数；
$m$：操作的个数；
$p$：$(i,p[i])$ 表示每个点的坐标，$0\le i < n$；
$d$：$d[i]$ 表示每个点的初始权值，$0\le i < n$；
$x1,x2,y1,y2,o,ans$：$x1[i],y1[i],x2[i],y2[i],o[i]$ 表示每次操作的输入，你需要将相应的答案存储到 $ans[i]$，$0\le i < m$。

下发文件中包含了你需要引用的头文件以及样例交互库。

输入格式

下发的交互库以如下格式读取输入数据：

第一行：$n$
接下来 $n$ 行：$p_i\;d_i$（$d_i$ 由两个整数表示）
第 $n+2$ 行：$m$
接下来 $m$ 行：$x1_i\;x2_i\;y1_i\;y2_i\;o_i$（$o_i$ 由 $9 \times 4$ 个整数表示）

$D$ 中的元素是 $2\times 1$ 的矩阵，$O$ 中元素是 $2\times 2$ 的矩阵，矩阵中的元素是对 $2^{32}$ 取模的整数；

$+$ 对应矩阵加法，$\cdot$ 对应矩阵乘法，具体可以参考下发的交互库的实现；

实际评测环境中输入输出格式以及 $D,O$ 等可能有不同的定义；

输出格式

下发的交互库以如下格式打印你的答案：

对每个询问，输出 $13$ 行，其中第 $1 , 2 , 3 , 5 , 6 , 7 , 9 , 10 , 11$ 行有两个整数，依次表示这次询问对应的$ans[0][0],ans[0][1],ans[0][2],ans[1][0],ans[1][1],ans[1][2],ans[2][0],ans[2][1],ans[2][2]$，其余为空行；
向 stderr 打印总代价，以及在总代价超过代价上限时进行提示。

样例数据

样例 1 输入

4
1 1 1
2 10 5
0 6 9
3 10 4
2
2 3 1 3 10 10 11 11 10 5 7 3 2 3 6 3 2 2 8 2 3 7 2 4 7 11 8 6 9 5 3 7 11 10 10 8 8 5 5 7
1 2 1 2 2 3 6 11 1 1 5 11 5 2 8 6 1 6 9 2 7 11 3 6 9 10 8 2 9 2 9 8 2 11 3 9 4 11 2 5

样例 1 输出

样例 2 输入

10
3 5 8
1 4 6
6 8 10
9 7 5
7 6 2
4 9 1
8 8 5
0 3 5
2 6 2
5 10 3
10
4 8 8 9 5 8 3 6 7 7 10 11 10 9 10 3 5 11 3 4 10 3 8 1 3 8 4 11 3 11 5 6 2 5 11 9 6 6 2 1
4 6 5 6 1 2 1 7 10 7 9 11 11 10 10 5 3 2 2 8 2 1 6 1 9 6 6 5 9 4 6 7 2 7 5 4 3 8 1 6
1 5 6 9 7 3 9 2 5 3 2 10 6 11 5 10 5 9 8 5 11 3 3 5 5 10 2 6 2 5 8 4 5 6 10 2 10 11 1 7
3 4 3 9 9 7 1 3 8 4 2 10 5 8 11 3 4 2 1 7 3 9 8 5 4 4 6 6 8 11 11 1 4 7 2 3 2 2 3 10
6 9 2 7 4 6 1 5 6 7 2 4 2 3 11 10 1 10 1 4 10 6 8 3 3 8 1 1 11 2 8 5 5 9 4 11 5 5 9 8
5 7 5 8 10 11 9 8 10 4 1 7 7 1 5 2 10 6 4 5 4 2 1 10 1 3 5 11 1 6 2 1 6 1 6 10 11 10 1 8
3 6 1 6 10 11 9 3 7 3 9 6 1 9 11 6 7 6 3 9 4 11 4 7 2 4 5 5 5 3 4 11 3 4 4 4 6 4 1 9
6 8 2 6 11 5 7 6 6 5 7 5 9 10 6 11 4 4 2 7 2 11 4 9 3 8 7 9 3 3 5 10 2 9 9 4 7 9 7 11
2 5 1 4 5 6 7 1 2 1 1 9 6 10 6 6 1 9 5 10 7 1 8 10 1 4 4 3 9 11 11 6 9 6 8 2 8 10 11 7
6 7 3 6 11 11 11 3 6 6 9 7 6 7 2 5 3 1 8 8 1 9 4 10 9 11 6 4 2 11 10 8 3 6 6 5 11 3 11 8

样例 2 输出

17 24
0 0
7 5

18 8
8 5
0 0

16 5
0 0
0 0


157 111
0 0
235 169

40 42
63 68
0 0

126 60
0 0
147 95


215 530
0 0
0 0

2324 2024
2479 1783
0 0

1578 1592
837 509
194 446


0 0
7116 10231
7239 9388

4607 8460
0 0
0 0

6944 6628
64844 45048
0 0


72300 52348
265311 254999
50596 23640

0 0
279180 126900
244936 114292

35348 63827
0 0
0 0


172112 792956
2447373 1106786
929486 443832

1119770 935959
0 0
0 0

1649144 359228
0 0
3553200 2614140


0 0
6950234 5535094
22444890 7998435

0 0
10443636 7892656
71682584 26662760

8776334 5075523
11841632 7740868
0 0


0 0
134875573 343366288
91300520 125610782

59108239 90936089
21697728 43262120
0 0

228318480 448464600
0 0
128593760 97023136


0 0
0 0
2054901740 1978497310

0 0
72853820 66252472
1991063770 2020209575

600177312 754769101
3803713784 3298681920
1004356824 1001672808


3063260331 3299980482
4100473464 1966207784
3031825976 3091919392

0 0
325795536 455181888
0 0

2133373140 3095093880
3643561634 2339855333
576229212 1245355280

子任务

Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足 $n\le 10^5,m\le 2\times 10^4$。

共 10 组数据，满足 $n=10^5$；

每组数据的 $m$ 分别为 $10,100,1000,2000,5000,10000,12500,15000,17500,20000$；

所有数据的代价上限为 $10^8$。

每组数据对应 $10$ 分。

QOJ.ac

QOJ

#7451. TB5X