P10134 [USACO24JAN] Cowmpetency S

Genius_Star · 2024-02-05 16:05:05 · 题解

题意：

给定 n 组约定条件 (l_i,r_i)，需要满足 l_i + 1 \sim n 中第一个大于 \max\limits_{i=1}^{l_i} \Big( a_i \Big) 的位置在 r_i。

目前 a 中有些值确定，有些值待定，你需要找到符合条件且字典序最小的序列 a。

思路：

感觉下位蓝？细节有点儿多。

先对于第 i 数找到前一个不确定值的位置 last_i。

然后将约束条件按照 l_i 从小到大排序，对于每组约束条件，记：

如果 Max_2>Max_1 了，说明 a_{r_i} 肯定不是第一个大于 Max_1 的数，此时有两种情况：

如果 last_{l_i} 是存在的，即我们可以修改 [1,l_i] 范围内的值，因为要使得字典序最小，可以令 a_{last_{l_i}} \to Max_2，那么现在 Max_1 也变化为 Max_2。
否则，这个区间是固定的了，没有满足要求的编排方案，输出 -1。

之后再次判断 a_{r_i} 的值，分三种情况：

如果 a_{r_i} 的值是确定的，判断是否满足 a_{r_i}>Max_1 这个条件。
如果是不确定的，且 Max_1=0，表示 [1,l_i] 也都不确定，则 a_{r_i} 至少应该是 2。（因为肯定要留 1 在前面的位置）
如果是不确定的，且 Max_1 \ne 0，则要使得字典序最小，令 a_{r_i} \to Max_1 + 1。

经过上面的判断之后，对于当前还没有确定下来的值，因为要使得字典序最小，直接令其为 1 即可。

注意，最后为了保险起见，我们可以再按照约束条件检查一遍；且 a 中每一个数都应该 \le c。

上面需要求区间最大值，且支持单点修改，可以使用线段树进行维护。

时间复杂度为 O(T \times N \log N)。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll N=100100;
inline ll read(){
    ll x=0,f=1;
    char a=getchar();
    while(a<'0'||a>'9'){
        if(a=='-')
          f=-1;
        a=getchar();
    }
    while(a>='0'&&a<='9'){
        x=(x<<1)+(x<<3)+(a^48);
        a=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
struct Node{
    ll l,r;
    ll Max;
}X[N<<2];
struct St{
    ll l,r;
    bool operator<(const St&rhs)const{
        return l<rhs.l;
    }
}s[N];
ll T,n,m,c,x,y;
ll a[N],last[N];
void pushup(ll c){
    X[c].Max=max(X[c<<1].Max,X[c<<1|1].Max);
}
void build(ll c,ll l,ll r){
    X[c].l=l,X[c].r=r;
    if(l==r){
        X[c].Max=a[l];
        return ;
    }
    ll mid=(l+r)>>1;
    build(c<<1,l,mid);
    build(c<<1|1,mid+1,r);
    pushup(c);
}
void add(ll c,ll i,ll v){
    if(X[c].l==i&&i==X[c].r){
        X[c].Max=v;
        return ;
    }
    ll mid=(X[c].l+X[c].r)>>1;
    if(i<=mid)
      add(c<<1,i,v);
    else
      add(c<<1|1,i,v);
    pushup(c);
}
ll qureyMax(ll c,ll l,ll r){
    if(l>r)
      return 0;
    if(X[c].l==l&&r==X[c].r)
      return X[c].Max;
    ll mid=(X[c].l+X[c].r)>>1;
    if(r<=mid)
      return qureyMax(c<<1,l,r);
    else if(l>mid)
      return qureyMax(c<<1|1,l,r);
    else
      return max(qureyMax(c<<1,l,mid),qureyMax(c<<1|1,mid+1,r));
}
void solve(){
    n=read(),m=read(),c=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(!a[i])
          last[i]=i;
        else
          last[i]=last[i-1];
    }
    for(int i=1;i<=m;i++)
      s[i]={read(),read()};
    sort(s+1,s+m+1);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        ll l=s[i].l,r=s[i].r;
        ll Max1=max(1ll,qureyMax(1,1,l)),Max2=qureyMax(1,l+1,r-1);
        if(Max2>Max1){
            if(!last[l]){
                puts("-1");
                return ;
            }
            a[last[l]]=Max2;
            add(1,last[l],Max2);
            Max1=Max2;
        }
        if(a[r]!=0){
            if(Max1>=a[r]){
                puts("-1");
                return ;
            }
        }
        else{
            if(!Max1){
                a[r]=2;
                add(1,r,2);
            }
            else{
                a[r]=Max1+1;
                add(1,r,Max1+1);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(!a[i])
          a[i]=1;
        if(a[i]>c){
            puts("-1");
            return ;
        }
    }
    for(int i=1;i<=m;i++){
        if(qureyMax(1,1,s[i].l)>=a[s[i].r]||qureyMax(1,s[i].l+1,s[i].r-1)>=a[s[i].r]){
            puts("-1");
            return;
        }       
    }
    for(int i=1;i<=n;i++){
        write(a[i]);
        if(i!=n)
          putchar(' ');
    }
    putchar('\n');
}
int main(){
//  freopen("A.in","r",stdin);
    T=read();
    while(T--)
      solve();
    return 0;
}