問題一覧 > 通常問題

No.3464 Max and Sum on Grid

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 20
作問者 : dyktr_06 / テスター : tyawanmusi sepa38 hikikomori おのせ
お気に入りにしたユーザー ProblemId : 12394 / 自分の提出
問題文最終更新日: 2026-02-27 23:49:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
MMA Contest 021 (順位表) の他の問題:

Problem Statement

You are given sequences $A$ and $B$ of length $N$.

Here, define an $N \times N$ two-dimensional grid $S$ as follows.

  • $S_{i, j} = \max(A_i, B_j)$

You are given $Q$ queries; process them in order. The $i$-th query is as follows.

  • l d r u: Over all pairs $(x, y)$ satisfying $l \leq x \leq r$, $d \leq y \leq u$, print the sum of $S_{x, y}$.

Constraints

  • $1 \leq N \leq 20000$
  • $1 \leq Q \leq 10^{5}$
  • $1 \leq A_i, B_i \leq 10^{5}$
  • $1 \leq l \leq r \leq N$
  • $1 \leq d \leq u \leq N$
  • All input values are integers.

Input

The input is given from standard input in the following format.

$N$ $Q$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$ $B_2$ $\cdots$ $B_N$
$\text{query}_{1}$  
$\text{query}_{2}$  
$\vdots$

$\text{query}_{Q}$

Each query is given in the following format.

$l$ $d$ $r$ $u$

Output

Print $Q$ lines.

On the $i$-th line, print the answer to the $i$-th query.

Sample

Sample 1
Input
5 4
8 6 2 4 1
2 3 5 7 11
2 3 3 4
4 2 5 4
1 1 3 3
1 1 5 5
Output
25
31
52
166

For example, for the $1$-st query, $S_{2, 3} + S_{2, 4} + S_{3, 3} + S_{3, 4} = \max(A_2, B_3) + \max(A_2, B_4) + \max(A_3, B_3) + \max(A_3, B_4) = 6 + 7 + 5 + 7 = 25$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。