問題一覧 > 通常問題

No.3265 Back Home, They Treat You Like a Genius!

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 110
作問者 : DeltaStruct / テスター : ゆにたりー卿 Andrew8128 kazuppa 👑 loop0919 bolero のらら elphe Rice_tawara459 よには yimiya（いみや）
お気に入りにしたユーザー ProblemId : 12017 / 自分の提出
問題文最終更新日: 2025-09-06 13:07:34
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
第2回 岩井星人アンソロジープログラミングコンテスト Div.2 (順位表) の他の問題:

Problem Statement

Planet Iwai is inhabited by Iwaians $1,\ \dots,\ N$.
Planet Iwai also has houses $1,\ \dots,\ M$, and for each $i \ (1 \leq i \leq N)$, Iwaian $i$ lives in house $i$.

Each Iwaian has a value called a rating that represents their programming ability, and the rating of Iwaian $i$ is $A_i$.
Also, Iwaian $i$ considers the Iwaians living in houses $L_i,\ L_i + 1,\ \dots,\ R_i$ to be living in the same hometown.

For each $j \ (1 \leq j \leq M)$, let $B_j$ be the rating of the Iwaian living in house $j$ ($B_j = 0$ if no Iwaian lives in house $j$), and define the genius level of Iwaian $i$ in their hometown as $\sum_{j = L_i}^{R_i} (A_i - B_j)$.
Note that, as described below, the values of $B_j$ and $L_i,\ R_i$ are updated, and the genius levels are updated accordingly.

From now on, $Q$ events occur. In the $k$-th event, Iwaian $X_k$ moves to house $Y_k$ and from then on considers the Iwaians living in houses $U_k,\ U_k + 1,\ \dots,\ V_k$ to be living in the same hometown. At this time, the values of $L_{X_k},\ R_{X_k}$ are updated to $U_{k},\ V_{k}$, respectively.
It is guaranteed that no Iwaian lives in house $Y_k$ immediately before event $k$.

Find the sum of the genius levels of the Iwaians immediately after each event.

Constraints

  • $1 \le N < M \le 2 \times 10^5$
  • $0 \le A_i \le 10^8$
  • $1 \le L_i \le R_i \le M$
  • $1 \le Q \le 2 \times 10^5$
  • $1 \le X_k \le N$
  • $1 \le Y_k \le M$
  • No Iwaian lives in house $Y_k$ immediately before event $k$
  • $1 \le U_k \le V_k \le M$
  • All inputs are integers

Input

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

$N\ M$
$A_1\ L_1\ R_1$
$A_2\ L_2\ R_2$
$\vdots$
$A_N\ L_N\ R_N$
$Q$
$X_1\ Y_1\ U_1\ V_1$
$X_2\ Y_2\ U_2\ V_2$
$\vdots$
$X_Q\ Y_Q\ U_Q\ V_Q$

Output

Output $Q$ lines.
The $k$-th line should contain the sum of the genius levels of the Iwaians immediately after event $k$.

Sample

Sample 1
Input
3 5
200 1 1
600 1 3
1000 1 4
2
3 4 3 5
1 5 4 5
Output
3000
2200

Immediately after event $1$, the genius levels are $0,\ 1000,\ 2000$, respectively, and their sum is $3000$.

Immediately after event $2$, the genius levels are $-800,\ 1200,\ 1800$, respectively, and their sum is $2200$.

Sample 2
Input
5 10
9 1 2
1 1 3
8 2 3
1 1 5
9 4 7
3
1 8 6 8
5 6 6 6
2 5 2 5
Output
31
5
6

Immediately after event $1$, $B$ becomes ${(0,\ 1,\ 8,\ 1,\ 9,\ 0,\ 0,\ 9,\ 0,\ 0)}$.
At this point, the genius levels are $18,\ -6,\ 7,\ -14,\ 26$, respectively, and their sum is $31$.

Immediately after event $2$, $B$ becomes ${(0,\ 1,\ 8,\ 1,\ 0,\ 9,\ 0,\ 9,\ 0,\ 0)}$.
At this point, the genius levels are $9,\ -6,\ 7,\ -5,\ 0$, respectively, and their sum is $5$.

Immediately after event $3$, $B$ becomes ${(0,\ 0,\ 8,\ 1,\ 1,\ 9,\ 0,\ 9,\ 0,\ 0)}$.
At this point, the genius levels are $9,\ -6,\ 8,\ -5,\ 0$, respectively, and their sum is $6$.

Sample 3
Input
2 8
10 1 3
15 4 5
2
1 5 1 3
2 1 6 8
Output
35
60

An Iwaian's set of houses considered to be their hometown may stay the same even after moving, and an Iwaian may also consider houses with which they have no connection at all to be their hometown.

Sample 4
Input
2 200000
9 1 15
181 2 2
3
2 3 5 9
2 181181 1 200000
2 2 2 2
Output
850
36199936
-55

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