//ZOJ 1610 Count the Colors 线段树 成段更新 单点求值
/*
题意:
有一个0-8000的区间,每次将一个子区间染色,颜色用整数表示,
如果一段区间被重复染色的话,它的颜色会被后面染上去的颜色覆盖
问最后有几种颜色出现,每种颜色的区间有多少个
思路:
注意是对区间染色,不是对点染色。
成段更新 单点求值
由于不需要知道父节点的信息,所以不需要pushup。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define N 8005
int add[N<<2],color[N];
int n;
void Pushdown(int rt){
if(add[rt] != -1){
add[rt<<1] = add[rt<<1|1] = add[rt];
add[rt] = -1;
}
}
void Build(){
memset(add,-1,sizeof(add));
memset(color,0,sizeof(color));
}
void Update(int rt,int l,int r,int L,int R,int val){
if(L <= l && R >= r){
add[rt] = val;
return ;
}
Pushdown(rt);
int mid = (l + r) >> 1;
if(L <= mid) Update(lson,L,R,val);
if(R > mid ) Update(rson,L,R,val);
}
int Query(int rt,int l,int r,int x){
if(l == r){
return add[rt];
}
Pushdown(rt);
int mid = (l + r) >> 1;
if(x <= mid) Query(lson,x);
else Query(rson,x);
}
int main(){
int i;
int a,b,c;
int mmax,mmin;
int pre;
while(scanf("%d",&n)!=EOF){
Build();
mmax = -1;
mmin = 8001;
for(i = 1; i <= n; ++i){
scanf("%d %d %d",&a,&b,&c);
if(b > mmax) mmax = b;
if(a+1 < mmin) mmin = a+1;
Update(1,1,8000,a+1,b,c);
}
pre = Query(1,1,8000,mmin);
++color[pre];
for(i = mmin+1; i <= mmax; ++i){
int tmp = Query(1,1,8000,i);
if(tmp != pre){
pre = tmp;
++color[pre];
}
}
for(i = 0; i <= 8000; ++i)
if(color[i])
printf("%d %d\n",i,color[i]);
puts("");
}
return 0;
}
分享到:
相关推荐
zoj 1610 Count the Colors.md
本资源是对线段树操作比较完整的操作,包括线段树的动态插入,动态删除和维护,可以查询区段的最大值,最小值,完成线段树的基本操作。
zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 poj 3468 成段更新 ...
hdu 1166线段树
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
zoj 1255 The Path.md
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
zoj 1810 The Gourmet Club.md
zoj 2499 The Happy Worm.md
zoj 2151 The Highest Profits.md
浙江大学2451题 用线段树思想解的,c++语言版本
Problem Arrangement zoj 3777
ZOJ题目答案源码
2416和2451测试程序原代码,编译成功,好使
一个非常非常非常非常实用的zoj结题代码
count 0; cout << "[" << endl; if s1 length s2 length BackTrake s1 s2 ; cout << "]" << endl; cout << count << endl; } return 0; }">深度...
ZOJ1805代码
zoj 1003 c语言的,要写这么多描述吗。。