#线段树#zoj 1610 Count the color

本文主要是介绍#线段树#zoj 1610 Count the color，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

用颜料覆盖一条线中的区间，输出能看到的颜色的个数。

---

分析

用线段树，统计时需要判重。

---

代码

#include<cstdio>
#include<cstring>
using namespace std;
int flag[30001],cover[30001];
int n,ll,rr,cl,color;
void inse(int k,int l,int r,int a,int b,int c)
{if (l==a&&r==b) cover[k]=c;if (cover[k]==c) return;if (cover[k]>=-1){cover[k*2]=cover[k];cover[k*2+1]=cover[k];cover[k]=-2;}int m=(l+r)>>1;if (b<=m) inse(k*2,l,m,a,b,c);else if (a>=m) inse(k*2+1,m,r,a,b,c);else{inse(k*2,l,m,a,m,c);inse(k*2+1,m,r,m,b,c);}return;
}
void find(int k,int l,int r)
{if (cover[k]>=-1){if (cover[k]!=-1&&cover[k]!=color) flag[cover[k]]++;color=cover[k];return;}else if (r-l>1){find(k*2,l,(l+r)>>1);find(k*2+1,(l+r)>>1,r);}
}
int main()
{while (scanf("%d",&n)!=EOF){memset(flag,0,sizeof(flag));memset(cover,-1,sizeof(cover));for (int i=1;i<=n;i++){scanf("%d%d%d",&ll,&rr,&cl);inse(1,0,8000,ll,rr,cl);}color=-3;find(1,0,8000);for (int i=0;i<=30000;i++) if (flag[i]) printf("%d %d\n",i,flag[i]);printf("\n");}return 0;
}

这篇关于#线段树#zoj 1610 Count the color的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---