[Ynoi2007] TB5x
题目描述
这是一道交互题。
二维平面上初始有 $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])$。
依次进行以下步骤：
1. 查询网格坐标为 $(X,Y)$ 的点的权值之和，记录在 $ans[X][Y]$。
2. 对每个网格坐标为 $(X,Y)$ 的点，进行修改 $o[X][Y]$。
3. 所有点的坐标同时发生改变，对于一个网格坐标为 $(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` （$D$）和 `Operation` （$O$），你可以使用以下已定义的成员函数对类型为 `Data` 和 `Operation` 的数据进行操作：
```c++
void Data::add_eq(const Data &a)
```
`w.add(a)` 计算 $w+a$，并将结果保存在 $w$，每次调用的代价在 $w,a$ 都不是单位元时为 $1$，否则为 $0$；
```c++
void Data::add(const Data &a,const Data &b)
```
`w.add(a,b)` 计算 $a+b$，并将结果保存在 $w$，每次调用的代价在 $a,b$ 都不是单位元时为 $1$，否则为 $0$；
```c++
void Data::clr()
```
`w.clr()` 可以将 $\epsilon_D$ 保存在 $w$，每次调用的代价为 $0$；
```c++
bool Data::empty()const
```
`w.empty()` 判断 $w$ 是否为 $\epsilon_D$，若是则返回 $\mathrm{true}$，否则返回 $\mathrm{false}$，每次调用的代价为 $0$；
```c++
void Operation::apply(Data &a)const
```
`w.apply(a)` 计算 $w\cdot a$，并将结果保存在 $a$，每次调用的代价在 $w,a$ 都不是单位元时为 $1$，否则为 $0$；
```c++
void Operation::apply(Operation &u)const
```
`w.apply(u)` 计算 $w\cdot u$，并将结果保存在 $u$，每次调用的代价在 $w,u$ 都不是单位元时为 $1$，否则为 $0$；
```c++
void Operation::clr()
```
`w.print()` 可以将 $\epsilon_O$ 存储在 $w$，每次调用的代价为 $0$；
```c++
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` 就可以写出正确的程序，其它函数可能可以提供便利。
你需要实现以下函数：
```c++
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$。
为了您的方便，这里提供模板。请完善以下代码：
```cpp
/* BEGIN HEADER: */
class Data {
friend class Operation;
friend int main();
private:
unsigned int x, sz, T, flag;
void read();
void print() const;
public:
Data() { clr(); }
void add_eq(const Data &a);
void add(const Data &a, const Data &b);
void clr();
bool empty() const;
};
class Operation {
friend int main();
private:
unsigned int a, b, L, R, flag;
void read();
public:
Operation() { clr(); }
void apply(Data &w) const;
void apply(Operation &w) const;
void clr();
bool empty() const;
};
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]);
/* END HEADER. */
#include <bits/stdc++.h>
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]) {
// complete this
}
```
由于洛谷的交互方法比较奇怪，所以提交的时候需要把本地的代码复制过来，放在这个 solve 函数这里，和前面的 HEADER 一起提交。提交时不引用 "data.h" 头文件。
输入输出格式
输入格式
下发的交互库以如下格式读取输入数据：
- 第一行：$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
0 0
11 6
0 0
6 9
0 0
0 0
0 0
0 0
10 4
0 0
0 0
15 10
0 0
0 0
125 85
30 66
100 78
0 0
输入样例 #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
Special thanks：w33z8kqrqk8zzzx33 修改交互库使得能在洛谷上运行。
对于 $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$ 分。