题解： Knight Tournament
n<=3e5 意味着只能写复杂度为nlogn的代码 思路一：

对于一个区间操作，其实每一个节点只需要找到是谁打败了它，接下来这个节点就没用了，我们可以维护一个set来表示目前还存活的人。被打败的人就踢出set。

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl "\n"
const int maxn=3e5+5;
#define PII pair<int,int>
const double EPS = 1e-12;
int ans[maxn],d[maxn];
int f[maxn];
int getRoot(int x) {
	//i节点当前的父节点是谁
	return x == f[x] ? x : f[x] = getRoot(f[x]);
}
void merge(int x,int y) {
	//两个集合合并
	int fx=getRoot(x),fy=getRoot(y);
	if(fx!=fy) {
		f[fx]=fy;
	}

}
signed main() {
//	ios::sync_with_stdio(false);
//	cin.tie(0),cout.tie(0);
	int n,q;
	cin>>n>>q;
	for(int i=1; i<=n; i++) {
		f[i]=0;
		//f[i]的含义为 i被f[i]打败 
	}
	set<int>s;
	for(int i=1; i<=n; i++) {
		s.insert(i);
		//当前所有人都存活 
	}
	while(q--) {
		int l,r,z;
		cin>>l>>r>>z;
		set<int>::iterator it;
		vector<int>num;
		for(it=s.lower_bound(l); it!=s.end(); it++) {
			if(*it==z)continue;
			if(*it>r)break;
			//找到区间[L,R]之间存活的人 设置谁打败了他 
			f[*it]=z;
			//维护一个vector 记录[L,R]存活了哪些人 等会剔除 
			num.push_back(*it);
		}
		//下面剔除掉失败的人 
		for(auto it=num.begin(); it!=num.end(); it++) {
			s.erase(*it);
		}
//		for(int i=1; i<=n; i++) {
//			cout<<f[i]<<" ";
//		}
//		cout<<endl;
	}
	for(int i=1; i<=n; i++) {
		cout<<f[i]<<" ";
	}
	cout<<endl;

}

思路二：

可以用并查集的路径压缩优化找下一个人没被击败过的位置，这样子就不会超时了，

初始化并查集数组 fa[i]=i ，代表自己没被击败过，被击败后指向下一个人

#include <bits/stdc++.h>

using namespace std;
const int N = 3e5 + 5;

int n, m, fa[N];
int ans[N];
int getRoot(int x) {
    return x == fa[x] ? x : fa[x] = getRoot(fa[x]);
}
void modify(int l, int r, int x) {
    while(l <= r) {
        if(getRoot(l) == l) {
            ans[l] = x;
            fa[l] = l + 1;
        }
        l = fa[l];
    }
}
void solve() {
    cin >> n >> m;

    for(int i = 1; i <= n + 1; i ++) fa[i] = i;
    while(m --) {
        int l, r, x;
        cin >> l >> r >> x;
        modify(l, x - 1, x);
        modify(x + 1, r ,x);
    }
    for(int i = 1; i <= n; i ++)
        cout << ans[i] << " ";
}
main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int _ = 1;
    // cin >> _;
    while(_ --) {
        solve();
    }
    return 0;
}

[银河英雄传说] 带权并查集

询问同一列内 i 和 j之间有几艘船，可以求 i 和 j到队列头有多少艘船，然后减一下就出来了， 所以这里的带权是每个点到它的根的距离，用 d 数组表示，合并两个队列计算 d 时，需要知道两个队列的长度，用 len 数组表示，并查集合并的时候知道两个队列的长度可以计算出合并后的长度，d 数组的话可以算出两个队头的相对距离，计算点到根的距离时，递归到根后回溯根据点和点之间的相对距离就可以算出点到根的距离，路径压缩可以减少下次找的时间。

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;

int fa[N];
int d[N], len[N];
int getRoot(int x) {
    if(x != fa[x]) {
        int root = getRoot(fa[x]);
        d[x] += d[fa[x]];
        fa[x] = root;
    }
    return fa[x];
}
void solve() {
    int t;
    cin >> t;
    for(int i = 1; i <= 3e4; i ++) fa[i] = i;
    while(t --) {
        string op;
        int x, y;
        cin >> op >> x >> y;


        int fx = getRoot(x), fy = getRoot(y);
        if(op == "M") {
            if(fx != fy) {
                fa[fx] = fy;
                d[fx] = len[fy] + 1;
                len[fy] += len[fx] + 1;
            }
        } else {
            if(fx == fy) {
                cout << max(0, abs(d[y] - d[x]) - 1) << '\n';
            } else {
                cout << "-1" << '\n';
            }
        }
    }
}
main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int _ = 1;
    // cin >> _;
    while(_ --) {
        solve();
    }
    return 0;
}

DZY Loves Chemistry

稍微画图观察可以发现，假设一个联通图里面有n个点。最多发生n-1次化学反应

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl "\n"
const int maxn=3e5+5;
#define PII pair<int,int>
const double EPS = 1e-12;
int f[maxn];
int getRoot(int x) {
	//i节点当前的父节点是谁
	return x == f[x] ? x : f[x] = getRoot(f[x]);
}
void merge(int x,int y) {
	//两个集合合并
	int fx=getRoot(x),fy=getRoot(y);
	if(fx!=fy) {
		f[fx]=fy;
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		merge(x,y);
	}
	int ans=1;
	map<int,int>mp;
	for(int i=1;i<=n;i++){
		int fx=getRoot(i);
		mp[fx]++;
	}
	for(auto it=mp.begin();it!=mp.end();it++){
		while(it->second!=1){
			ans*=2;
			it->second--;
		}
	}
	cout<<ans<<endl;
}