CF356A

Nukumizu_Kaju · 2022-03-18 11:22:03 · 题解

和白雪皑皑重题了，这题还是弱化版，建议白雪皑皑也给整成紫的

比较显然，一个骑士只会被打烂一次，那我们就给这个序列开一个并查集， find(i) 表示第 i 个骑士之后第一个没有被打烂的骑士的编号是多少，最开始的时候 find(i)=i 。

如果第 i 个骑士被打烂了，显然， find(i)=find(i+1) 。

这题和白雪皑皑唯一的区别是，骑士不会被自己打烂，所以特判一下，打自己时跳过去就行了。

因为一个骑士顶了天被打烂一次，所以时间复杂度是 O(n) 的。(但是其实并查集的时间复杂度是反阿克曼函数，只不过那玩意太小了，可以忽略不计)

代码如下:

#include <bits/stdc++.h>
using namespace std;
int n, m, p, q;
int father[1000005];
int sl[1000005];
int find(int x) {
  if (father[x] == x) {
    return x;
  }
  return father[x] = find(father[x]);
}
int main() {
  scanf("%d%d", & n,& m);
  for (int i = 1; i <= n + 2; i++) {
    father[i] = i;
  }
  for (int i = 1; i <= m; i++) {
    int lt;
    int rt;
    int color;
    scanf("%d%d%d", &lt, &rt, &color);
    if (lt > rt) {
      swap(lt, rt);
    }
    for (int j = lt; j <= rt;) {
      if (!sl[j]) {
        if (color == j) {//不能打自己
          j++;
          continue;
        }
        father[j] = j + 1;//把别人打烂
        sl[j] = color;//别人是我打烂的
      }
      j = find(j);//找到右边第一个还没被打烂的
    }
  }
  for (int i = 1; i <= n; i++) {
    printf("%d ", sl[i]);
  }
  return 0;
}