「雅礼集训 2018 Day11」序列

ID: 1637

传统题

1000ms

512MiB

难度: (无)

上传者:

标签>

雅礼集训

2018

题目描述

有一个长度为 $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]$ 的最大值。

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

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