题解：P11024 [COTS 2020] 定序 Redoslijed

haoertiansuo · 2025-10-21 22:34:24 · 题解

来一个非乱搞的并查集做法。

首先还是考虑倒着维护所有操作，那么相当于每次选择一段所有颜色都相同的区间，然后删除这个区间内的所有元素，直到所有区间都被操作为止。

接下来按左端点从大到小的顺序考虑所有区间，此时相当于依次将元素 c_N 到 c_1 塞进数组开头，然后判断每一个区间是否合法，那么对每个区间 (l,r,c) 一共有两种可能：

区间内的所有元素颜色相同：此时直接删除即可。
区间内存在不同颜色的元素：此时考虑接下来操作的区间对这个区间的影响，因为我们是按左端点从大到小的顺序枚举的区间，因此接下来的区间一定只会影响当前区间的一段前缀，那么如果我们已经确定当前区间 (l,r,c) 内最靠右的不合法元素的位置 p，则当且仅当删除该位置后当前区间才变得合法。

将塞入元素的过程视作压栈，那么删除元素的操作相当于弹出栈中所有位置不大于 r 的元素；而对于需要删除的位置 p，我们可以为每个 p 开一个桶，在删除该元素时顺便处理对应区间的操作。

接下来考虑如何找到位置 p。我们需要对每个区间 (l,r,c) 快速查询三个位置：

与 i 颜色相同的极长连续段的左端点 j。

其中的 i 和 k 可以用并查集轻松维护，而极长连续段可以在每次新加入元素时判断：对于栈顶元素 x 和新加入的元素 y，如果两者颜色相同则将两者对应的联通块合并。

左端点的顺序可以直接桶排，因此时间复杂度由并查集决定，此处为同时使用路径压缩和启发式合并的 O(N\alpha(N))。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=500000;

int i,j,k,n,m,t,a[N+50],p[N+50];
int qr[N+50],cl[N+50];

int it0,s[N+50],cur;
basic_string<int> v[N+50],ev[N+50];
int it3,op[N+50];

struct FA{
    int sz[N+50],fa[N+50],pos[N+50];
    inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    inline int find2(int x){return pos[find(x)];}
    void hb(int x,int y){
        x=find(x); y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y]; fa[y]=x; pos[x]=min(pos[x],pos[y]);
    }
}fa,fa2;

void del(int id){
    static int q[N+50],L,R;
    q[L=R=1]=id;
    while(L<=R){
        id=q[L++];
        op[++it3]=id;
        while(it0&&s[it0]<=qr[id]){
            int k=s[it0--];
            fa.hb(k,cur);
            if(!cur||a[k]==a[cur])fa2.hb(k,cur);
            for(auto j:ev[k])q[++R]=j;
        }
    }
}

void get(int l,int id){
    const int r=qr[id],c=cl[id];
    int i=fa.find2(r);
    if(i<l){
        del(id); return;
    }
    if(a[i]!=c){
        ev[i]+=id; return;
    }
    i=fa.find2(fa2.find2(i)-1);
    if(i<l)del(id);
    else ev[i]+=id;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>j>>k>>t; v[j]+=i;
        p[j]++; p[k+1]--; qr[i]=k; cl[i]=t;
    }
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<=n;i++)if(a[i]){
        fa.pos[i]=fa.fa[i]=i; fa.sz[i]=1;
    }
    k=0;
    for(i=1;i<=n;i++)if(a[i]){
        if(a[k]!=a[i]){
            fa2.pos[i]=i; k=i;
        }
        fa2.fa[i]=k; fa2.sz[k]++;
    }
    for(i=1;i<=n;i++){
        p[i]+=p[i-1];
        if((!p[i])!=(!a[i])){cout<<"NE"; return 0;}
    }
    for(i=n;i>=1;i--){
        if(!a[i]){
            if(it0){cout<<"NE"; return 0;}
            continue;
        }
        cur=fa.find(i-1);
        if(it0&&a[s[it0]]==a[i]){
            fa2.hb(s[it0],i);
        }
        s[++it0]=i;
        for(auto j:v[i])get(i,j);
    }
    if(it3!=m){cout<<"NE"; return 0;}
    cout<<"DA\n";
    for(i=it3;i>=1;i--)cout<<op[i]<<' ';
}