首页 > 代码库 > zoj-1610-Count the Colors-线段树-区域更新,单点查询
zoj-1610-Count the Colors-线段树-区域更新,单点查询
线段树的区域更新,然后单点查询。
x1 x2 c:区域更新x1-x2为c。
全部染色之后,从0-8000依次查询每个点的颜色。然后存贮每一种颜色有几块。
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<math.h> using namespace std; #define lmin 0 #define rmax 8000 #define lson l,(l+r)/2,rt<<1 #define rson (l+r)/2+1,r,rt<<1|1 #define root lmin,rmax,1 #define maxn 10000 int cl[maxn*4]; int num[maxn]; void push_up(int rt) { } void push_down(int rt) { if(cl[rt]!=-1) { cl[rt<<1]=cl[rt]; cl[rt<<1|1]=cl[rt]; cl[rt]=-1; } } void update(int ll,int rr,int x,int l,int r,int rt) { if(l>rr||r<ll)return; if(ll<=l&&rr>=r) { // cout<<l<<"-"<<r<<"-"<<rt<<"-"<<x<<endl; cl[rt]=x; return; } push_down(rt); update(ll,rr,x,lson); update(ll,rr,x,rson); } int query(int st,int l,int r,int rt) { if(r<st)return 0; if(l>st)return 0; if(l==r&&st==l)return cl[rt]; if(l<=st&&r>=st&&cl[rt]!=-1)return cl[rt]; return query(st,lson)+query(st,rson); } int main() { int n,l,r,c; while(~scanf("%d",&n)) { memset(cl,-1,sizeof(cl)); memset(num,0,sizeof(num)); while(n--) { scanf("%d%d%d",&l,&r,&c); update(l,r-1,c,root); } int y=-1; for(int i=0;i<=8000;i++) { int x=query(i,root); //cout<<x<<"-"<<endl; // getchar(); if(x==y)continue; y=x; if(x>=0)num[x]++; } for(int i=0;i<=8000;i++) { if(num[i]) { printf("%d %d\n",i,num[i]); } } cout<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。