题目链接：http://www.icpc.moe/onlinejudge/showProblem.do?problemCode=1610
题意：给一个长8000的绳子，向上染色。一共有n段被染色，问染色后共有多少不同的色段。注意假如相邻两个线段同色，那么算作一条线段。
线段树区间更新，不需要pushUP操作，因为查询和非叶节点无关。找长线段的时候首先定位最靠左那根，然后判后面是否与前面的线段颜色相等。注意有可能出现两条线段中间没有染色的情况，这时候查询返回一个无关值，这时候重置p即可。
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; #define fr first
#define sc second
#define pb(a) push_back(a)
#define Rint(a) scanf("%d", &a)
#define Rll(a) scanf("%I64d", &a)
#define Rs(a) scanf("%s", a)
#define Fread() freopen("in", "r", stdin)
#define Fwrite() freopen("out", "w", stdout)
#define Rep(i, n) for(int i = 0; i < (n); i++)
#define For(i, a, n) for(int i = (a); i < (n); i++)
#define Cls(a) memset((a), (0), sizeof(a))
#define Clr(a, x) memset((a), (x), sizeof(a))
#define Full(a) memset((a), 0x7f7f, sizeof(a)) #define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int maxn = ;
int sum[maxn<<];
int vis[maxn];
int n, a, b, c; void pushDOWN(int rt) {
if(sum[rt] != -) {
sum[rt<<] = sum[rt<<|] = sum[rt];
sum[rt] = -;
}
} void update(int L, int R, int c, int l, int r, int rt) {
if(L <= l && r <= R) {
sum[rt] = c;
return;
}
pushDOWN(rt);
int m = (l + r) >> ;
if(L <= m) update(L, R, c, lson);
if(R > m) update(L, R, c, rson);
} int query(int p, int l, int r, int rt) {
if(l == r) {
return sum[rt];
}
pushDOWN(rt);
int m = (l + r) >> ;
if(p <= m) return query(p, lson);
else return query(p, rson);
} int main() {
// Fread();
while(~Rint(n)) {
int lo = 0x7f7f;
Clr(sum, -); Cls(vis);
Rep(i, n) {
Rint(a), Rint(b), Rint(c);
lo = min(lo, a+);
update(a+, b, c, , , );
}
int p = query(lo, , , );
vis[p]++;
For(i, lo+, ) {
int t = query(i, , , );
if(t == -) {
p = -;
continue;
}
if(t != p) {
vis[t]++;
p = t;
} }
Rep(i, ) {
if(vis[i]) printf("%d %d\n", i, vis[i]);
}
printf("\n");
}
return ;
}