| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 42 | 25 | 12 | 63.158% |
1ドル$ 이상 $N$ 이하의 정수가 한 번씩 등장하는 길이 $N$의 수열 $A$가 주어진다.
수열 $A$에 대한 RMQ란 보통 Range Minimum Query 또는 Range Maximum Query를 뜻하는 말로, 1ドル \le l \le r \le N$인 $l$과 $r$이 주어졌을 때 $\min(A_l,\cdots\!,A_r)$ 또는 $\max(A_l,\cdots\!,A_r)$를 구하는 쿼리를 의미한다.
어느 쿼리도 포기하지 못했던 종영이는 새로운 RMQ를 만들기로 했다. 종영이가 새로 만든 RMQ(Range Mueonga Query)는 $RMQ(l,r)=\min(A_l,\cdots\!,A_r) \times \max(A_l,\cdots\!,A_r)$를 의미한다.
모든 쿼리 값들을 기억하기 위해, $N$행 $N$열의 2차원 배열 $B$에 대해 $i$행 $j$열의 위치에 해당하는 값 $B_{i,j}$에 $i \le j$라면 $RMQ(i,j)$를, $i>j$라면 0ドル$을 써 놓았다.
쿼리 중독증인 종영이는 이제 $B$에서 2차원 쿼리를 날리고 싶어졌다. 종영이를 위해 1ドル \le l \le r \le N$이고 1ドル \le s \le e \le N$인 네 정수 $l,ドル $r,ドル $s,ドル $e$가 주어질 때마다 $l \le i \le r$이고 $s \le j \le e$인 모든 $i,ドル $j$에 대해 $B_{i,j}$의 합을 구해주자.
첫째 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다. $(1 \le N \le 150,000,円 1 \le Q \le 150,000円)$
둘째 줄에 $A_1,ドル $\cdots,ドル $A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le N)$
셋째 줄부터 $Q$개의 줄에 걸쳐 쿼리들이 주어진다. 각 쿼리에서는 $l,ドル $r,ドル $s,ドル $e$가 공백으로 구분되어 주어진다. (1ドル \le l \le r \le N,ドル 1ドル \le s \le e \le N$)
각 줄에 쿼리의 답을 10ドル^9+7$로 나눈 나머지를 출력한다.
10 10 7 6 1 10 5 3 2 4 8 9 1 2 7 8 7 9 8 8 2 10 8 8 5 10 1 4 7 9 2 9 1 7 8 10 3 8 5 9 3 10 2 6 1 4 4 8 1 3 1 5
40 24 82 0 140 278 381 260 370 201
University > 서울대학교 > 서울대학교 프로그래밍 경시대회 > 2021 서울대학교 프로그래밍 경시대회 > Division 1 H번
Contest > Open Cup > 2021/2022 Season > Stage 4: Grand Prix of Korea M번