← 返回题目列表

AtCoder · past202206_o

O. 区域查询

中文机器翻译题面 查看原题

分数: 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