Count the Colors ZOJ - 1610

题目链接

题意：

给定n个区间[ l, r ]和颜色c, 每次给[l, r]涂上c这个颜色. 后面的涂色会覆盖之前的涂色.

最后要求输出区间[0, 8000]中每种颜色及其出现的次数, 如果该颜色没有出现过则不输出.

思路：典型的线段树区间染色问题，一般这种题在（l , r) 区间有问题，比如这题我们正常做法就是把区间变为点，但是我们注意到 我们染色[ 1 , 2 ] 和 [ 3?, 4?] 后? [ 2, 3?] 这一段我们并没有染色，而我们当点处理这一段会被染色，还有一个问题就是染色区间为[ 0,8000 ]， 0在线段树里我们并不能维护，所以我们在处理[ l , r ]?时右移 l ，变为[ l +1 , r ]，这样问题都解决了。，我们可以用一个 pre 记录 前面的颜色，

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define Yshanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 2e4 + 10, M = 1010, inf = 0x3f3f3f3f, mod = 1e9 + 7, P = 13331;
const double eps = 1e-8;
int n, pre;
int ans[N];
int color[N];
void pushdown(int u)
{
    color[u << 1] = color[u];
    color[u << 1 | 1] = color[u];
    color[u] = -1;
}
void modify(int u, int l, int r, int L, int R, int c)
{
    if (l >= L && r <= R)
    {
        color[u] = c;
        return;
    }
    if (color[u] != -1)
        pushdown(u);
    int mid = l + r >> 1;
    if (L <= mid)
        modify(u << 1, l, mid, L, R, c);
    if (R > mid)
        modify(u << 1 | 1, mid + 1, r, L, R, c);
}
void query(int u, int l, int r)//这种查询方式一定会查到底才行
{
    if (l == r)
    {
        if (color[u] != -1 && pre != color[u])
        {
            ans[color[u]]++;
        }
        pre = color[u];
        return;
    }
    if (color[u] != -1)
        pushdown(u);
    int mid = l + r >> 1;
    query(u << 1, l, mid); // 就和dfs一样，先跑左子树，这样就相当于从左向右跑的区间
    query(u << 1 | 1, mid + 1, r);
}

void query(int u, int l, int r)//而这一种相当于利用了懒标记的性质，
{
    if (color[u] != pre&&color[u]!=-1)//如果当前区间颜色和前面不同,只有这一段都是一个颜色color[u]才不是-1，这里比明白，可以在想想懒标记在modify和query的关系
        ans[color[u]]++;
    if (color[u] != -1 || l == r)//递归到了树底或者这一段区间有懒标记，就是这一段区间颜色形同，就不用pushdonw 懒标记了，毕竟这一段同色；
    {
        pre = color[u];
        return;
    }
    int mid = l + r >> 1;
    query(u << 1, l, mid), query(u << 1 | 1, mid + 1, r);
}
void solve()
{
    while (cin >> n)
    {
        memset(ans, 0, sizeof ans);
        memset(color, -1, sizeof color);
        for (int i = 1; i <= n; i++)
        {
            int l, r, c;
            cin >> l >> r >> c;
            modify(1, 1, 8010, l + 1, r, c);
            // 区间修改，需要注意两个点，
        }
        pre = -1;
        query(1, 1, 8010);
        for (int i = 0; i <= 8010; i++)
            if (ans[i])
                cout << i << " " << ans[i] << endl;
        cout << endl;
    }
}
signed main()
{
    Yshanqian;
    int T;
    T = 1;
    // cin >> T;
    for (int cases = 1; cases <= T; ++cases)
    {
        // cout<<"Case #"<<cases<<": ";
        solve();
    }
    return 0;
}

?