4044. 动态规划

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|$ 最小是多少。