自动搬运

查看原文

来自洛谷，原作者为

	VainSylphid 美しい音色で世界が鳴った

搬运于2025-08-24 23:03:35，当前版本为作者最后更新于2024-11-06 22:16:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

有意思的题。

正着考虑非常困难！这样我没法知道该用哪次染色操作。但是如果我们考虑最后一次染色 $(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$，用一个队列记录未使用的合法操作，然后在线段树上维护以下过程：

• 取出队头的一个操作 $(l,r,c)$，如果没有这样的操作就报告无解。

• 把 $b_l\sim b_r$ 全部改成一个你喜欢的标记，比如 $-1$。因为不能用懒标记，所以要暴力递归找到区间中所有没标记过的位置。

• pushup 的时候，如果当前区间首次只剩下一种没标记的颜色，那么把这个区间上挂着的相同颜色的操作的 $cnt$ 减一。

• 如果当前区间全部被标记了，那么把这个区间上挂着的所有操作的 $cnt$ 减一，但是之前就已经同色的那些区间不能减，需要记录下首次只剩下一种没标记的颜色编号，这次减的时候就跳过了。

• 如果一个操作的 $cnt$ 被减到 $0$，让它入队。

这样一来，每个操作被拆成 $\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;
}