4044. 动态规划

单点时限: 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$)。

输出格式

对于每个询问,输出一行一个整数,表示答案。

样例

Input
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
Output
2
0
1
0
3
0
1
Input
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
Output
48
0
22
15
0

34 人解决,57 人已尝试。

43 份提交通过,共有 203 份提交。

5.3 EMB 奖励。

创建: 3 年,11 月前.

修改: 3 年,10 月前.

最后提交: 4 月,2 周前.

来源: EOJ Monthly 2021.1

题目标签