「题目描述」

平面上有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

「时间限制」

2s

题解

线段树不知道有多少，但是有更为简单的做法

用to[i]表示i结点后第一个未被染色的结点编号，将操作按C排序后从大到小操作，顺便更新to数组