2024JAN
Silver
Cowmpetency
线段树可以有效减少思维含量。建议评分：蓝。
设
\[x=\max _{k=1}^i a_k \]\[y=\max _{k=i+1}^{j-1} a_k \]则 FJ 的限制 \((i, j)\) 可以表示为 \(x\ge y\) 并且 \(x<a_j\)。
将所有限制按 \(i\) 从小到大排序后，对每个限制 \((i, j)\) 执行以下流程。
- \(x<y\)。如果 \(1\sim i\) 全部填完了，则无解。否则，为了字典序最小，找到最靠近 \(i\) 的没填的下标 \(pre(i)\)，\(a_{pre(i)}\leftarrow y\)，\(x\leftarrow y\)。
- \(a_j\) 已经填数但 \(a_j\le x\)。一定无解。
- \(a_j\) 没有填数。如果 \(1\sim i\) 全都没有填数，\(a_j\leftarrow 2\)，不然 \(a_j\leftarrow x+1\)。
然后扫描一遍整个 \(a\) 数组，如果 \(a_i>c\) 则无解，如果 \(a_i\) 没有填则 \(a_i\leftarrow 1\)。
最后复查一遍，输出答案。线段树需要支持单点修改、区间查询最大值。
// Title: Cowmpetency
// Source: USACO24JAN Silver
// Author: Jerrywang
#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define ll long long
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
const int N=300010;
using namespace std;
int n, T, C, a[N], pre[N]; pii q[N];
struct node
{
int l, r, x;
} t[N<<4];
#define lc p<<1
#define rc p<<1|1
void build(int p, int l, int r)
{
t[p]={l, r, a[l]};
if(l==r) return;
int m=l+r>>1;
build(lc, l, m), build(rc, m+1, r);
t[p].x=max(t[lc].x, t[rc].x);
}
int query(int p, int l, int r)
{
if(l<=t[p].l && t[p].r<=r) return t[p].x;
int m=t[p].l+t[p].r>>1, res=0;
if(l<=m) res=max(res, query(lc, l, r));
if(r>m) res=max(res, query(rc, l, r));
return res;
}
void modify(int p, int i, int x)
{
if(t[p].l==t[p].r) {t[p].x=x; return;}
int m=t[p].l+t[p].r>>1;
if(i<=m) modify(lc, i, x); else modify(rc, i, x);
t[p].x=max(t[lc].x, t[rc].x);
}
#define err {puts("-1"); return;}
void solve()
{
scanf("%d%d%d", &n, &T, &C);
rep(i, 1, n)
{
scanf("%d", a+i);
if(a[i]) pre[i]=pre[i-1]; else pre[i]=i;
}
build(1, 1, n);
rep(i, 1, T) scanf("%d%d", &q[i].F, &q[i].S);
sort(q+1, q+T+1);
rep(k, 1, T)
{
int i=q[k].F, j=q[k].S;
int x=query(1, 1, i), y=query(1, i+1, j-1);
if(x<y)
{
if(!pre[i]) err
x=a[pre[i]]=y, modify(1, pre[i], y);
}
if(a[j] && a[j]<=x) err
if(!a[j])
a[j]=x?x+1:2, modify(1, j, a[j]);
}
rep(i, 1, n)
{
if(a[i]>C) err
if(!a[i]) a[i]=1, modify(1, i, a[i]);
}
rep(k, 1, T)
{
int i=q[k].F, j=q[k].S;
int x=query(1, 1, i), y=query(1, i+1, j-1);
if(!(x>=y && a[j]>x)) err
}
rep(i, 1, n) printf("%d%c", a[i], " \n"[i==n]);
}
int main()
{
#ifdef Jerrywang
freopen("in.txt", "r", stdin);
#endif
int T; scanf("%d", &T);
while(T--) solve();
return 0;
}