染色问题（漂浮思想的应用）

染色问题(color.pas/c/cpp)
【题目描述】
平面上有n个珠子排成一排， 每个珠子初始颜色为0，你要对他们进行m次染色，每次你选定l和r，然后把[l,r]之间的珠子染成编号c的颜色，每个珠子的最终颜色为它曾经染过的编号最大的颜色，请你写个程序统计每个珠子最终的颜色。
【输入格式】
第一行两个数n，m，表示珠子个数和染色的次数
接下来m行，每行三个数l,r,c如题意所示
【输出格式】
由于数据较大，为了减少输出所用的不必要的时间，请采取以下方法输出：
假如a[i]为第i个珠子的最终颜色
ans := 0;
for i := 1 to n do ans := (ans * 1200007 + a[i]) mod 999911659;
writeln(ans);
注意用int64保存相关变量，防止运算过程中越界
【样例输入】
3 2
1 2 1
2 2 2
【样例输出】
146411103
【数据范围】
30% n,m<=5000
50% n,m <= 10000
80% n,m <= 500000
100% n <= 1000000, m <= 2000000

题解：第一感觉是线段树，但是常数大对100%的要挂（我会说原题时限5S所以线段树能过……不过这就太水了），然后题解讲的就是一种很巧妙的并查集

可以想到在线的方法肯定TLE，而且题目也不要求是在线的，所以想着离线搞。。。。。。。。然后很自然想到按颜色从大到小排序，这样有个好处就是你按这个顺序染的就是最后你看到的，类似的经典漂浮法问题：http://www.cnblogs.com/wmrv587/p/3534476.html

然后就是具体如何实现的问题了——那就是并查集= =

撸一个f[i]维护最靠近i左边的未染色点的下标，然后边撸f[i]边搞结果就行了……（具体看code)

for(int i=1;i<=n;++i) f[i]=i;//由f[i]的定义知道先开始每个i的f[i]是自己 
for(int i=1;i<=m;++i)//a[i]已经按a[i].c从大到小排好
{
    int t=find(a[i].r);//从右边界开始往左找没染色的
    while(t>=a[i].l)
    {
        ans[t]=a[i].c;
        f[t]=find(f[t-1]);//因为f[t]已经染色了，所以要往前维护
        t=f[t];//迭代，继续进行下去
    }
}