P12762 [POI 2018 R2] 电信中继站 Transceivers

翻译来自于 [LibreOJ](https://loj.ac/p/5070)。

**题目译自 [XXV Olimpiada Informatyczna — II etap](https://sio2.mimuw.edu.pl/c/oi25-2/dashboard/) [Przekaźniki telekomunikacyjne](https://szkopul.edu.pl/problemset/problem/GmAagCBetbskP0qiKlgVd-6A/statement/)** 国王 Bajtazar 顺应时代潮流，决定为拜托尼亚王国铺设移动电话网络，覆盖所有村庄和城市。这些地点分布在一条笔直的道路上，可视为数轴。 新任命的电信顾问需要一个程序，测试中继站天线杆的位置。每根天线杆顶端装有中继站，由参数 $s$ 和 $a$ 描述。在杆位置 $x$，信号强度为 $s$；在其他点，信号强度随距离线性下降，即在点 $x \pm d$，强度为 $\max(0, s - a \cdot d)$。 道路上某点的信号覆盖强度为所有中继站信号强度的总和。 程序需支持添加或移除天线杆，以及查询某段整数点平均信号覆盖强度的操作。

第一行包含两个整数 $n, m$ $(n \geq 2, m \geq 1)$，分别表示道路长度和操作数量。 接下来的 $m$ 行描述操作，每行以单个字符开头，表示操作类型，后跟一至三个整数： - $\texttt{P}\ x\ s\ a$：在点 $x$ 架设天线杆，安装中继站，参数为 $s, a$ $(1 \leq x \leq n, 1 \leq s, a \leq 100000)$。 - $\texttt{U}\ x$：移除点 $x$ $(1 \leq x \leq n)$ 的天线杆。 - $\texttt{Z}\ x_1\ x_2$：查询区间 $[x_1, x_2]$ 内所有整数点 $x$ $(x_1 \leq x \leq x_2, 1 \leq x_1 \leq x_2 \leq n)$ 的平均信号覆盖强度。 各行数据以单空格分隔。保证操作 $\texttt{P}$ 时点 $x$ 无天线杆，操作 $\texttt{U}$ 时点 $x$ 有天线杆。

输出与输入中 $\texttt{Z}$ 操作数量相同的行，每行包含一个整数，表示对应查询的平均信号覆盖强度，向下取整。

**样例 1 解释** | 操作 | 结果 | 说明 | |:------:|:------:|:------:| | $\texttt{P}\ 5\ 30\ 10$ | - | 在点 $x=5$ 架设天线杆，中继站参数 $s=30, a=10$。 | | $\texttt{Z}\ 6\ 7$ | $15$ | 点 $6$ 信号强度为 $30-10=20$，点 $7$ 为 $30-2 \cdot 10=10$，区间 $[6,7]$ 整数点的平均强度为 $(20+10)/2=15$。 | | $\texttt{P}\ 10\ 22\ 5$ | - | 在点 $x=10$ 架设天线杆，中继站参数 $s=22, a=5$。 | | $\texttt{Z}\ 6\ 7$ | $19$ | 两杆存在，点 $6$ 强度为 $20+2=22$，点 $7$ 为 $10+7=17$，平均强度为 $(22+17)/2=19.5$，向下取整为 $19$。 | | $\texttt{Z}\ 6\ 6$ | $22$ | 点 $6$ 强度为 $22$，平均为 $22$。 | | $\texttt{U}\ 5$ | - | 移除点 $x=5$ 的天线杆。 | | $\texttt{Z}\ 6\ 6$ | $2$ | 点 $6$ 强度为 $2$（仅剩 $x=10$ 的中继站）。 | **附加样例** 1. $n=101, m=500$，道路首尾中各一杆，随机查询。 2. $n=300000$，点 $1$ 有一杆，$s=100000, a=100$，查询各前缀 $[1, i]$ 的平均强度，$1 \leq i \leq 300000$。 3. $n=300000, m=500000$，每点有杆，$s=1000, a=1$，查询整条路的平均强度。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n, m \leq 2000$ | $8$ | | $2$ | $n \leq 300000, m \leq 500000$，$\texttt{Z}$ 操作在所有 $\texttt{P}$、$\texttt{U}$ 操作后 | $24$ | | $3$ | $n \leq 300000, m \leq 500000$，同时最多 $50$ 个中继站 | $16$ | | $4$ | $n \leq 300000, m \leq 500000$，$\texttt{Z}$ 操作总有 $x_1=x_2$ | $15$ | | $5$ | $n, m \leq 100000$ | $15$ | | $6$ | $n \leq 300000, m \leq 500000$，$\texttt{P}$ 操作总有 $a=1$ | $12$ | | $7$ | $n \leq 300000, m \leq 500000$ | $10$ |