先把是否有色的约束处理掉。累一个前缀和，对每个位置判一下即可。
考察区间覆盖的性质，显然最后一个操作的区间内的颜色一定与其覆盖的颜色相同。考虑从后往前确定操作的顺序，一个操作只要满足这个条件就可以作为当前的最后一个操作，如果有多个满足条件的操作，随便取一个都合法。
考虑维护满足条件的操作，每次取出一个操作将其区间内的位置标记掉，将所有从不合法变为合法的操作加入集合。
如何快速求出从不合法变为合法的操作？有个经典的套路就是用线段树将每个区间拆成若干段，对每个操作记录不合法的段数 \(\text{cnt}_i\)。每次区间标记在线段树上递归找到所有需要标记的点，因为每个点只会被标记一次，所以时间复杂度是一个 \(\log\)。
观察什么时候需要将一些操作的 \(\text{cnt}\) 减一。发现当线段树上的一个点对应区间内的颜色数从 \(>1\) 变成 \(1\) 时，需要将含有这个点且颜色与剩下的这个颜色相同的操作的 \(\text{cnt}\) 减一，对每个点记录颜色 \(\min,\max\) 即可判断。当一个点被完全标记掉时将包含它的剩下操作的 \(\text{cnt}\) 减一。\(\text{cnt}\) 减到 \(0\) 时加入集合即可。
然后就做完了，时间复杂度 \(\mathcal O((N+M) \log N)\)，参考代码：
#include<bits/stdc++.h>
#define mxn 500003
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rept(i,a,b) for(int i=(a);i<(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
inline int read(){
int x=0;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
struct node{
int l,r,c;
}d[mxn];
int n,m,tt,tot,a[mxn],c[mxn],ct[mxn],st[mxn],ans[mxn],t1[mxn<<2],t2[mxn<<2],cl[mxn<<2];
vector<int>t[mxn<<2];
bool b[mxn<<2],b1[mxn<<2];
void build(int p,int l,int r){
if(l==r){
if(a[l])t1[p]=t2[p]=a[l],b1[p]=1;
else t1[p]=1e9,t2[p]=-1e9,b[p]=1;
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
t1[p]=min(t1[p<<1],t1[p<<1|1]);
t2[p]=max(t2[p<<1],t2[p<<1|1]);
b1[p]=t1[p]==t2[p],b[p]=t2[p]<0;
}
void add(int p,int l,int r,int x,int L,int R){
if(l<=L&&R<=r){
if(b1[p]&&t1[p]==d[x].c)return;
ct[x]++,t[p].pb(x);
return;
}
int mid=(L+R)>>1;
if(l<=mid)add(p<<1,l,r,x,L,mid);
if(r>mid)add(p<<1|1,l,r,x,mid+1,R);
}
void upd(int p,int l,int r,int L,int R){
if(b[p])return;
if(L==R){
b[p]=1,t1[p]=1e9,t2[p]=-1e9;
for(int i:t[p])if(d[i].c!=cl[p]){
if(!(--ct[i]))st[++tot]=i;
}
return;
}
int mid=(L+R)>>1;
if(l<=mid)upd(p<<1,l,r,L,mid);
if(r>mid)upd(p<<1|1,l,r,mid+1,R);
t1[p]=min(t1[p<<1],t1[p<<1|1]);
t2[p]=max(t2[p<<1],t2[p<<1|1]);
if(t2[p]<0&&!b[p]){
b[p]=1;
for(int i:t[p])if(d[i].c!=cl[p]){
if(!(--ct[i]))st[++tot]=i;
}
}else if(t1[p]==t2[p]&&!b1[p]){
cl[p]=t1[p],b1[p]=1;
for(int i:t[p])if(d[i].c==cl[p]){
if(!(--ct[i]))st[++tot]=i;
}
}
}
signed main(){
n=read(),m=read();
rep(i,1,m)d[i].l=read(),d[i].r=read(),d[i].c=read(),c[d[i].l]++,c[d[i].r+1]--;
rep(i,1,n){
a[i]=read();
c[i]+=c[i-1];
if((c[i]&&!a[i])||(!c[i]&&a[i])){
puts("NE");
return 0;
}
}
build(1,1,n);
rep(i,1,m)add(1,d[i].l,d[i].r,i,1,n);
rep(i,1,m)if(!ct[i])st[++tot]=i;
while(tot){
int x=st[tot--];ans[++tt]=x;
upd(1,d[x].l,d[x].r,1,n);
}
if(tt!=m)puts("NE");
else{
puts("DA");
drep(i,m,1)cout<<ans[i]<<" ";
}
return 0;
}