Count the Colors

题目

在[0,8000]区间进行N次区间染色，后涂的色可以覆盖之前涂的色，问N次染色之后，能看见的颜***间数量各是多少？

分析

其实这题区间覆盖这部分很好做，不需要离散化，因为只有8000长度的区间。我们要注意的是，需要将区间改成左开右闭的形式，比如给[0,2]，[2,4]区间染色，要变成给[1,2],[3,4]染色。这样才不会有冲突。
然后N次染色之后，将有色的区间进行统计一下，能合并的就合并。然后输出就可以了

AC 代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <map>
#include <cstring>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn  = 8e3+10;
int M;
struct node{
    int l,r,tag;
}tr[4*maxn];
vector<pii> h[maxn];
map<int,int> mp;
void pushup(int u){
    node &fa = tr[u],&L = tr[u*2],&R = tr[u*2+1];
    if(L.tag == R.tag){
        fa.tag = L.tag;
    }else{
        fa.tag = -1;
    }
}
void pushdown(int u){
    node &fa = tr[u],&L = tr[u*2],&R = tr[u*2+1];
    if(fa.tag > 0){
        L.tag = fa.tag;
        R.tag = fa.tag;
    }
}
void build(int u,int l,int r){
    tr[u] = {l,r};
    if(l != r){
        int mid = l+r>>1;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
    }
}
void modify(int u,int l,int r,int tag){
    if(tr[u].l>=l && tr[u].r<=r){
        tr[u].tag = tag;
    }else{
        pushdown(u);
        int mid = (tr[u].l+tr[u].r)>>1;
        if(l<=mid) modify(u*2,l,r,tag);
        if(r>mid) modify(u*2+1,l,r,tag);
        pushup(u);
    }
}
void query(int u,int l,int r){
    if(tr[u].tag == 0) return ;
    if(tr[u].tag>0){
        h[tr[u].tag].emplace_back(tr[u].l,tr[u].r);
        //cout<<tr[u].l<<" "<<tr[u].r<<" "<<tr[u].tag<<endl;
    }else{
        pushdown(u);
        query(u*2,l,r);
        query(u*2+1,l,r);
        pushup(u);
    }
}

void fun(){
    for(int i  = 1;i<=8000;i++) {
        sort(h[i].begin(),h[i].end());
        int l = -1,r = -1,cnt = -1;
        for(auto p:h[i]){ //合并区间，并统计
            int x = p.X,y = p.Y;
            if(x>r+1){
                cnt ++;
                l = x;
                r = y;
            }else{
                r = y;
            }
        }
        if(h[i].size()) mp[i] = cnt+1;
    }
    for(auto p:mp){
        printf("%d %d\n",p.X-1,p.Y);//前面+1了，现在-1
    }
    puts("");
}
int main(){
    while(~scanf("%d",&M)){
        memset(tr,0,sizeof tr);
        mp.clear();
        for(int i = 1;i<=8000;i++) h[i].clear();
        build(1,1,8000);
        int a,b,c;
        while(M--){
            scanf("%d%d%d",&a,&b,&c);
            modify(1,a+1,b,c+1);//+1是因为我想从1开始
        }
        query(1,1,8000);
        fun();
    }
    return 0;
}