題解-BOI 2004 Sequence

Problem

bzoj & Luogu

題目大意：

給定序列\(\{a_i\}\)，求一個嚴格遞增序列\(\{b_i\}\)，使得\(\sum \bigl |a_i-b_i\bigr|\)最小

Thought

正序：直接對應
逆序：取中位數（證明：“醫院設置”）
最優解一定是分段
每一段臺階式上升
每一段選取中位數
沙漏型左偏樹 合并區間 選取中位數
upd:貌似不需要沙漏型？

Solution

前置技能：小學奧數、可并堆

和上面類似，先不考慮嚴格上升，即先考慮非嚴格上升

序列一定是要分成若干段，每一段的\(b\)值相等，且后一段比前一段大，像臺階一樣（如下圖，是一個\(b(x)\)的偽函數）

先令\(\forall i\in[1,n],a_i=b_i\)，這樣的答案為零，但卻不合法，接下來考慮如何用最小代價使答案合法，考慮對于相鄰兩段數：

設當前前一段取最優值時的\(b\)統一為\(b_1\)，后一段統一為\(b_2\)，變換之后兩者的統一\(b\)值分別變為\(b_1^{'},b_2^{'}\)

如果\(b_1\leq b_2\)，則對于這兩段來說是合法的，無需操作；

如果\(b_1>b_2\)，則表示因為要求\(b_1\leq b_2\)，而現在是\(b_1>b_2\)，要求\(b_1^{'}\leq b_2^{'}\)，考慮到兩段的\(b\)變化得越少越好，即\(\bigl | b_1-b_1^{'}\bigr |,\bigl | b_1-b_1^{'}\bigr |\)取最小，則變換之后\(b_1^{'}=b_2^{'}\)，我們再考慮\(b_1^{'}(b_2^{'})\)的取值，應為這兩段數合在一起的中位數，證明見下方“附”，找中位數可以用線段樹解決，也可以用堆解決（堆解法見TJOI2010中位數），考慮到兩段需要合并，線段樹需要線段樹合并，而堆只需要可并堆即可

如何把相鄰兩段的處理擴展到整個序列呢，鑒于整個\(b\)序列是遞增的，可以用單調棧實現，棧中的比較方式就是上述對于相鄰兩段的處理

現在解除一開始自己設置的限制，將\(a_i\)設為\(a_i-i\)即可將非嚴格上升序列的做法轉移到嚴格上升序列的做法

附：證明：其實就是小學奧數題 對于一段數\(\{c_i\}\)選取\(x\)使得\(\sum \bigl |x-c_i \bigr |\)，最小的\(x\)值的一個取值為\(\{c_i\}\)序列的中位數：

反證法：設原序列有\(n\)個元素，則比\(x\)大/小的數有\(\frac n2\)個，若\(x\)變小或變大，則若越過序列中另一個值時，比\(x\)大/小的數有\(\frac n2±1\)個，統計答案時只會增加\(2\)或不變

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rg registerstruct ios {inline char read(){static const int IN_LEN=1<<18|1;static char buf[IN_LEN],*s,*t;return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;}template <typename _Tp> inline ios & operator >> (_Tp&x){static char c11,boo;for(c11=read(),boo=0;!isdigit(c11);c11=read()){if(c11==-1)return *this;boo|=c11=='-';}for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');boo&&(x=-x);return *this;}
} io;const int N=1001000;
struct Leftist_Tree{int l,r,dis,val;}t[N];
struct node{int l,r,rt,sz,val;node(){}node(const int&L,const int&id){l=L,r=rt=id,sz=1,val=t[id].val;}
}h[N];
int n,top;inline int merge(int u,int v){if(!u||!v)return u|v;if(t[u].val<t[v].val||(t[u].val==t[v].val&&u>v))swap(u,v);int&l=t[u].l,&r=t[u].r;r=merge(r,v);if(t[l].dis<t[r].dis)swap(l,r);t[u].dis=t[r].dis+1;return u;
}inline int del(int u){return merge(t[u].l,t[u].r);}void work(){io>>n;for(rg int i=1;i<=n;++i)io>>t[i].val,t[i].val-=i;h[top=1]=node(1,1);for(rg int i=2;i<=n;++i){int l=h[top].r+1;h[++top]=node(l,i);while(top^1&&h[top-1].val>h[top].val){--top;h[top].rt=merge(h[top].rt,h[top+1].rt);h[top].r=h[top+1].r;h[top].sz+=h[top+1].sz;while(h[top].sz>((h[top].r-h[top].l+2)>>1)){--h[top].sz;h[top].rt=del(h[top].rt);}h[top].val=t[h[top].rt].val;}}return ;
}void Print(){ll Ans=0;for(rg int i=1,p=1;i<=n;++i){if(i>h[p].r)++p;Ans+=abs(h[p].val-t[i].val);}printf("%lld\n",Ans);for(rg int i=1,p=1;i<=n;++i){if(i>h[p].r)++p;printf("%d ",h[p].val+i);}putchar('\n');return ;
}int main(){work();Print();return 0;
}