周歪歪的序列 - 题目 - Universal Online Judge

周歪歪有一个长度为$n$的序列，但$syy$觉得这个序列很不美观

$syy$认为，只有序列满足$m$个要求时它才是美观的，要求要么是一个位置是一个区间最小值，要么为一个位置是一个区间最大值（注意最小值和最大值不严格）

周歪歪很无奈，只能挥动它的大锤修改序列，每挥动一次大锤，可以将一个数增加或减小一

挥动大锤不是一个容易的事，请你帮助周歪歪计算最小的挥动次数使得序列满足$syy$的要求

第一行两个整数$n,m$。

第二行$n$个正整数表示$a_i$

接下来$m$行，每行$4$个整数$ty,l,r,pos$，如果$ty=0$表示第$pos$个数是$[l,r]$中数的最小值，否则表示最大值，满足$1\le l \le pos \le r\le n$

一行一个数字，表示最小挥动大锤次数。

$Subtask 1[20pts]: n\le 15,m\le 25,a_i \le 100$

$Subtask 2[20pts]: n\le 100,m\le 200,a_i \le 100$

$Subtask 3[10pts]: n\le 100,m\le 200,a_i \le 10^5$

$Subtask 4[10pts]: n\le 5000,m\le 15000,a_i \le 2$

$Subtask 5[10pts]: n\le 5000,m\le 15000,a_i \le 10^5$

$Subtask 6[20pts]: n\le 100000,m\le 500000,a_i \le 2$

$Subtask 7[10pts]: n\le 100000,m\le 500000,a_i \le 10^4$

时间限制：$1s$

空间限制：$512MB$

Universal Online Judge