首页 > 代码库 > ZOJ 1610 Count the Colors （线段树区间更新）
ZOJ 1610 Count the Colors （线段树区间更新）
题目链接
题意 ： 一根木棍，长8000，然后分别在不同的区间涂上不同的颜色，问你最后能够看到多少颜色，然后每个颜色有多少段，颜色大小从头到尾输出。
思路 ：线段树区间更新一下，然后标记一下，最后从头输出。
//ZOJ 1610#include <cstdio>#include <cstring>#include <iostream>using namespace std ;int p[8010*4],lz[8010*4] ,hashh[8010*4],hash1[8101*4];//void pushup(int rt)//{// if(p[rt << 1] == p[rt << 1 | 1])// p[rt] = p[rt << 1] ;// else p[rt] = -1 ;//}void pushdown(int rt){ if(lz[rt] != -1) { lz[rt << 1] = lz[rt << 1 | 1] = lz[rt] ; p[rt << 1] = p[rt << 1 | 1] = lz[rt] ; lz[rt] = -1 ; }}//void build(int l,int r,int rt)//{// lz[rt] = -1 ;// if(l == r)// {// p[rt] = -1 ;// return ;// }// int mid = (l + r) >> 1 ;// build(l,mid,rt << 1) ;// build(mid+1,r,rt << 1 | 1) ;// pushup(rt) ;//}void update(int L,int R,int l,int r,int rt,int sc){ if(l >= L && r <= R) { lz[rt] = sc ; p[rt] = sc ; return ; } pushdown(rt) ; int mid = (l+r) >> 1; if(mid >= L) update(L,R,l,mid,rt << 1,sc) ; if(mid < R) update(L,R,mid+1,r,rt << 1 | 1 ,sc) ; // pushup(rt) ;}void query(int l,int r,int rt){ if(l == r) { hashh[l] = p[rt] ; return ; } pushdown(rt) ; int mid = (l+r) >> 1 ; query(l,mid,rt << 1) ; query(mid+1,r,rt << 1 | 1) ;}void Init(){ memset(lz,-1,sizeof(lz)) ; memset(hashh,0,sizeof(hashh)) ; memset(hash1,0,sizeof(hash1)) ; memset(p,-1,sizeof(p)) ;}int main(){ int n ,x1,x2,c; while(cin >> n ) { Init() ; for(int i = 0 ; i < n ; i++) { cin >> x1 >> x2 >> c ; update(x1,x2-1,0,8000,1,c) ; } query(0,8000,1) ; for(int i = 1 ; i <= 8000 ; i++) { if(hashh[i] != hashh[i-1]) { if(hashh[i-1] != -1) hash1[hashh[i-1]] ++ ; } } if(hashh[8000] != -1) hash1[hashh[8000]]++ ; for(int i = 0 ; i <= 8000 ;i++) { if(hash1[i]) { printf("%d %d\n",i,hash1[i]) ; } } puts("") ; } return 0 ;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。