题解：P11024 [COTS 2020] 定序 Redoslijed

注意到每个位置对应的权值只与覆盖这一位置的最后一次操作有关，所以考虑倒序选择操作。

问题变为，如果某个位置被操作一次，则颜色被永久保留，求一组方案。那么，在一个位置被涂色后，可以任意对其做其余操作。

考虑贪心策略。每次选一个当前可以选择的区间，标记这个区间内的所有位置。如果对于某个区间包含的每个位置，要么被标记，要么其颜色与操作对应相同，则这个区间就是可以选择的。

容易得出，这样选择一定不劣，复杂度为

\Theta(nm)

。显然不能通过，需要优化。这里用到了一个 trick。

使用线段树，将每个操作区间拆成 $\log n$ 级别个线段树上的不交子区间，如果这些区间是可以被选择的，那么整个原来的区间也是可以被选择的。

维护每个位置对应的需要涂的颜色，记录线段树每个节点的

val

：

如果这个线段树节点对应区间中，每个位置均被标记，即整个区间剩下的涂色方案可以任意，则 $val$ 为 $0$ 。
如果这个区间中，除了被标记的位置，其余位置需要涂的颜色都为 $c$ ，则 $val$ 为 $c$ 。
否则，需要涂的颜色至少有两种， $val$ 为 $-1$ 。

第一种情况下，这个线段树节点对应的所有操作都是可选的；第二种情况下，颜色为

val

的操作可选；第三种情况下都不能选。

涂色操作是好维护的，直接暴力修改颜色就行，如果遇到

val

是

0

的节点就不用往下搜了。

用一个队列维护一下类似拓扑的过程即可。

注意

b_i

存在

0

，这种情况特判一下，显然所有操作不能覆盖这些位置中的任意一个。

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pii pair<int,int>
#define yes cout<<'Y'<<'E'<<'S'<<endl
#define no cout<<'N'<<'O'<<endl
#define im cout<<-1<<endl
#define debug(x) cerr<<#x<<':'<<x<<endl
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,r,l) for(int i=r;i>=l;i--)
#define couts(x) cout<<setprecision(x)<<fixed
void Ios(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int N=1e6+5;
int n,m,a[N],c[N];
struct opt{
    int l,r,v;
}q[N];
queue<int>que;
namespace sgm{
    #define lc (x<<1)
    #define rc (x<<1|1)
    #define mid ((l+r)>>1)
    int col[N<<2],vis[N<<2];
    vector<int>e[N<<2];
    void addseg(int x,int l,int r,int id){
        if (q[id].l<=l&&r<=q[id].r){
            c[id]++;
            e[x].push_back(id);
            return;
        }
        if (q[id].l<=mid)
            addseg(lc,l,mid,id);
        if (q[id].r>mid)
            addseg(rc,mid+1,r,id);
    }
    void pushup(int x){
        int sb=col[x];
        if (col[lc]==col[rc])
            col[x]=col[lc];
        else if (!col[lc]||!col[rc])
            col[x]=col[lc]+col[rc];
        else col[x]=-1;
        if (vis[x]==0&&col[x]!=-1){
            vis[x]=1;
            for (auto i:e[x])
                if (q[i].v==col[x])
                    if (!--c[i])
                        que.push(i);
        }
        if (vis[x]<=1&&!col[x]){
            vis[x]=2;
            for (auto i:e[x])
                if (q[i].v!=sb)
                    if (!--c[i])
                        que.push(i);
        }
    }
    void build(int x,int l,int r){
        if (l==r){
            col[x]=a[l],vis[x]=1;
            for (auto i:e[x])
                if (q[i].v==col[x])
                    if (!--c[i])
                        que.push(i);
            return;
        }
        build(lc,l,mid);
        build(rc,mid+1,r);
        pushup(x);
    }
    void delseg(int x,int l,int r,int id){
        if (q[id].l<=l&&r<=q[id].r&&!col[x])
            return;
        if (l==r){
            vis[x]=2;
            for (auto i:e[x])
                if (q[i].v!=col[x])
                    if (!--c[i])
                        que.push(i);
            col[x]=0;
            return;
        }
        if (q[id].l<=mid)
            delseg(lc,l,mid,id);
        if (q[id].r>mid)
            delseg(rc,mid+1,r,id);
        pushup(x);
    }
    bool check(int x,int l,int r){
        if (l==r)
            return !col[x];
        return (check(lc,l,mid)&&check(rc,mid+1,r));
    }
}
using namespace sgm;
vector<int>rs;
int pre[N];
void solve(){
    cin>>n>>m;
    fo(i,1,m){
        cin>>q[i].l>>q[i].r>>q[i].v;
        addseg(1,1,n,i);
    }
    fo(i,1,n){
        cin>>a[i];
        pre[i]+=pre[i-1];
        if (!a[i])
            pre[i]++;
    }
    fo(i,1,m)
        if (pre[q[i].r]-pre[q[i].l-1]){
            cout<<"NE\n";
            return;
        }
    build(1,1,n);
    while (que.size()){
        int x=que.front();
        que.pop(),rs.push_back(x);
        delseg(1,1,n,x);
    }
    if (!check(1,1,n)||rs.size()!=m){
        cout<<"NE\n";
        return;
    }
    cout<<"DA\n";
    reverse(rs.begin(),rs.end());
    for (auto i:rs)
        cout<<i<<' ';
    cout<<'\n';
}
signed main(){
    Ios();
    int T=1;
    //cin>>T;
    while (T--)
        solve();
    return 0;
}

题解：P11024 [COTS 2020] 定序 Redoslijed

文章操作

相关推荐

评论

题解：P11024 [COTS 2020] 定序 Redoslijed