/ 
Time Limit: 8 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
xy 平面 P があります。
この平面に点を追加したり削除したりする操作を行うことを考えます。はじめ、 P にはひとつも点が追加されていません。
以下のクエリを、与えられた順に合計で Q 個処理してください。
+ x y
P 中の座標 (x,y) に点を 1 つ追加する。
- x y
P 中の座標 (x,y) にある点を 1 つ削除する。
各クエリを処理した直後に、以下の問いに答えてください。
現在 P に残っている任意の相異なる 2 点の（順序を問わない）組を考える。この 2 点の組は、 P 中に点が k 個残っている場合、 \frac{k(k-1)}{2} 通り考えられる。
このとき、それら全てに対して組を構成する 2 点と原点（座標 (0,0)）からなる三角形の面積（ただし、この 3 点を全て通る直線が存在する場合、面積は 0 であるとする）の 2 倍を足し合わせた値（この値は整数になることが示せる）を 998244353 で割った余りを求める。
制約
- 1 \le Q \le 3 \times 10^5
+クエリは以下の制約を満たす。- -10^5 \le x,y \le 10^5 かつ (x,y) \neq (0,0)
-クエリの時点で、 (x,y) に点が 1 つ以上存在する。- 入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。ただし、 \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 つ目のクエリで、 (2,3) に点を 1 つ追加します。
- このクエリを処理した時点で、問いに対する答えは 0 です。
- 2 つ目のクエリで、 (-1,2) に点を 1 つ追加します。
- (2,3),(-1,2),(0,0) からなる三角形の面積は \frac{7}{2} です。
- このクエリを処理した時点で、三角形の面積の総和は \frac{7}{2} なので、問いに対する答えは 7 です。
- 3 つ目のクエリで、 (1,-2) に点を 1 つ追加します。
- (2,3),(1,-2),(0,0) からなる三角形の面積は \frac{7}{2} です。
- (-1,2),(1,-2),(0,0) からなる三角形の面積は、この 3 点を全て通る直線が存在するので、 0 であるとします。
- このクエリを処理した時点で、三角形の面積の総和は 7 なので、問いに対する答えは 14 です。
- 4 つ目のクエリで、 (-1,2) にある点を 1 つ削除します。
- このクエリを処理した時点で、三角形の面積の総和は \frac{7}{2} なので、問いに対する答えは 7 です。
- 5 つ目のクエリで、 (-1,-1) に点を 1 つ追加します。
- (1,-2),(-1,-1),(0,0) からなる三角形の面積は \frac{3}{2} です。
- (-1,-1),(2,3),(0,0) からなる三角形の面積は \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 で割った余りを求めることに注意してください。
同じ座標に複数個の点が追加される場合もあります。
点を削除する際、その座標に複数個の点があっても 1 つだけ削除することに注意してください。
入力例 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
Score : 6 points
Problem Statement
There is a coordinate plane P.
Consider performing operations of plotting points in this plane and deleting them. Initially, no points are plotted in P.
Process a total of Q queries in the following forms in the given order.
+ x y
Plot a point at (x,y) in P.
- x y
Delete a point plotted at (x,y) in P.
After processing each query, answer the following question.
Consider all (unordered) pairs of points currently plotted in P; there are \frac{k(k-1)}{2} such pairs, where k is the current number of points plotted in P.
Find the sum of the following value (which is always an integer) over all those pairs modulo 998244353: the doubled area of the triangle whose vertices are the origin (the point (0,0)) and the points in the pair (if these three points lie on the same line, the area is assumed to be 0).
Constraints
- 1 \le Q \le 3 \times 10^5
- For each
+query, -10^5 \le x,y \le 10^5 and (x,y) \neq (0,0). - At each
-query, at least one point is plotted at (x,y). - All values in input are integers.
Input
Input is given from Standard Input in the following format, where \mathrm{Query}_i denotes the i-th query:
Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q
Output
Print a total of Q lines, the i-th of which should contain the answer to the question when the i-th query has been processed as an integer.
Sample Input 1
5 + 2 3 + -1 2 + 1 -2 - -1 2 + -1 -1
Sample Output 1
0 7 14 7 11
- The 1-st query plots a point at (2,3).
- At this point, the answer to the question is 0.
- The 2-nd query plots a point at (-1,2).
- The area of the triangle with the vertices (2,3),(-1,2),(0,0) is \frac{7}{2}.
- At this point, the total area of the triangles is \frac{7}{2}, so the answer to the question is 7.
- The 3-rd query plots a point at (1,-2).
- The area of the triangle with the vertices (2,3),(1,-2),(0,0) is \frac{7}{2}.
- The area of the triangle with the vertices (-1,2),(1,-2),(0,0) is assumed to be 0 since these three points lie on the same line.
- At this point, the total area of the triangles is 7, so the answer to the question is 14.
- The 4-th query deletes a point at (-1,2).
- At this point, the total area of the triangles is \frac{7}{2}, so the answer to the question is 7.
- The 5-th query plots a point at (-1,-1).
- The area of the triangle with the vertices (1,-2),(-1,-1),(0,0) is \frac{3}{2}.
- The area of the triangle with the vertices (-1,-1),(2,3),(0,0) is \frac{1}{2}.
- At this point, the total area of the triangles is \frac{11}{2}, so the answer to the question is 11.
Sample Input 2
10 + 100000 100000 + 100000 -100000 + 100000 100000 + 100000 -100000 + 100000 100000 - 100000 100000 - 100000 -100000 - 100000 100000 - 100000 -100000 - 100000 100000
Sample Output 2
0 35112940 70225880 140451760 210677640 140451760 70225880 35112940 0 0
Be sure to find the sought sum modulo 998244353.
Also, multiple points may be plotted at the same coordinates.
Note that when deleting a point, just one point is deleted, not all of them at the specified coordinates.
Sample Input 3
10 + -5010 51358 + 95817 96893 + 19668 -58533 - 95817 96893 - -5010 51358 + 90155 -74912 - 90155 -74912 + -83888 -29953 - -83888 -29953 + 72565 37307
Sample Output 3
0 415181651 660233626 716858814 0 808940340 0 508110143 0 988223809