题目背景

题目描述

本地测试需 #include <data.h>

提交时请采用以下模板，而不 include data.h，具体方法就是直接把这个模板放在自己代码里面。

以下说明均为对本地测试的说明，提交时请注意上面的说明。

class Data{
	friend int main();
  private:
	unsigned short x1,x2,x3,x4;
  public:
	void add(const Data &a,const Data &b);
	void sub(const Data &a,const Data &b);
	void clr();
};
void solve(
	int n,
	int xy[][2],
	Data d[],
	int m,
	int abc[][3],
	int q,
	int lr[][2],
	Data ans[]);

这是一道交互题，你需要借助 Data 类实现 solve() 函数。你可以使用 Data 类的成员函数 add()、sub()、clr()，以及 C++ 编译器自动合成的函数（包括构造函数和赋值运算符）。

设所有 Data 类型的元素组成的集合为 $D$。

对任意 $a,b,c\in D$，有以下性质：

• $a+b, a-b \in D$
• $(a+b)+c=a+(b+c)$
• $a+b=b+a$

存在单位元 $e \in D$，使得对任意 $a,b\in D$，有以下性质：

• $a+e=e+a=a$
• $a+(e-a)=(e-a)+a=e$
• $a-b=a+(e-b)$

上述性质也可以表述为：$(D,+,-,e)$ 构成一个交换群。

给定 $n$ 个点，第 $i$ 个点有坐标 $(x_i,y_i)$ 和 Data 类的权值 $d_i$，$i=1,2,\dots,n$；

给定 $m$ 个半平面 $(A_i,B_i,C_i)$，$i=1,2,\dots,m$；

共有 $q$ 次询问 $l_i,r_i$，$i=1,2,\dots,q$；

第 $i$ 次询问中，你需要回答一个区间中的半平面的交的点权和，具体来说：

设集合 $S_i = \{ k \mid \forall l_i \le j \le r_i, A_jx_k + B_jy_k \ge C_j \}$，求 $\sum\limits_{k \in S_i} d_k$。

提示

Idea：nzhtl1477，Solution：nzhtl1477&ccz181078，Code：ccz181078，Data：ccz181078

接口说明

使用 a.clr() 函数可以将 $a$ 设为单位元 $e$。

使用 a.add(b,c) 函数可以将 $a$ 设为 $b+c$。

使用 a.sub(b,c) 函数可以将 $a$ 设为 $b-c$。

使用 a=b 可以将 $a$ 设为 $b$。

评测说明

你需要实现的函数 solve 的接口信息如下：

void solve(
	int n,
	int xy[][2],
	Data d[],
	int m,
	int abc[][3],
	int q,
	int lr[][2],
	Data ans[]);

评测时，交互库会恰好调用 solve 一次。

在 solve 函数的参数中，$x_i$ 对应 xy[i][0]，$y_i$ 对应 xy[i][1]，$d_i$ 对应 d[i]；

$A_i,B_i,C_i$ 对应 abc[i][0],abc[i][1],abc[i][2]；

$l_i,r_i$ 对应 lr[i][0],lr[i][1]，第 $i$ 次询问的答案需要被保存在 ans[i]；

$n,m,q$ 对应 n,m,q。

你可以进行任意次对元素的赋值、拷贝或者 clr() 函数的调用，但调用 add() 和 sub() 的次数之和不能超过 $4\times 10^7$。

对 C++ 语言选手，请确保你的程序开头有

#include "data.h"

试题目录下的 grader.cpp 是我们提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

对 C++ 语言的选手：

你需要将本题提交代码命名为 chesed.cpp，并在本题目录下使用如下命令编译得到可执行程序：

g++ grader.cpp chesed.cpp -o chesed -O2 -lm

对于编译得到的可执行程序：

先从该测试点的输入数据中读入数据。

读入完成之后，交互库将调用恰好一次函数 solve，用输入数据测试你的函数。

你的函数正确返回后，交互库会根据你返回的结果向输出文件中输出每次询问的答案，如果你输出的答案和对应测试点的输出文件除行末空格外完全一致，则判定你通过该测试数据。

限制与约定

对于 $25\%$ 的数据，满足 $n,m,q\le 100$；

对于另外 $25\%$ 的数据，满足 $q\le 100$；

对于另外 $25\%$ 的数据，满足 $l_i=r_i$，$x_i,y_i$ 独立地在数据范围内均匀随机选取；

对 $100\%$ 的数据，满足 $1\le n\le 2\times 10^5$，$1\le m\le 10^4$，$1\le q\le 10^5$，$|A_j|,|B_j|\le 10^4$，$|x_i|,|y_i|,|C_j|\le 10^5$，$B_j>0$，$C_j<0$，$-10^6\le C_j<0$，$1\le l_i\le r_i\le m$。