[NOIP模拟][并查集]纸带

题目描述：
题目大意：有一个无限长的纸带··上面被划分为若干个格子··现在进行N次操作，第i次操作在L到R上擦出曾经写上的数字（如果有）,并写上数字i，询问最终可以看到多少个数字。N≤106，L,R≤109。
样例输入：

4
0 5
3 8
5 6
4 7

样例输出：

3

题目分析：
首先离散化,但注意离散化时候如果相邻两个数的差大于1··需要在中间插入一个在两数之间的数(因为中间本来有空隙，也许它会被染色，但你直接离散化就把这段弄没了)。
正解：并查集，我们将询问倒着来，然后用并查集维护每次染色的最右端的位置,这样当你下一次操作遇到一个已经染过色的点，就直接跳转到一个没有染色的点，具体细节见代码。理论时间复杂度O（n）。
附代码：

#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
#include<algorithm>
#include<queue>
using namespace std;

const int N=4e6+100;
int n,m,tot,cnt,b[N],ans,jump[N],check[N],po,ri[N];
bool flag[N/2];
struct node{
    int l,r;
}a[N/2];

inline int readint()
{
    char ch;int i=0,f=1;
    for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
    if(ch=='-') {ch=getchar();f=-1;}
    for(;ch>='0'&&ch<='9';ch=getchar()) i=(i<<3)+(i<<1)+ch-'0';
    return i*f;
}

inline int find(int x){
    if(check[x]==0) return x;
    return jump[x]=find(jump[x]);
}

inline void dis_init()//离散化
{
    sort(b+1,b+tot+1);
    tot=unique(b+1,b+tot+1)-b-1;
    m=tot;
    for(int i=2;i<=tot;i++)//插入
        if(b[i]!=b[i-1]+1) b[++m]=b[i-1]+1;
    sort(b+1,b+m+1);
    for(int i=1;i<=n;i++)
    {
        a[i].l=lower_bound(b+1,b+m+1,a[i].l)-b;
        a[i].r=lower_bound(b+1,b+m+1,a[i].r)-b;
    }
}

int main()
{
    //freopen("ribbon.in","r",stdin);
    //freopen("ribbon.out","w",stdout);

    int l,r,x,y;
    n=readint();
    for(int i=1;i<=n;i++)
    {
        l=readint()+1;r=readint();
        a[i].l=l;a[i].r=r;
        b[++tot]=l;b[++tot]=r;
    }
    dis_init();
    for(int i=n;i>=1;i--)
    {
        x=a[i].l;y=a[i].r;
        po=find(y+1);//右端要一直找到一个没有染色的点
        while(x<=y)
        {
            if(check[x]!=0) x=find(x);//染过色，跳转
            else
            {
                if(flag[i]==false) ans++,flag[i]=true;//统计有多少种颜色（数字）
                check[x]=i;
                jump[x]=po;
                x++;
            }
        }   
    }
    printf("%d",ans);

    return 0;
}