ZOJ - 1610 Count the Colors（模拟，线段树）

ZOJ - 1610 Count the Colors（模拟，线段树）

直接模拟

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 8010;
int a[N], color[N];
int main()
{
    int n;while(scanf("%d",&n)!=EOF){
    memset(color,0,sizeof color);memset(a,-1,sizeof a);int maxr=0,minl=1e9;while(n--){
    int l,r,c;scanf("%d%d%d",&l,&r,&c);maxr=max(maxr,r);minl=min(minl,l);for(int i=l+1;i<=r;i++) a[i]=c;}for(int i=minl+1;i<=maxr;i++)if(a[i]!=a[i-1])color[a[i]]++;for(int i=0;i<N-5;i++)if(color[i])printf("%d %d\n",i,color[i]);puts("");}return 0;
}

线段树

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 8010;struct Node
{
    int l,r,lazy;
}tr[N<<2];
int cnt[N];void build(int u,int l,int r)
{
    if(l==r) tr[u]=(Node){
    l,l,-1};else{
    tr[u]=(Node){
    l,r,-1};int mid=(l+r)>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);}
}void pushdown(int u)
{
    Node &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];if(~root.lazy) left.lazy=right.lazy=root.lazy;root.lazy=-1;
}void modify(int u,int l,int r,int v)
{
    if(tr[u].l>=l&&tr[u].r<=r) tr[u].lazy=v;else{
    pushdown(u);int mid=(tr[u].l+tr[u].r)>>1;if(l<=mid) modify(u<<1,l,r,v);if(r>mid) modify(u<<1|1,l,r,v);}
}int query(int u,int l,int r)
{
    if(tr[u].l==tr[u].r) return tr[u].lazy;int mid=(tr[u].l+tr[u].r)>>1;pushdown(u);if (l<=mid) return query(u<<1,l,r);if (r>mid) return query(u<<1|1,l,r);return -1;
}int main()
{
    int n;while(scanf("%d",&n)!=EOF){
    memset(cnt, 0, sizeof cnt);build(1,1,N-5);for(int i=0;i<n;i++){
    int l,r,c;scanf("%d%d%d",&l,&r,&c); modify(1,l+1,r,c);}int pre=-1;for(int i=1;i<=N-5;i++){
    int t=query(1,i,i);if(t==pre) continue;cnt[t]++;pre=t;}for(int i=0;i<=N-5;i++)if(cnt[i])printf("%d %d\n",i,cnt[i]);printf("\n");}return 0;
}