최댓값과 쿼리

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

요약
이전 행에서 원형으로 이웃한 두 값의 최댓값으로 다음 행을 만들고, 부분행렬 합 쿼리에 답한다.
난이도

어려움10점 중 8점

유형
누적 합, 동적 계획법, 수학
정답자
아직 제출이 없습니다

문제

크기 NN의 정사각행렬 AA가 아래 식을 만족한다.

1<i≤N1\lt i \le N일 때 A_i,j={max⁡(A_i−1,j,A_i−1,j−1)if j>1 max⁡(A_i−1,1,A_i−1,N)if j=1A\_{i,j} = \begin{cases} \max(A\_{i-1,j},A\_{i-1,j-1}) & \text{if }j>1 \\\ \max(A\_{i-1,1}, A\_{i-1,N}) & \text{if }j=1 \end{cases}

A_1,1,A_1,2,⋯ ,A_1,NA\_{1,1}, A\_{1,2}, \cdots, A\_{1,N}이 주어질 때, 다음 쿼리를 수행하라.

  • aa bb cc dd: ∑_i=ab∑_j=cdA_i,j\sum\_{i=a}^b \sum\_{j=c}^d A\_{i,j}를 998,244,353998\\,244\\,353으로 나눈 나머지를 출력한다.

입력

첫째 줄에 NN, QQ가 공백으로 구분되어 주어진다. (1≤N,Q≤200,000)(1 \le N, Q \le 200 \\, 000)

둘째 줄에 A_1,1,A_1,2,⋯ ,A_1,NA\_{1,1}, A\_{1,2}, \cdots, A\_{1,N}이 공백으로 구분되어 주어진다. (1≤j≤N;(1 \le j \le N; 0≤A_1,j<998,244,353)0 \le A\_{1,j} \lt 998 \\, 244 \\, 353)

셋째 줄부터 QQ개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. (1≤a≤b≤N;(1 \le a \le b \le N; 1≤c≤d≤N)1 \le c \le d \le N)

입력으로 주어지는 모든 수는 정수이다.

출력

각 줄에 쿼리의 답을 한 줄에 하나씩 순서대로 출력한다.

예제2

  1. 예제 1

    입력
    2 5
100 200
1 1 1 1
1 1 2 2
2 2 1 1
2 2 2 2
1 2 1 2
    예상 출력
    100
200
200
200
700

  2. 예제 2

    입력
    5 5
100 200 300 150 300
1 1 1 5
1 5 2 4
1 5 1 5
4 5 4 5
2 4 4 4
    예상 출력
    1050
4150
6950
1200
900