luoguP4331 [BOI2004]Sequence 数字序列

题意

大力猜结论。

首先将所有\(a_i\)变为\(a_i-i\)，之后求不严格递增的\(b_i\)，显然答案不变，最后\(b_i\)加上\(i\)即可。

考虑两种特殊情况：

1.\(a[]\)是递增的：所有\(b_i=a_i\)。

2.\(a[]\)是递减的：显然取\(a[]\)的中位数\(x\)，所有\(b_i=x\)。

现在考虑\(a[]\)一段递增一段递减这样排列，我们可以对每一段递减的\(a_i,a_{i+1}...a_{i+k}\)求出中位数\(c_i\)。

现在我们的\(a[]\)变成了\(c_1,c_2...c_k\)的形式，考虑如果还有\(c_{i+1}<c_i\)，我们就合并\(i,i+1\)两段，求出它们的中位数作为新的一段的值。

合并求中位数可以用左偏树完成，我们只需要对每一段开一个左偏树，只保留段数的一半个数，每次合并后就暴力弹出。

code：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1000010;

int n,top;

ll ans;

ll a[maxn],b[maxn];

struct Heap

{

	#define lc(p) (heap[p].lc)

	#define rc(p) (heap[p].rc)

	#define dis(p) (heap[p].dis)

	int lc,rc,dis;

}heap[maxn];

struct node

{

	int root,l,r,size;

	ll k;

}sta[maxn];

int merge(int x,int y)

{

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

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

	rc(x)=merge(rc(x),y);

	if(dis(rc(x))>dis(lc(x)))swap(lc(x),rc(x));

	dis(x)=dis(rc(x))+1;

	return x;

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]-=i;

	for(int i=1;i<=n;i++)

	{

		sta[++top]=(node){i,i,i,1,a[i]};

		while(top>1&&sta[top].k<sta[top-1].k)

		{

			sta[top-1].root=merge(sta[top-1].root,sta[top].root);

			sta[top-1].size+=sta[top].size;

			sta[top-1].r=sta[top].r;

			while(sta[top-1].size>(sta[top-1].r-sta[top-1].l+1-1)/2+1)

			{

				sta[top-1].size--,sta[top-1].root=merge(lc(sta[top-1].root),rc(sta[top-1].root));

			}

			top--;

			sta[top].k=a[sta[top].root];

		}

	}

	for(int i=1;i<=top;i++)

		for(int j=sta[i].l;j<=sta[i].r;j++)

			b[j]=sta[i].k,ans+=abs(a[j]-b[j]);

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

	for(int i=1;i<=n;i++)printf("%lld ",b[i]+i);

	return 0;

}

巴特西

luoguP4331 [BOI2004]Sequence 数字序列

题意

最新文章

热门文章