Codeforces Round #504 D. Array Restoration

题目描述：有一个长度为\(n\)的序列\(a\)，有\(q\)次操作，第\(i\)次选择一个区间，将区间里的数全部改为\(i\)，序列\(a\)的每个位置至少被改一次。得到最终的序列，然后将序列里的某些位置变成\(0\)，输出一种可能的置零之前的最终序列，或无解。

solution

求出每种数字最长的染色区间，按这个区间染色，记下没出现的数字。染色后如果存在\(0\)联通块，则用没出现的数字从大到小染色（一个联通块一种颜色），不够则无解，最后判断最大的数字\(q\)是否用上了，如果没有，则在原序列中找一个\(0\)变成\(q\)即可，若原序列没有\(0\)，则无解。

时间复杂度：\(O(nlogn)\)

#include <bits/stdc++.h>

using namespace std;

const int maxn=int(2e5)+100;

struct mes

{

	int x, y, v;

};

int n, m;

int a[maxn], ans[maxn];

int BIT[maxn];

int tree[maxn*4], mark[maxn*4];

bool vis[maxn];

vector<int> zero;

pair<int, int> block[maxn];

mes dat;

void read()

{

	scanf("%d%d", &n, &m);

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

}

void insert(int cur, int v)

{

	for (; cur<=m; cur+=(-cur)&cur) BIT[cur]=max(BIT[cur], v);

}

int ask(int cur)

{

	int w=0;

	for (; cur; cur-=(-cur)&cur) w=max(w, BIT[cur]);

	return w;

}

void down(int cur)

{

	tree[cur<<1]=tree[cur<<1 | 1]=mark[cur];

	mark[cur<<1]=mark[cur<<1 | 1]=mark[cur];

	mark[cur]=0;

}

void updata(int cur, int L, int R)

{

	if (dat.x>R || dat.y<L) return;

	if (dat.x<=L && R<=dat.y)

	{

		tree[cur]=dat.v;

		mark[cur]=dat.v;

		return;

	}

	int mid=(L+R)>>1;

	if (mark[cur]) down(cur);

	updata(cur<<1, L, mid);

	updata(cur<<1 | 1, mid+1, R);

}

int get(int cur, int L, int R)

{

	if (L==R) return tree[cur];

	int mid=(L+R)>>1;

	if (mark[cur]) down(cur);

	if (dat.x<=mid) return get(cur<<1, L, mid);

	else return get(cur<<1 | 1, mid+1, R);

}

void solve()

{

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

	{

		if (a[i]==0) continue;

		if (!vis[a[i]]) block[a[i]].first=ask(a[i]-1);

		vis[a[i]]=true;

		insert(a[i], i);

	}

	for (int i=1; i<=m; ++i) BIT[i]=0, vis[i]=false;

	for (int i=n; i; --i)

	{

		if (a[i]==0) continue;

		if (!vis[a[i]]) block[a[i]].second=n-ask(a[i]-1)+1;

		vis[a[i]]=true;

		insert(a[i], n-i+1);

	}

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

		if (!vis[i]) zero.push_back(i);

		else

		{

			dat.x=block[i].first+1;

			dat.y=block[i].second-1;

			dat.v=i;

			updata(1, 1, n);

		}

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

	{

		dat.x=dat.y=i;

		ans[i]=get(1, 1, n);

	}

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

		if (a[i]!=0 && a[i]!=ans[i])

		{

			printf("NO\n");

			return;

		}

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

	{

		if (ans[i]!=0) { ++i; continue; }

		if (zero.size()==0)

		{

			puts("NO");

			return;

		}

		int j=i;

		while (j<=n && a[j]==0) ++j;

		for (int k=i; k<j; ++k) ans[k]=zero.back();

		zero.pop_back();

		i=j;

	}

	if (!zero.empty() && zero.back()==m)

	{

		int idx=0;

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

			if (a[i]==0)

			{

				idx=i;

				break;

			}

		if (idx==0)

		{

			puts("NO");

			return;

		}

		ans[idx]=m;

	}

	puts("YES");

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

}

int main()

{

	read();

	solve();

	return 0;

}