QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100 Interactive

# 7451. 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.h 头文件。

头文件中定义了数据类型 Data ($D$)和 Operation ($O$),你可以使用以下已定义的成员函数对类型为 DataOperation 的数据进行操作:

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$;

另外,你还可以使用 DataOperation 类型的赋值运算符、拷贝构造函数或无参构造函数,以 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$;

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

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

你需要实现以下函数:

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 输出

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

对于 $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$ 分。