QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Interactive

# 7445. rmpq

统计

这是一道交互题。

实现细节

你需要包含头文件lib.h

在本地编译时,需要和 lib.cpp 一起编译;

交互库提供了以下数据类型和函数:

struct Data{
    unsigned short a,b,c,d;
    void operator*=(const Data &x);
    void clr();
};

Data 类型是一个含幺半群 $(D,*,e)$,具体地:

$D$ 是类型为 Data 的元素构成的集合;

$*:D\times D\to D$

$e\in D$

$\forall x,y,z\in D, x*(y*z)=(x*y)*z$

$\forall x\in D, x*e=e*x=x$

使用 x.clr() 可以将 $x$ 修改为 $e$;

使用 x=y 可以将 $x$ 修改为 $y$;

使用 x*=y 可以将 $x$ 修改为 $x*y$,这个操作的调用次数有常数上限 $2\times 10^7$,不计 $x=e$ 或 $y=e$ 的情况。

初始条件下,平面上每个点 $(x,y)$ 都对应一个权值 $d(x,y)\in D$;

你需要实现以下函数:

void update(int x,int dim,Data d1,Data d2);

对每个 $(x_0,y_0)$ 执行操作:

若 $dim=0$ 且 $x_0 < x$,则将 $d(x_0,y_0)$ 修改为 $d(x_0,y_0)*d1$;

若 $dim=0$ 且 $x_0\ge x$,则将 $d(x_0,y_0)$ 修改为 $d(x_0,y_0)*d2$;

若 $dim=1$ 且 $y_0 < x$,则将 $d(x_0,y_0)$ 修改为 $d(x_0,y_0)*d1$;

若 $dim=1$ 且 $y_0\ge x$,则将 $d(x_0,y_0)$ 修改为 $d(x_0,y_0)*d2$;

Data query(int x,int y);

查询 $d(x,y)$,返回值为答案。

为了您的方便,这里提供模板。请完善以下代码:

/* BEGIN HEADER: */
struct Data{
    unsigned short a,b,c,d;
    void operator*=(const Data &x);
    void clr();
};
void update(int x,int dim,Data d1,Data d2);
Data query(int x,int y);
/* END HEADER. */

#include <bits/stdc++.h>

void update(int x,int dim,Data d1,Data d2){
    // complete this
}
Data query(int x,int y){
    // complete this
}

样例数据

样例输入

10
2 200842854 123159544
2 192001936 902183645
2 996055655 154684468
2 957446126 232761122
1 739061119 1 4 6
1 762263616 1 5 8
1 669159682 0 10 7
2 361701640 274578757
1 392040275 0 2 8
1 800311125 1 3 2

样例输出

(0,0,0,0)
(0,0,0,0)
(0,0,0,0)
(0,0,0,0)
(19,19,329,10)

子任务

Idea:ccz181078,Solution:ccz181078,Code:ccz181078,Data:ccz181078

对于前 8 组数据,操作个数分别为 $10,1000,10000,20000,40000,60000,80000,10^5$,且 $x,y,dim$ 均匀随机选取;

对于其余数据,操作个数为 $10^5$,且构成子任务。

对于所有数据: 对于 update 操作,满足 $1\le x\le 10^9$,$dim\in\{0,1\}$; 对于 query 操作,满足 $1\le x,y\le 10^9$。