zoj1610 发表于 2018-04-07 | 分类于 算法 , 数据结构 , 线段树 | 阅读数 次 链接:zoj1610 题解 和poj2528差不多,但是不需要离散化. 注意,这里染的不是点是区间,比如0 1 1, 1 2 1这组数据输出应该是1 2,解决方法是所有左标+1 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)using namespace std;const int N=1e5;const int M=8000;int rt[N<<2],num[N],n,m,nc;inline void pushdown(int o){rt[o<<1]=rt[o<<1|1]=rt[o];rt[o]=-1;}void update(int o,int l,int r,int ll,int rr,int c){ if(ll<=l&&rr>=r){rt[o]=c;return ;} if(rt[o]!=-1)pushdown(o); int mid=l+r>>1; if(ll<=mid)update(o<<1,l,mid,ll,rr,c); if(rr>mid)update(o<<1|1,mid+1,r,ll,rr,c);}void query(int o,int l,int r){ if(l==r){if(rt[o]>=0&&rt[o]!=nc)num[rt[o]]++;nc=rt[o];return ;} if(rt[o]!=-1)pushdown(o); int mid=l+r>>1; query(o<<1,l,mid); query(o<<1|1,mid+1,r);}int main(){ while(~scanf("%d",&n)){ nc=-1; memset(rt,-1,sizeof(rt)); memset(num,0,sizeof(num)); rep(i,1,n){ int a,b,c; scanf("%d%d%d",&a,&b,&c); update(1,1,M,a+1,b,c); } query(1,1,M); rep(i,0,M)if(num[i])printf("%d %d\n",i,num[i]); printf("\n"); } return 0;}