356A

356A - Knight Tournament 【并查集】

题意

题目的意思是说有n个人参加比赛，共有m场比赛，每场比赛给出l,r,x,表示[l,r]区间内的人都被x打败，问最后每个人是被谁打败的，输出那个人的编号，冠军输出0.

思路

可以看出如果这个人已经输掉了，那么之后他就不会被更新了。最暴力的是不使用并查集，直接暴力枚举每一次的lr肯定是会TLE的。
但是使用并查集可以直接跳过一段拥有相同父节点的区间，但是需要额外开一个ans数组记录答案，因为pre[]祖宗数组需要用来合并。

要点

1、自己不能跟自己打
2、使用while(l<=r)枚举区间 但是不可以l++， 必须使用l = p[l]，同时每次记录答案之后需要把p[l] = l + 1; 这样我们一连串的相同父节点的全部合并到一起，并且使用l=p[l]进行跳转到下一个的时候，可以直接跳过一整段区间，大大降低时间复杂度。

代码

#include <iostream>
#include <cstring>
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <sstream>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define int long long
template <typename T>
inline void rd(T &a)
{char c = getchar();T x = 0, f = 1;while (!isdigit(c)){if (c == '-')f = -1;c = getchar();}while (isdigit(c)){x = (x << 1) + (x << 3) + c - '0';c = getchar();}a = f * x;
}int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};const int N = 3e5 + 10;int qmi(int a, int b, int p)
{int res = 1;while (b){if (b & 1){res = res * a % p;}b >>= 1;a = a * a % p;}return res;
}bool cmp(int a, int b)
{return a > b;
}int n, m, l, r, t;
int p[N], ans[N];
int find(int x)
{if (p[x] != x)p[x] = find(p[x]);return p[x];
}void mix(int l, int r, int t)
{while (l <= r){int k = find(l);if (k == l){//被第一次打败ans[l] = t;// 可以直接跳过当前相同操作的块// 防止后边输入相同的区间p[l] = l + 1; //合并条件修改一下}l = p[l];}
}
void solve()
{cin >> n >> m;for (int i = 1; i <= n + 10; i++)p[i] = i;for (int i = 1; i <= m; i++){rd(l), rd(r), rd(t);mix(l, t - 1, t);mix(t + 1, r, t);}for (int i = 1; i <= n; i++){printf("%lld ", ans[i]);}puts("");
}signed main()
{//     int ________________________________________________________________________;//  cin >> ________________________________________________________________________;//  while (________________________________________________________________________--)//     {solve();// }
}