Sky 玩了一个神奇的游戏，这种游戏有n个集合，每一个集合内都可以插入数字。每一个集合都有一个权值，集合的权值定义为该集合内最长连续出现的数字个数。连续出现定义为： 如果[l,r]内的元素全部在该集合中存在， 那么这一部分是连续出现的，
连续的数字个数为r-l+1。
现在 Sky 准备开始玩这个集合，每一次 Sky 都会对一个区间的集合进行操作，一共操作m次。
每一次操作会输入l，r，x ，表示在第往l 到 r的集合都插入x这数字。
Sky 想知道，他的所有操作结束之后，所有集合的权值是什么。
输入两个数字n，m，然后输入m行l r x
输出n个数字，表示n个集合的权值
$ n,m le 10^5 $
(1 le x le 10^9)
保证同一个数字不会重复插入一个集合
首先，区间加入一个数，有点像线段树，但是线段树每个节点代表一个元素，怎么代表一个集合？？一个线段树只能表示一个集合，开n颗线段树？一次操作nlogn，无法接受。。
多颗线段树？？主席树，线段树合并。。。
进一步分析，可以用线段树合并最后来统计答案。把x的值域当做线段树叶子节点个数，显然要离散化，但是跟一般的离散化又不一样，因为要判断离散化前的数字是不是相邻的，这需要特殊处理一下。区间操作可以用差分来代替，大大降低了时间复杂度。最后线段树维护区间最大连续数字长度即可。
这题y_dove大佬弱的时候用线段树分治过了，多了一个log,但是还是很快，std是线段树加STL一堆神奇操作，看不懂，空间比线段树合并优一点，但是比较慢。
#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
using namespace std;
typedef long long lxl;
template<typename T>
inline T max(T &a, T &b) {
return a > b ? a : b;
}
template<typename T>
inline T min(T &a, T &b) {
return a < b ? a : b;
}
inline char gt() {
static char buf[1 << 21], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void read(T &x) {
register char ch = gt();
x = 0;
int w(0);
while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x) {
if(x < 0) x = -x, putchar('-');
char ch[20];
int num(0);
while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
while(num) putchar(ch[num--]);
putchar(' ');
}
const int MX = 1e5 + 79;
int n, m;
struct opt {
int l, r, val;
bool operator <(const opt &r)const {
return this->val < r.val;
}
} p[MX];
int cnt, root[MX*40];
int lc[MX * 40], rc[MX * 40], sum[MX * 40], lmax[MX * 40], rmax[MX * 40];
//左儿子编号，右儿子编号,整个区间最大连续的 ,从左往右连续的，从右往左连续的
inline void pushup(int p, int L, int R) {
int mid((L + R) >> 1);
if(lmax[lc[p]] != (mid - L + 1)) { //左儿子左边未满
lmax[p] = lmax[lc[p]];
} else {
lmax[p] = (mid - L + 1) + lmax[rc[p]];
}
if(rmax[rc[p]] != (R - mid)) {//右儿子右边未满
rmax[p]=rmax[rc[p]];
} else {
rmax[p]=rmax[lc[p]]+(R-mid);
}
sum[p]=max(max(sum[lc[p]],sum[rc[p]]),rmax[lc[p]]+lmax[rc[p]]);
//左儿子连续的，右儿子连续的，两个儿子相邻的
}
inline void change(int &p, int L, int R, int pos, int val) {
if(!p) p = ++cnt;
if(L == R) {
lmax[p]=rmax[p]=sum[p]+=val;
return;
}
int mid((L + R) >> 1);
if(pos <= mid) change(lc[p], L, mid, pos, val);
if(pos > mid) change(rc[p], mid + 1, R, pos, val);
pushup(p, L, R);
}
inline void merge(int &a, int b, int L, int R) {
if(!a) {
a = b;
return;
}
if(!b) return;
if(L == R) {
sum[a]+=sum[b];
lmax[a]+=lmax[b];
rmax[a]+= rmax[b];
return;
}
int mid((L + R) >> 1);
merge(lc[a],lc[b] ,L, mid);
merge(rc[a],rc[b], mid + 1, R);
pushup(a, L, R);
}
/*
10 10
1 2 1
1 2 2
1 2 3
1 2 4
1 3 5
3 4 6
3 4 7
3 4 8
3 4 9
3 10 10
*/
int main() {
freopen("gather.in", "r", stdin);
freopen("gather.out", "w", stdout);
read(n);
read(m);
rep(i, 1, m) {
read(p[i].l);
read(p[i].r);
read(p[i].val);
}
int R = 3 * MX,t(-1);
sort(p + 1, p + 1 + m);
p[0].val = -1;
rep(i, 1, m) {
if(p[i].val != p[i - 1].val) {
if(p[i].val == p[i - 1].val + 1)
t++;
else t += 2;
}
change(root[p[i].l], 1, R, t, 1);
change(root[p[i].r + 1], 1, R, t, -1);
}//离散化
out(sum[root[1]]);
rep(i, 2, n) {
merge(root[1], root[i], 1, R);
out(sum[root[1]]);
}
//每个集合里面的内容，用前缀和 表示
return 0;
}