---

题目描述

X轴上从下向上依次叠放一定长度的某种颜色的线段。问从上向下看X轴，它被分成了不同颜色的多少段？

---

输入格式

第1行：2个整数XC，N。XC表示X轴的颜色，1<=N<=100000，表示线段的条数，其中X轴的范围为[-100000,100000]。。 接下来N行，每行3个整数L，R，C，-100000 <=L<=R<= 100000，表示一线段的左、右端点；1<=C<=100000，表示线段的颜色。

---

输出格式

文件输出只有一行仅为一个整数M，表示X轴被分成不同颜色的多少段。

---

样例数据

样例输入

1 4 2 6 2 1 5 3 3 4 2 7 8 4

样例输出

8

---

题目分析

统计标记总数（区间修改区间查询） 维护颜色data（懒标记） 标记总数sum 左右端点颜色leftcolor/rightcolor 对于每一个新的颜色，丢进线段树添加懒标记 为什么需要leftcolor/rightcolor？ 因为有可能这一段区间右边部分与下一段区间的左边部分颜色相等，而懒标记尚未下传没有更新他们，如果相等sum在标记上传的时候还需-1 注意偏移量

---

源代码

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const int maxn=800000; struct Tree { //修改区间 查询区间 int left,right,data,sum,leftcolor,rightcolor; //sum表示标记总数 leftcolor表示左端点颜色 rightcolor表示右端点颜色 }; struct Segment_Tree { //统计标记总数 Tree tree[maxn*4]; void build(int index,int Left,int Right,int color) { tree[index].left=Left; tree[index].right=Right; tree[index].leftcolor=tree[index].rightcolor=tree[index].data=color; if(Left==Right)return; int mid=(Left+Right)/2; build(2*index,Left,mid,color); build(2*index+1,mid+1,Right,color); } void push_down(int index) { if(tree[index].data>=0) { tree[index*2].data=tree[index*2].leftcolor=tree[index*2].rightcolor=tree[index*2+1].data=tree[index*2+1].leftcolor=tree[index*2+1].rightcolor=tree[index].data; tree[index*2].sum=tree[index*2+1].sum=1; tree[index].data=-1; } } void push_up(int index) { tree[index].sum=tree[index*2].sum+tree[index*2+1].sum; tree[index].leftcolor=tree[index*2].leftcolor; tree[index].rightcolor=tree[index*2+1].rightcolor; if(tree[index*2].rightcolor==tree[index*2+1].leftcolor)tree[index].sum--; } void modify(int index,int Left,int Right,int color) { if(Right<tree[index].left||Left>tree[index].right)return; //不相交 if(Left<=tree[index].left&&Right>=tree[index].right) { //完全包含 tree[index].leftcolor=tree[index].rightcolor=tree[index].data=color; tree[index].sum=1; return; } push_down(index); modify(index*2,Left,Right,color); modify(index*2+1,Left,Right,color); push_up(index); } }; Segment_Tree st; int Left,Right,n,Delta=100001,color; int main() { color=Get_Int(); st.build(1,-100000+Delta,100000+Delta,color); n=Get_Int(); for(int i=1; i<=n; i++) { int l=Get_Int()+Delta,r=Get_Int()+Delta-1,color=Get_Int(); st.modify(1,l,r,color); } printf("%d\n",st.tree[1].sum); return 0; }

---