#6518. 「雅礼集训 2018 Day11」序列

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一个长度为 N 的序列以及 M 个限制,你需要尽量少地修改序列, 使得序列满足限制。输出每个元素变化量之和的最小值。

输入格式

第一行两个数 N, M ,如题所述。

接下来一行 N 个数 a_1, ... ,a_N ,表示序列。

接下来 M 行,每行四个数 {\rm type}, l, r, k 。如果 \rm type = 0 ,表示需要使第 k 个数成为区间 [l, r] 的最小值;如果 \rm type = 1 ,表示需要使第 k 个数成为区间 [l, r] 的最大值。

输出格式

一个数表示每个元素变化量之和的最小值。

样例

样例输入 1

3 2
1 2 3
1 1 2 1
0 1 3 3

样例输出 1

2

数据范围与提示

测试点编号 N \leq M \leq a_i \leq
1 5
2 15 25 100
3
4 100 200
5
6 10^5
7 5000 15000 2
8
9 10^5
10