1、给了每条线段的颜色，存在颜色覆盖，求表面上能够看到的颜色种类以及每种颜色的段数。
2、线段树区间更新，单点查询。
但是有点细节，比如：
输入：
2
0 1 1
2 3 1
输出：
1 2
这种情况如果不处理，那么由于是检查点的颜色，会检查到0,1,2,3的颜色都为1，认为是一段连续的，就会输出 1 1
需要处理一下，代码中把所有的左端点都+1，避免了这种情况，比较巧妙。
3、
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; #define L(root) ((root) << 1) #define R(root) (((root) << 1) + 1) const int MAXN = 8005; struct st { // 区间范围 int left, right; int flag;//-1没有颜色 } st[MAXN * 4]; int color[MAXN];//每种颜色看到的段数 // 建树代码基本不变 void build(int root, int l, int r) { st[root].left = l, st[root].right = r, st[root].flag = -1; if (l == r) { return; } int m = l + ((r - l) >> 1); build(L(root), l, m); build(R(root), m + 1, r); } int query(int root, int x)//单点查询 { if (st[root].left == st[root].right) { return st[root].flag; } // 否则需将当前区间的“缓冲”值更新下去并修正各节点区间的总和 if (st[root].flag!=-1) { st[L(root)].flag = st[root].flag; st[R(root)].flag = st[root].flag; st[root].flag = -1; } int m = st[root].left + ((st[root].right - st[root].left) >> 1); if (x <= m) { return query(L(root), x); } else { return query(R(root), x); } } void update(int root, int l, int r, int v)//区间更新 { // 如变更区间恰等于节点区间，只修正当前节点区间即可 if (st[root].left == l && st[root].right == r) { st[root].flag = v; return; } // 否则需向下修正相关节点区间 if (st[root].flag!=-1) { st[L(root)].flag = st[root].flag; st[R(root)].flag = st[root].flag; st[root].flag = -1; } int m = st[root].left + ((st[root].right - st[root].left) >> 1); if (r <= m) { update(L(root), l, r, v); } else if (l > m) { update(R(root), l, r, v); } else { update(L(root), l, m, v); update(R(root), m + 1, r, v); } } int main() { int n,i; int x1,x2,c; int lastColor;//记录上一个颜色 int nowColor;//当前颜色 while(~scanf("%d",&n)){ build(1,1,8000); for(i=1;i<=n;++i){ scanf("%d%d%d",&x1,&x2,&c); update(1,++x1,x2,c);//++x1表示缩掉前面一点，处理了0 1 1,2 3 1这种情况，而且还符合了左端点从1开始 } memset(color,0,sizeof(color)); lastColor=-1; for(i=1;i<=8000;++i){ nowColor=query(1,i); if(nowColor==lastColor) continue; else if(nowColor!=-1) ++color[nowColor]; lastColor=nowColor; } for(i=0;i<=8000;++i)//颜色标号是0~8000 if(color[i]) printf("%d %d ",i,color[i]); printf(" "); } return 0; }
c2.这个没有用上面的左端点+1，但是在建树的时候是用的[0,1],[1,2],[2,3]，类似这样的建树，比较刁
上面的建树是[0,1],[2,3]，类似这样的，还是有点区别的。具体看代码吧。
#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> using namespace std; const int MAXN=8010; struct Node { int l,r; int color; }segTree[MAXN*3]; int color[MAXN]; int temp; void Build(int i,int l,int r) { segTree[i].l=l; segTree[i].r=r; segTree[i].color=-1;//-1表示没有颜色 if(l+1==r)return; int mid=((l+r)>>1); Build(i<<1,l,mid); Build((i<<1)|1,mid,r); } void insert(int i,int l,int r,int c) { if(l==r)return; if(segTree[i].color==c)return; if(l<=segTree[i].l&&r>=segTree[i].r) { segTree[i].color=c; return; } if(segTree[i].color>=0)//存在颜色，往下更新 { segTree[i<<1].color=segTree[i].color; segTree[(i<<1)|1].color=segTree[i].color; segTree[i].color=-2;//表示有多种颜色 } int mid=((segTree[i].l+segTree[i].r)>>1); if(r<=mid) insert(i<<1,l,r,c); else if(l>=mid) insert((i<<1)|1,l,r,c); else { insert(i<<1,l,mid,c); insert((i<<1)|1,mid,r,c); } segTree[i].color=-2; } void Count(int i)//统计各颜色的段数 { if(segTree[i].color==-1) { temp=-1; return; } if(segTree[i].color!=-2) { if(segTree[i].color!=temp)//temp存的是前一段的颜色 { color[segTree[i].color]++; temp=segTree[i].color; } return; } if(segTree[i].l+1!=segTree[i].r) { Count(i<<1); Count((i<<1)|1); } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n,a,b,c; int Max; while(scanf("%d",&n)!=EOF) { Build(1,0,8000); Max=0; while(n--) { scanf("%d%d%d",&a,&b,&c); insert(1,a,b,c); if(c>Max)Max=c; } temp=-1; memset(color,0,sizeof(color)); Count(1); for(int i=0;i<=Max;i++) { if(color[i])printf("%d %d ",i,color[i]); } printf(" "); } return 0; }