luogu 4331 [BalticOI 2004]Sequence 数字序列

LINK:数字序列

这是一道论文题 我去看了一眼论文鸽的论文。

发现讲的还算能懂。可并堆的操作也讲的比较清晰。

对于这道题首先有一个小trick 我们给a数组全部减去其对应的下标这样我们求出来的b数组就可以不需要满足严格递增的条件了只要不降即可。

这样更有利于我们继续的思考 此时对于a序列单调不降的时候 显然a序列本身即是答案。

而对于a序列单调不升的时候 根据小学奥数 可以的出此时b为序列的中位数最优。

具体证明是这样的b序列完全小于a序列 b序列完全大于a序列 b序列先小于后大于a序列。

显然第三种情况代价<=前两种代价。

考虑在完成交叉的时候 \(b_k==a_k\)时此时最优。

所以可以证明 此时至少有一个位置 \(a_k==b_k\) 此时考虑k左边元素\(a_{k-1}\geq a_k\)

\(b_{k-1}\leq b_k\) 可以发现此时\(b_{k-1}\)取\(b_k\)最优。

而k右边元素同理。

当我们把k的位置移到最中间的时候可以发现是最优的 所以上述小学奥数成立。

依照这个思路我们可以发现 把序列分段 让每一段单调的是最优的即可。

假设现在有两端 其序列的最优值分别为x1 x2 x1>=x2 我们考虑此时将序列进行合并。

因为这两段不可能同时最优了 所以将其当成一段来解决。

他们同时也不满足不降 所以 按照第二种策略解决即可。

所以这道题变成了合并两个区间的数字并找出中位数 可以采用主席树 当然更快的还是可并堆。

const int MAXN=1000010;

int n,top;

int c[MAXN][2],d[MAXN],a[MAXN],b[MAXN];

ll ans;

struct wy

{

	int l,r,rt;

	int v,sz;

}s[MAXN];

inline int merge(int x,int y)

{

	if(!x||!y)return x|y;

	if(a[x]<a[y])swap(x,y);

	c[x][1]=merge(c[x][1],y);

	if(d[c[x][1]]>d[c[x][0]])swap(c[x][0],c[x][1]);

	d[x]=d[c[x][1]]+1;

	return x;

}

int main()

{

	freopen("1.in","r",stdin);

	get(n);rep(1,n,i)get(a[i]),a[i]-=i;

	rep(1,n,i)

	{

		s[++top]=(wy){i,i,i,a[i],1};

		while(top>1&&s[top].v<s[top-1].v)

		{

			s[top-1].rt=merge(s[top].rt,s[top-1].rt);

			s[top-1].r=s[top].r;s[top-1].sz+=s[top].sz;

			--top;int sz=s[top].r-s[top].l+1;

			while(s[top].sz>sz/2+(sz&1))

			{

				s[top].rt=merge(c[s[top].rt][0],c[s[top].rt][1]);

				--s[top].sz;

			}

			s[top].v=a[s[top].rt];

		}

	}

	int flag=1;

	rep(1,n,i)

	{

		if(s[flag].r<i)++flag;

		ans+=abs(a[i]-a[s[flag].rt]);

		b[i]=a[s[flag].rt];

	}

	printf("%lld\n",ans);

	rep(1,n,i)printf("%d ",b[i]+i);

	return 0;

}

luogu 4331 [BalticOI 2004]Sequence 数字序列的相关教程结束。