34 人解决,57 人已尝试。
43 份提交通过,共有 203 份提交。
5.3 EMB 奖励。
单点时限: 2.0 sec
内存限制: 512 MB
Cuber QQ 在研究动态规划时收获了快乐。他想把这份快乐通过这题传达给你。
Cuber 有 $x_1, x_2, \cdots, x_n$ 这 $n$ 个变量。其中,$x_i$ 可以是区间 $[l_i, r_i]$ 内的任何整数。
现在,Cuber 会进行 $m$ 次操作,每次操作都是下面两种之一:
M k u v
:Cuber 将 $[l_k, r_k]$ 改为 $[u, v]$;Q p q
:Cuber 让你回答若 $x_i$ 在范围内任意取值,$|x_p - x_{p + 1}| + |x_{p + 1} - x_{p + 2}| + \cdots + |x_{q - 1} - x_q|$ 最小是多少。第一行两个整数 $n, m$($1 \le n \le 10^5, 1 \le m \le 2 \times 10^5$)。
接下来 $n$ 行,每行两个整数 $l_i, r_i$($1 \le l_i \le r_i \le 10^9$)。
接下来 $m$ 行,每行一个操作。操作要么形如 M k u v
($1 \le k \le n, 1 \le u \le v \le 10^9$),要么形如 Q p q
($1 \le p \le q \le n$)。
对于每个询问,输出一行一个整数,表示答案。
5 9 1 2 3 6 4 5 2 5 1 3 Q 1 3 Q 2 4 Q 3 5 Q 1 1 Q 1 5 M 1 2 4 Q 1 4 M 3 1 2 Q 1 5
2 0 1 0 3 0 1
5 10 19 50 13 58 35 94 32 36 22 76 M 4 98 98 Q 1 4 M 3 55 57 Q 1 1 M 3 65 82 Q 4 5 M 4 37 41 Q 1 3 M 2 39 83 Q 4 5
48 0 22 15 0
34 人解决,57 人已尝试。
43 份提交通过,共有 203 份提交。
5.3 EMB 奖励。