正题

题目：

http://acm./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);}}