分数: 6 点
问题陈述
有一个坐标平面 P.
考虑执行该平面上的绘制点操作并将其删除。最初,没有绘制点 P.
进程总共 Q 按给定顺序以下列形式查询。
+ x y
绘制一个点 (x,y) in P.
- x y
删除绘制于 (x,y) in P.
处理每个查询后,回答以下问题。
考虑当前绘制的所有(无序)点对 P;有 \frac{k(k-1)}{2} 这样的对,其中 k 是当前绘制的点数 P.
求所有这些对的以下值(始终为整数)的总和 998244353:以原点为顶点(点 (0,0))和该对中的点(如果这三个点位于同一条线上,则假定面积为 0).
约束
- 1 \le Q \le 3 \times 10^5
- 对于每个
+查询, -10^5 \le x,y \le 10^5 和 (x,y) \neq (0,0). - 在每个
-查询,至少有一个点绘制在 (x,y). - 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出,其中 \mathrm{Query}_i 表示 i第一个查询:
Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q
输出
共打印 Q 行, i- 其中应包含问题的答案 i第一个查询已作为整数处理。
示例输入 1
5 + 2 3 + -1 2 + 1 -2 - -1 2 + -1 -1
示例输出 1
0 7 14 7 11
- 的 1-st 查询绘制一个点 (2,3).
- 此时,问题的答案是 0.
- 的 2-nd 查询绘制一个点 (-1,2).
- 具有顶点的三角形的面积 (2,3),(-1,2),(0,0) is \frac{7}{2}.
- 此时,三角形的总面积为 \frac{7}{2},所以问题的答案是 7.
- 的 3-rd 查询绘制一个点 (1,-2).
- 具有顶点的三角形的面积 (2,3),(1,-2),(0,0) is \frac{7}{2}.
- 具有顶点的三角形的面积 (-1,2),(1,-2),(0,0) 假设为 0 因为这三个点位于同一条线上。
- 此时,三角形的总面积为 7,所以问题的答案是 14.
- 的 4-th 查询删除位于 (-1,2).
- 此时,三角形的总面积为 \frac{7}{2},所以问题的答案是 7.
- 的 5-th 查询绘制一个点 (-1,-1).
- 具有顶点的三角形的面积 (1,-2),(-1,-1),(0,0) is \frac{3}{2}.
- 具有顶点的三角形的面积 (-1,-1),(2,3),(0,0) is \frac{1}{2}.
- 此时,三角形的总面积为 \frac{11}{2},所以问题的答案是 11.
示例输入 2
10 + 100000 100000 + 100000 -100000 + 100000 100000 + 100000 -100000 + 100000 100000 - 100000 100000 - 100000 -100000 - 100000 100000 - 100000 -100000 - 100000 100000
示例输出 2
0 35112940 70225880 140451760 210677640 140451760 70225880 35112940 0 0
一定要找到求和模 998244353.
此外,可以在同一坐标处绘制多个点。
请注意,删除点时,仅删除一个点,而不是指定坐标处的所有点。
示例输入 3
10 + -5010 51358 + 95817 96893 + 19668 -58533 - 95817 96893 - -5010 51358 + 90155 -74912 - 90155 -74912 + -83888 -29953 - -83888 -29953 + 72565 37307
示例输出 3
0 415181651 660233626 716858814 0 808940340 0 508110143 0 988223809