题目大意:
给你一段长度为 8000 的绳子,n 次操作,每次将[ l r ]区间染色为 c ,染色会覆盖掉之前的染色,所有数字不超过8000,统计最后的颜色和出现的不连续区间的个数。按颜色顺序输出。
题解思路:
线段数区间染色,因为是区间染色,所以在每个2点之间又加了一个点来代表此区间的颜色。
最后统计区间个数用一个last标记一下上次的颜色即可,注意如果颜色断掉last要初始一下。
(这个数据范围,暴力不好吗)
几个样例
2
1 2 1
3 4 1
3
1 10 0
1 4 1
5 10 2
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<cmath>#include<queue>#include<map>#include<set>#include<stack>const int maxn=16005;using namespace std;int col[4*maxn],n,cnt[maxn],last;void built(int l,int r,int now)//初始化{int mid=(l+r)/2;col[now]=-1;if(l==r) return ;built(l,mid,now*2);built(mid+1,r,now*2+1);}void updata(int l,int r,int left,int right, int c,int now){int mid=(l+r)/2;if(left<=l&&r<=right){col[now]=c;return ;}if(l==r) return ;if(col[now]!=-1)//向下传递{col[now*2]=col[now*2+1]=col[now];col[now]=-1;}if(left<=mid) updata(l,mid,left,right,c,now*2);if(right>mid) updata(mid+1,r,left,right,c,now*2+1);}void query(int l,int r,int now){int mid=(l+r)/2;if(col[now]!=-1){if(col[now]!=last){cnt[col[now]]++;last=col[now];}return ;}if(l==r) {last=-1;return ;}//如果到了叶子节点且没有颜色,表示颜色断掉query(l,mid,now*2);query(mid+1,r,now*2+1);}int main(){while(~scanf("%d",&n)){built(0,16000,1);for(int i=1;i<=n;i++){int l,r,k;scanf("%d%d%d",&l,&r,&k);updata(0,16000,2*l,2*r,k,1);//区间加点,直接*2处理了}last=-1;memset(cnt,0,sizeof(cnt));query(0,16000,1);for(int i=0;i<=8000;i++){if(cnt[i]!=0){printf("%d %d\n",i,cnt[i]);}}printf("\n");}return 0;}