## 题目链接：

http://exam.upc.edu.cn/problem.php?id=5791

## 题目：

### 样例输入

5 3
2 4 3
1 3 1
1 5 5

### 样例输出

5 3 1 3 0

## 思路：

注意到被打败之后就再也不能上场了，容易得到：从最后一轮比赛开始，每次用上一轮比赛区间去掉x这个点之后去覆盖这一轮，然后就可以得到答案，用线段树实现的复杂度是$O(nlgn)$。

官方题解给的$O(n)$做法是维护一个长度为n的链表，每次从x点向左向右删除，对于每个将要删除的点将其标记为x即可，这样可以保证每个点只访问一遍，复杂度为$O(n)$。

## 线段树实现：

#include <bits/stdc++.h>
#define lson (u << 1)
#define rson (u << 1 | 1)
using namespace std;
struct Query { int l, r, x; } q[int(1e6) + 7];
int node[int(1e7) + 7], n, m;
bool lazy[int(1e7) + 7];
void pushdown(int u) {
node[lson] = node[rson] = node[u];
lazy[lson] = lazy[rson] = true;
lazy[u] = false;
}
void update(int b, int e, int val, int u = 1, int l = 1, int r = n) {
if (b <= l && r <= e) {
node[u] = val;
lazy[u] = true;
return ;
}
int mid = (l + r) >> 1;
if (lazy[u]) pushdown(u);
if (b <= mid) update(b, e, val, lson, l, mid);
if (e > mid) update(b, e, val, rson, mid + 1, r);
}
int query(int aim, int u = 1, int l = 1, int r = n) {
if (l == r) return node[u];
int mid = (l + r) >> 1;
if (lazy[u]) pushdown(u);
if (aim <= mid) return query(aim, lson, l, mid);
return query(aim, rson, mid + 1, r);
}
int main() {
//    freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].x);
if (q[i].l > q[i].r) std::swap(q[i].l, q[i].r);
}
for (int i = m; i >= 1; i--) {
if (q[i].l < q[i].x) update(q[i].l, q[i].x - 1, q[i].x);
if (q[i].x < q[i].r) update(q[i].x + 1, q[i].r, q[i].x);
}
for (int i = 1; i <= n; i++) printf("%d%c", query(i), i == n ? '\n' : ' ');
return 0;
}


## 链表实现：

#include <bits/stdc++.h>
const int maxn = int(5e6) + 7;
struct { int l, r; } node[maxn];
void remove(int cur) {
node[node[cur].l].r = node[cur].r;
node[node[cur].r].l = node[cur].l;
}
int ans[maxn], n, m, l, r, x, cur;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) node[i] = {i - 1, i + 1};
while (m--) {
scanf("%d%d%d", &l, &r, &x);
cur = node[x].l;
while (cur >= l) {
ans[cur] = x;
remove(cur);
cur = node[cur].l;
}
cur = node[x].r;
while (cur <= r) {
ans[cur] = x;
remove(cur);
cur = node[cur].r;
}
}
for (int i = 1; i <= n; i++) printf("%d%c", ans[i], i == n ? '\n' : ' ');
return 0;
}