题目传送门
Count the Colors
题目大意
一面长为8000的墙，给出n次操作，每次给出x，y，z，代表在x~y区间将墙粉刷成颜色z，后面的粉刷可以覆盖之前的 求最后墙上不同的颜色的种数和每种颜色非连续的段数
思路
很明显的区间修改，单点查询 注意点： 多组输入 最后换行，不然会PE 显然区间是左开右闭的 编号从0开始代表颜色可以为0
AC Code
#include<bits/stdc++.h>
using namespace std
;
#define debug(a) cout<<#a<<"="<<a<<endl;
const int N
=8009;
int n
, l
, r
, c
;
int ans
[N
], colour
[N
], idx
;
struct segtree
{
int l
, r
;
int colour
;
}tr
[N
<<2];
inline int read()
{
int ans
=0;
char last
=' ',ch
=getchar();
while(ch
<'0'||ch
>'9') last
=ch
,ch
=getchar();
while(ch
>='0'&&ch
<='9') ans
=ans
*10+ch
-'0',ch
=getchar();
if(last
=='-') ans
=-ans
;
return ans
;
}
inline int lc(int p
) {return p
<<1;}
inline int rc(int p
) {return p
<<1|1;}
inline void build(int p
, int l
, int r
){
tr
[p
].l
=l
, tr
[p
].r
=r
;
tr
[p
].colour
=-1;
if(l
==r
) return ;
int mid
=(l
+r
)>>1;
build(lc(p
), l
, mid
);
build(rc(p
), mid
+1, r
);
}
inline void f(int p
, int k
){
tr
[p
].colour
=k
;
}
inline void push_down(int p
){
f(lc(p
), tr
[p
].colour
);
f(rc(p
), tr
[p
].colour
);
tr
[p
].colour
=-1;
}
inline void updata(int p
, int l
, int r
, int x
, int y
, int k
){
if(x
>r
|| y
<l
) return ;
if(l
<=x
&& y
<=r
){
tr
[p
].colour
=k
;
return ;
}
if(tr
[p
].colour
!=-1) push_down(p
);
int mid
=(x
+y
)>>1;
updata(lc(p
), l
, r
, x
, mid
, k
);
updata(rc(p
), l
, r
, mid
+1, y
, k
);
}
inline void query(int p
, int x
, int y
){
if(x
==y
){
colour
[idx
++]=tr
[p
].colour
;
return ;
}
int mid
=(x
+y
)>>1;
if(tr
[p
].colour
!=-1) push_down(p
);
query(lc(p
), x
, mid
);
query(rc(p
), mid
+1, y
);
}
int main(){
while(~scanf("%d", &n
)){
build(1,0,8000);
idx
=0;
memset(colour
, -1, sizeof(colour
));
memset(ans
, 0, sizeof(ans
));
for(int i
=1; i
<=n
; i
++){
l
=read(); r
=read(); c
=read();
updata(1,l
,r
-1,0,8000,c
);
}
query(1,0,8000);
for(int i
=0; i
<idx
; i
++){
if(colour
[i
]!=colour
[i
+1] && colour
[i
]!=-1){
ans
[colour
[i
]]++;
}
}
for(int i
=0; i
<=8000; i
++) if(ans
[i
]) cout
<<i
<<" "<<ans
[i
]<<endl
;
cout
<<endl
;
}
return 0;
}
