题解：P11024 [COTS 2020] 定序 Redoslijed

· · 题解

有意思的题。

正着考虑非常困难！这样我没法知道该用哪次染色操作。但是如果我们考虑最后一次染色 (l,r,c)，假装有解，那么最终的 b_l\sim b_r 的颜色必须是 c。

类似地从后往前考虑，我们能做某次染色 (l,r,c) 当且仅当区间 b_l\sim b_r 中颜色与 c 不同的位置在之后又被正确地染过了，因为只有这些位置是可以任意染色的，不管染的对不对之后都会覆盖掉。

并且，可以发现，如果有多个操作可以同时放在这个位置，那么任选一个操作不会使有解的情况变成无解，因为已经被染过的位置只会越来越多，可以用的操作也会越来越多，原本可以用的操作还是可以用。

那么现在我们就得到了这样一个构造方法：从最后一次操作往前考虑，每次找到一个操作 (l,r,c) 使得 b_l\sim b_r 的每个位置要么是 c，要么被标记了，如果没有合法的操作直接报告无解。把这个操作加到答案序列里，然后把 b_l\sim b_r 全部打上标记，也就是这些位置在之后会被覆盖。

显然这样的构造一定合法，并且只要有解，一定能通过这样的构造找到一个解。

但是这怎么和暴力同分！我们发现这个过程和拓扑排序有点像，不如看看能不能快速维护有哪些合法的操作 (l,r,c)。这是一个常见的套路：把 (l,r,c) 拆成线段树上的若干个区间。

我们发现，对于线段树上的一个区间 [L,R]，如果这个区间里有两个颜色不同的位置都没标记，那包含 [L,R] 的操作肯定都不合法。如果这个区间里只有一个颜色的位置没标记，那么只有同一个颜色的操作可能合法。

如果一个操作 (l,r,c) 拆出来的所有区间都合法了，那这个操作也就合法了。因此，我们把每个操作挂到线段树上，类似拓扑排序记录每个操作拆成了多少个区间，记为 cnt_i，用一个队列记录未使用的合法操作，然后在线段树上维护以下过程：

这样一来，每个操作被拆成 \log N 个区间，线段树上的每个区间至多遍历两次挂在上面的操作，总时间复杂度 O((N+M)\log N)。

代码并不难写。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,xl[500005],xr[500005],c[500005],b[500005];
int d[2000005],cnt[500005];
int vis[2000005],cl[2000005];
vector<int> v[2000005];
queue<int> q;
int ans[500005],pos;
void insert(int p,int l,int r,int id)
{
    if(xl[id] <= l && r <= xr[id])
    {
        v[p].push_back(id),cnt[id]++;
        return;
    }
    int mid = l + r >> 1;
    if(xl[id] <= mid)
        insert(p << 1,l,mid,id);
    if(xr[id] > mid)
        insert(p << 1 | 1,mid + 1,r,id);
}
void update(int p)
{
    if(d[p] == -2 && vis[p] < 2)
    {
        vis[p] = 2;
        for(auto i : v[p])
            if(cl[p] != c[i])
            {
                if(!(--cnt[i]))
                    q.push(i);
            }
    }
    if(d[p] != -1 && vis[p] < 1)
    {
        cl[p] = d[p],vis[p] = 1;
        for(auto i : v[p])
            if(cl[p] == c[i])
            {
                if(!(--cnt[i]))
                    q.push(i);
            }
    }
}
void pushup(int p)
{
    if(d[p << 1] == -1 || d[p << 1 | 1] == -1)
        d[p] = -1;
    else if(d[p << 1] == -2)
        d[p] = d[p << 1 | 1];
    else if(d[p << 1 | 1] == -2)
        d[p] = d[p << 1];
    else
        d[p] = (d[p << 1] == d[p << 1 | 1] ? d[p << 1] : -1);
    update(p);
}
void build(int p,int l,int r)
{
    if(l == r)
    {
        d[p] = b[l];
        update(p);
        return;
    }
    int mid = l + r >> 1;
    build(p << 1,l,mid);
    build(p << 1 | 1,mid + 1,r);
    pushup(p);
}
void modify(int p,int l,int r,int x,int y)
{
    if(x <= l && r <= y && d[p] == -2)
        return;
    if(l == r)
    {
        d[p] = -2;
        update(p);
        return;
    }
    int mid = l + r >> 1;
    if(x <= mid)
        modify(p << 1,l,mid,x,y);
    if(y > mid)
        modify(p << 1 | 1,mid + 1,r,x,y);
    pushup(p);
}
int query(int p,int l,int r,int x)
{
    if(l == r) return d[p];
    int mid = l + r >> 1;
    if(x <= mid) return query(p << 1,l,mid,x);
    return query(p << 1 | 1,mid + 1,r,x);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++)
        scanf("%d%d%d",&xl[i],&xr[i],&c[i]),insert(1,1,n,i);
    for(int i = 1;i <= n;i++)
        scanf("%d",&b[i]);
    build(1,1,n);
    while(!q.empty())
    {
        int tmp = q.front();
        q.pop();
        ans[++pos] = tmp;
        modify(1,1,n,xl[tmp],xr[tmp]);
    }
    for(int i = 1;i <= n;i++)
        if(query(1,1,n,i) != -2 && query(1,1,n,i) != 0)
        {
            printf("NE\n");
            return 0;
        }
    if(pos != m)
        printf("NE\n");
    else
    {
        printf("DA\n");
        for(int i = m;i >= 1;i--)
            printf("%d%c",ans[i]," \n"[i == 1]);
    }
    return 0;
}