2528:Mayor’s posters

本题很多都是用的线段树，但线段树客观来说代码长，容易写错，所以并查集其实更好

先把操作离线，由于只有靠后的操作才会对区间产生影响，所以说每个点最后一次覆盖的才是最后显示的颜色

把区间抽象成节点。每个区间有一个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++)
    {
        scanf("%d",&n);
        set<int> st;
        unordered_map<int,int> raw,ump;
        for(int i = 1; i <= n; i++)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            q[i] = make_pair(l,r + 1);
            st.insert(l);st.insert(r + 1);
        }
        for(int i = 1; i <= 100233; i++) f[i] = i;
        int cnt = 0;
        for(set<int>::iterator it = st.begin(); it != st.end(); it++)
        {
            ump[*it] = ++cnt;
            //raw[cnt] = *it;
        } 
        int ans = 0;
        for(int i = n; i >= 1; i--)
        {
            int l = ump[q[i].first], r = ump[q[i].second];
            if(ff(l) != ff(r))
            {
                int k = l;
                while(ff(k) != ff(r))
                {
                    k = ff(k);
                    f[k] = ff(r);
                    k = k + 1;
                }
            }
            else ans++;
        }
        printf("%d\n",n - ans);
    }
}

百练是支持unordered_map的，poj不支持。所以在poj上需要自己手动写离散化（其实开个1e7大小的数组进行暴力映射就可以了，亲测能过）