QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100

# 9020. 测测你的半平面修改查询

统计

这是一道交互题。

给定平面上的 $n$ 个点,第 $i+1$ 个点为 $(x_i,y_i)$,初始值为 $d_i$,$0\le i < n$;

你需要按顺序进行 $m$ 次操作,所有操作在一开始已知;

第 $j+1$ 次操作给出三个数 $a_j,b_j,c_j$,以及 $o_j$,表示半平面 $a_jx+b_jy < c_j$,$0\le j < m$;

你需要按顺序执行:

首先令 $s_j=\epsilon_D$,然后对每个满足 $a_jx_i+b_jy_i < c_j$ 的 $i$,先将 $s_j$ 修改为 $s_j+d_i$,后将 $d_i$ 修改为 $o_j\cdot d_i$;

完成这些修改后,就得到了这次操作的答案 $s_j$;

其中 $d_i$ 属于抽象的数据类型 $D$,$o_j$ 属于抽象的数据类型 $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。你需要保证每个答案正确,且总代价不能超过当前子任务的代价上限

输入格式

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

  • 第一行:$n$
  • 接下来 $n$ 行:$x_i\;y_i\;d_i$($d_i$ 由两个整数表示)
  • 第 $n+2$ 行:$m$
  • 接下来 $m$ 行:$a_i\;b_i\;c_i\;o_i$($o_i$ 由4个整数表示)

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

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

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

输出格式

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

  • 前 $m$ 行:$s_i$,由两个整数表示
  • 第 $m+1$ 行:总代价

实现细节

你必须引用 hpmq.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;

void Data::print()const

w.print() 可以将 $w$ 作为一次操作的答案,每次调用的代价为0,这个函数需要被调用恰好 $m$ 次,依次对应每次操作的答案;

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 *x,
    const int *y,
    const Data *d,
    const int *a,
    const int *b,
    const int *c,
    const Operation *o)
  • $n$:点的个数;
  • $x,y,d$:大小为 $n$ 的数组,其中 $(x_i,y_i)$ 为第 $i+1$ 个点的坐标,这个点的初始值为 $d_i$;
  • $m$:操作的个数;
  • $a,b,c,o$:大小为 $m$ 的数组,其中第 $i+1$ 次操作的范围为半平面 $a_ix+b_iy < c_i$,修改操作为 $o_i$;

限制与约定

对于所有数据,满足:

$|x_i|\le 10^6$,$|y_i|\le 10^6$;

$|a_i|\le 10^3$,$|b_i|\le 10^3$,$b_i\ne 0$,$|c_i|\le 10^6$;

$x_i,y_i,a_i,b_i,c_i$ 为整数;

对任意 $i,j$,有 $a_ix_j+b_iy_j\ne c_i$,即不存在点在直线上的情况;

对任意 $i\ne j$,有 $\left(\frac{a_i}{b_i},\frac{c_i}{b_i}\right)\ne \left(\frac{a_j}{b_j},\frac{c_j}{b_j}\right)$,即不存在重合的直线;

数据被分为8个子任务,每个子任务有固定的 $n,m$ 和允许的代价上限,每个子任务可能依赖其它子任务,只有通过一个子任务和其依赖的子任务的所有测试点才能获得这个子任务的分值;

子任务 n m 代价上限 分值 依赖
1 $2\times 10^4$ $10^3$ $4\times 10^7$ 5
2 $2\times 10^4$ $10^3$ $8\times 10^5$ 15 1
3 $2\times 10^5$ $10^2$ $4\times 10^7$ 5
4 $2\times 10^5$ $10^2$ $1.25\times 10^6$ 15 3
5 $2^{16}$ $10^4$ $8\times 10^7$ 20
6 $2\times 10^5$ $10^4$ $2.5\times 10^7$ 10
7 $2\times 10^5$ $10^4$ $1.25\times 10^8$ 15
8 $2\times 10^5$ $10^4$ $2.5\times 10^7$ 15 1~7

子任务5满足特殊限制:$-2^7\le x_i < 2^7$,$-2^7\le y_i < 2^7$,对任意 $i\ne j$,有 $\left(x_i,y_i\right)\ne \left(x_j,y_j\right)$,即不存在重合的点;

子任务6满足特殊限制:对 $0\le i < n,\;0\le j < m$,$x_i=0$,$y_i=2i$,$a_j=0$,$|b_j|=1$;