正题

题目： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=610

---

题意

有一条长m的线，有n条长度和颜色不同的线段，每个颜色可以看到的段数。

---

解题思路

标记颜色-2表示有多种颜色，然后用color表示上次的颜色以去重。

---

代码

#include<cstdio> #include<cstring> using namespace std; struct xjq{ int l,r,cover; }tree[30001]; int flag[30001]; int n,ll,rr,w,s,cl,color; void build(int x,int a,int b)//建树 { tree[x].l=a; tree[x].r=b; tree[x].cover=-1; if (b-a==1) return; else { int m=(a+b)/2; build(x*2,a,m); build(x*2+1,m,b); } } void inster(int x,int a,int b,int c)//插入 { if (tree[x].cover==c) return; if (tree[x].l==a && tree[x].r==b) { tree[x].cover=c;return; } if (tree[x].cover>=-1) { tree[x*2].cover=tree[x].cover; tree[x*2+1].cover=tree[x].cover; tree[x].cover=-2; } int m=tree[x*2].r; if (b<=m) inster(x*2,a,b,c); else if (a>=m) inster(x*2+1,a,b,c); else { inster(x*2,a,m,c); inster(x*2+1,m,b,c); } return; } void find(int x)//查询 { if (tree[x].cover>=-1) { if (tree[x].cover!=-1 && tree[x].cover!=color) flag[tree[x].cover]++;//统计 color=tree[x].cover;//标记 return; } if (tree[x].r-tree[x].l==1) return; else { find(x*2); find(x*2+1); } } int main() { while (scanf("%d",&n)!=EOF) { memset(tree,0,sizeof(tree)); memset(flag,0,sizeof(flag)); for (int i=1;i<=8000;i++) tree[i].cover=-1; build(1,0,8000); for (int i=1;i<=n;i++) { scanf("%d%d%d",&ll,&rr,&cl); inster(1,ll,rr,cl); } s=0; color=-3; find(1); for (int i=0;i<=30000;i++) if (flag[i]) printf("%d %d\n",i,flag[i]);//输出 printf("\n"); //printf("%d\n",s); } }