正题

题目链接:https://loj.ac/p/6518

---

题目大意

一个长度为$n$的序列$a$，你可以花费$1$的代价让一个数$+1$或者$-1$，给出$m$个限制形如第$k$个数要是区间$[l,r]$的最大/最小值。

求满足所有限制的最小代价

$1\le n\le 5000,1\le a_i\le 10^5$

---

解题思路

一个保序回归问题，我们考虑整体二分。

二分到$mid$时，我们就只考虑每个数选为$mid$还是$mid+1$，选为$mid$的最终$\le mid$，选为$mid+1$的最终$>mid$。

然后是怎么处理一个$mid$，考虑使用$dp$，用$0$表示$mid$，$1$表示$mid+1$，那么序列就会被分成很多$01$交错的段，设$f_{i,0/1}$表示上一段的结尾是$i$，且是$0/1$段。

然后考虑怎么转移，我们将一个条件$[type,l,r,k]$分为$[type,l,k,k]$和$[type,k,r,k]$，然后用线段树维护权值。

对于形如$[type,l,k,k]$的条件，这里设$type=1$，那在我们取$0$段时如果包括了$k$那么必须包括整个$[l,k]$，也就是左端点的选择不能为$(l,k]$，我们可以视为在线段树上去掉一段可选区间。

对于形如$[type,k,r,k]$的条件，同样设$type=1$，那我们在取$0$段时如果包括了$k$那么必须包括整个$[k,r]$，也就是如果$i\in [k,r]$，那么我们上一个转移点$j$的选择必须有$j>k$，可以用单调栈来维护这些限制。

需要注意的点就是线段树的清空需要只清空修改过的点，否则会错。

时间复杂度：$O(a\log a\log n)$

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#define ll long long
using namespace std;
const ll N=5100,M=N<<2,inf=1e9;
ll n,m,a[N],ans,lim[2][N],rim[2][N];
ll p[N],p0[N],p1[N],f[2][N],g[2][N];
stack<ll> d0,d1;
struct SegTree{ll cl[M],p[M],w[M],lazy[M];ll ans,ansp,clt;bool v[M];void Add(ll x){if(!v[x])v[x]=1,cl[++clt]=x;return;}void Downdata(ll x){Add(x);if(!lazy[x])return;Add(x*2);Add(x*2+1);lazy[x*2]+=lazy[x];w[x*2]+=lazy[x];lazy[x*2+1]+=lazy[x];w[x*2+1]+=lazy[x];lazy[x]=0;return;}void Merge(ll x){if(w[x*2]<w[x*2+1])w[x]=w[x*2],p[x]=p[x*2];else w[x]=w[x*2+1],p[x]=p[x*2+1];return;}void Change(ll x,ll L,ll R,ll l,ll r,ll val){if(L==l&&R==r){Add(x);lazy[x]+=val;w[x]+=val;return;}ll mid=(L+R)>>1;Downdata(x);if(r<=mid)Change(x*2,L,mid,l,r,val);else if(l>mid)Change(x*2+1,mid+1,R,l,r,val);else Change(x*2,L,mid,l,mid,val),Change(x*2+1,mid+1,R,mid+1,r,val);Merge(x);return;}void Ins(ll x,ll L,ll R,ll pos,ll val,ll pr){if(L==R){Add(x);if(w[x]>val)w[x]=val,p[x]=pr;return;}ll mid=(L+R)>>1;Downdata(x);if(pos<=mid)Ins(x*2,L,mid,pos,val,pr);else Ins(x*2+1,mid+1,R,pos,val,pr);Merge(x);return;}void Query(ll x,ll L,ll R,ll l,ll r){if(L==l&&R==r){if(w[x]<ans)ans=w[x],ansp=p[x];return;}ll mid=(L+R)>>1;Downdata(x);if(r<=mid)Query(x*2,L,mid,l,r);else if(l>mid)Query(x*2+1,mid+1,R,l,r);else Query(x*2,L,mid,l,mid),Query(x*2+1,mid+1,R,mid+1,r);}void Ask(ll l,ll r){ans=inf;Query(1,1,n,l,r);return;}void Clear(){for(ll i=1;i<=clt;i++){w[cl[i]]=inf;v[cl[i]]=lazy[cl[i]]=0;}clt=0;return;}
}T0,T1;
void solve(ll l,ll r,ll L,ll R){if(l>r)return;if(L==R){for(ll i=l;i<=r;i++)ans+=abs(a[p[i]]-L);return;}T0.Clear();T1.Clear();while(!d0.empty())d0.pop();d0.push(0);while(!d1.empty())d1.pop();d1.push(0);T0.Ins(1,1,n,1,0,0);T1.Ins(1,1,n,1,0,0);ll mid=(L+R)>>1;for(ll i=l;i<=r;i++){f[0][i]=f[1][i]=inf;if(i>l&&lim[0][p[i]]<p[i])T0.Change(1,1,n,lim[0][p[i]]+1,p[i],inf);if(i>l&&lim[1][p[i]]<p[i])T1.Change(1,1,n,lim[1][p[i]]+1,p[i],inf);T1.Change(1,1,n,1,p[i],abs(mid-a[p[i]]));T0.Change(1,1,n,1,p[i],abs(mid+1-a[p[i]]));while(!d0.empty()&&rim[0][d0.top()]<=rim[0][p[i]])d0.pop();while(!d1.empty()&&rim[1][d1.top()]<=rim[1][p[i]])d1.pop();if(i<r){while(!d0.empty()&&rim[0][d0.top()]<p[i+1])d0.pop();while(!d1.empty()&&rim[1][d1.top()]<p[i+1])d1.pop();if(rim[0][p[i]]>=p[i+1])d0.push(p[i]);if(rim[1][p[i]]>=p[i+1])d1.push(p[i]);}else{while(d0.size()>1)d0.pop();while(d1.size()>1)d1.pop();}if(d1.top()<p[i]){T1.Ask(d1.top()+1,p[i]);f[0][i]=T1.ans;g[0][i]=T1.ansp;}if(d0.top()<p[i]){T0.Ask(d0.top()+1,p[i]);f[1][i]=T0.ans;g[1][i]=T0.ansp;}if(i<r){T0.Ins(1,1,n,p[i]+1,f[0][i],i);T1.Ins(1,1,n,p[i]+1,f[1][i],i);}}ll t0=0,t1=0,i=r,k=(f[0][r]<f[1][r])?0:1;while(i){for(ll j=i;j>max(g[k][i],l-1);j--)if(k)p1[++t1]=p[j];else p0[++t0]=p[j];i=g[k][i];k^=1;}for(ll i=1;i<=t0;i++)p[l+i-1]=p0[t0-i+1];for(ll i=1;i<=t1;i++)p[l+t0+i-1]=p1[t1-i+1];solve(l,l+t0-1,L,mid);solve(l+t0,r,mid+1,R);return;
}
signed main()
{freopen("hack.in","r",stdin);scanf("%lld%lld",&n,&m);rim[0][0]=rim[1][0]=inf;for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);memset(lim,0x3f,sizeof(lim));for(ll i=1,t,l,r,k;i<=m;i++){scanf("%lld%lld%lld%lld",&t,&l,&r,&k);lim[t][k]=min(lim[t][k],l);rim[t][k]=max(rim[t][k],r);}for(ll i=1;i<=n;i++)p[i]=i;memset(T0.w,0x3f,sizeof(T0.w));memset(T1.w,0x3f,sizeof(T1.w));solve(1,n,1,1e5);printf("%lld\n",ans);return 0;
}