Codeforces Round #504 D. Array Restoration

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;
}
上一篇:如何使用Ubuntu中的avdManager命令行为“System-Image;Androd-27;GoogleAPI;x86”创建一个AVD?


下一篇:bootbox.js官方文档中文版