ZOJ – 1610 Count the Colors ([线段树] 区间修改+染色统计)

• 将区间[l,r]染成c（c>=0）

• 输出每一种颜色的段数

• 因为是对区间染色，需要转为对点染色，即向一个方向开闭，这里选择(l,r]

• 实际上就对整个区间[1,8000]进行查询
• 当区间p为单区间，即l(p)==r(p)时，判断是否和左相邻的单区间颜色相同，是则计数++
• 问题在于怎么记录左相邻的单区间，实际上我们询问时用的是dfs，所以对于最底层单曲间，时间戳随着该区间的下标增加而增加，也就是说我们是顺序访问实际的每个点的

//在区间修改时，有lazy标记的区间 其lazy标记就就是区间里面的同一值 
#include<algorithm>
#include <iostream>
#include   <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan_d(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int maxn = 1e4+10;
struct SegmentTree {
	int l,r;
	long long add;
#define l(x) tree[x].l
#define r(x) tree[x].r
//#define sum(x) tree[x].sum
#define add(x) tree[x].add
} tree[maxn*4];
int a[maxn],n,last_color;
void build(int p,int l,int r) {
	l(p)=l,r(p)=r;
	add(p)=-1;//注意初始化位置 
	if(l==r) {
		return ;
	}
	int mid=(l+r)/2;//只有这里的一半是直接用传入的l，r，但实际上这里的l，r就是下面的p.l,p.r
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
//延迟标记代表：该节点已经被修改，但子节点尚未被更新
void spread(int p) {
	if(add(p)!=-1) {
		add(p*2)=add(p*2+1)=add(p);
		add(p) = -1;//清除p节点的标记
	}
}
void change(int p,int l,int r,int d) {
	if(l<=l(p) && r>=r(p)) { //完成覆盖
		add(p)=d;//给节点打延迟标记
		return ;
	}
	spread(p); 
	int mid=(l(p)+r(p))/2;
	if(l<=mid)change(p*2,l,r,d);
	if(r>mid)change(p*2+1,l,r,d);
}
void ask(int p) {
	if(l(p)==r(p)){
		if(add(p)>=0&&last_color!=add(p))++a[add(p)];
		last_color=add(p);
		return;
	}
	spread(p);
	ask(p*2);
	ask(p*2+1);
}
int main()
{
    while(~scanf("%d",&n)){
        last_color=-1;
        memset(a,0,sizeof(a));
        build(1,1,8000);
        rep(i,1,n){
            int d,l,r;
            scanf("%d%d%d",&l,&r,&d);
            if(l<r) change(1,l+1,r,d);
        }
       	ask(1);
        rep(i,0,8000){
            if(a[i]) printf("%d %d\n",i,a[i]);
        }
        printf("\n");
    }
}