【并查集+离散化】POJ2528
本题很多都是用的线段树，但线段树客观来说代码长，容易写错，所以并查集其实更好
先把操作离线，由于只有靠后的操作才会对区间产生影响，所以说每个点最后一次覆盖的才是最后显示的颜色
把区间抽象成节点。每个区间有一个l和r，倒着操作。每次操作就合并所有操作的区间。
如果操作的左右端点的父亲不同，那么本次操作就是合法的，说明至少有一个段是没有被合并的。还可以被涂一次颜色。
否则不合法次数 ans + 1。
最后答案就是 n – ans 。相当于问有多少次合法合并（询问）。很明显可以转化为并查集的询问条件是否成立。由于操作只有1e4次，所以不同的点不会超过2e4个点。可以把区间进行离散化。
#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<stdio.h>
#include<iostream>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 10233;
pii q[100233 + 233];
int f[100233 + 233];
int ff(int x)
{
if(f[x] == x) return x;
return f[x] = ff(f[x]);
}
void uni(int u, int v)
{
f[ff(u)] = ff(v);
}
int main()
{
int tc,n;
scanf("%d",&tc);
for(int j = 1; j <= tc; j++)