직사각형 세기

시간 제한5초메모리 제한1024 MB

요약

배열 A와 B에 원소가 추가될 때마다 A_i + B_j가 0 이상인 칸으로만 이루어진 직사각형의 개수를 998244353으로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 8점
유형: 세그먼트 트리, 스택
정답자: 아직 제출이 없습니다

문제

정수 배열 $A$ (길이 $N$ )와 $B$ (길이 $M$ )에 대해 크기가 $N \times M$ 인 격자 $G(A, B)$ 를 정의한다. 칸 $(i, j)$ 는 $A_i + B_j \ge 0$ 이면 검은색, 아니면 흰색이다.

$F(A, B)$ 는 $G(A, B)$ 안에 있는 검은색 직사각형의 개수이다. 직사각형에 포함된 각 칸은 직사각형에 완전히 포함되거나, 직사각형과 전혀 겹치지 않는다.

즉, $F(A, B)$ 는 $1 \le l_1 \le r_1 \le N$ , $1 \le l_2 \le r_2 \le M$ 을 만족하고, $l_1 \le i \le r_1$ , $l_2 \le j \le r_2$ 인 모든 칸 $(i, j)$ 가 검은색인 튜플 $(l_1, r_1, l_2, r_2)$ 의 개수이다.

처음에는 $A_1$ 과 $B_1$ 만 주어진다. 이후 다음 $Q$ 개의 질의를 처리한다.

0 $v$ : 현재 배열 $A$ 의 끝에 $v$ 를 추가한다.
1 $v$ : 배열 $A$ 의 끝에 $v$ 를 추가한 뒤, $F(A, B) \bmod 998\,244\,353$ 을 출력한다.
2 $v$ : 현재 배열 $B$ 의 끝에 $v$ 를 추가한다.
3 $v$ : 배열 $B$ 의 끝에 $v$ 를 추가한 뒤, $F(A, B) \bmod 998\,244\,353$ 을 출력한다.

입력

첫 줄에 정수 $Q$ 가 주어진다.

둘째 줄에 공백으로 구분된 정수 $A_1$ 과 $B_1$ 이 주어진다.

이어지는 $Q$ 개의 줄에는 각각 위 형식의 질의를 나타내는 공백으로 구분된 정수 두 개가 주어진다.

출력

타입 1 또는 3인 질의마다 그 답을 한 줄에 정수 하나로 출력한다.

제한

$1 \le N \le 250\,000$
$1 \le M \le 250\,000$
$1 \le Q = N + M - 2$
$-10^9 \le A_i \le 10^9$ ( $1 \le i \le N$ )
$-10^9 \le B_i \le 10^9$ ( $1 \le i \le M$ )

여기서 $N$ 은 모든 질의를 처리한 뒤의 배열 $A$ 의 크기이고, $M$ 은 모든 질의를 처리한 뒤의 배열 $B$ 의 크기이다. 마지막 질의의 타입은 1 또는 3이다.

예제2

예제 1
입력
```
4
-4 -3
0 -5
2 2
0 3
3 -5
```
예상 출력
```
3
```

예제 2

입력

8
-187121777 648583176
0 536185451
1 77324177
2 -543947071
1 -495948203
2 809620127
2 918209957
3 -724806401
1 30094601

예상 출력