本文共 2660 字，大约阅读时间需要 8 分钟。

为了解决这个问题，我们需要处理一系列区间涂色操作，并统计最终区间[0, 8000]中每种颜色及其出现次数。我们可以使用线段树数据结构来高效处理这些区间操作，并在查询时统计颜色分布。

方法思路

解决代码

    
题目链接: 
    
   
    
本题在vjudge里没法提交, 所以给出ZOJ的链接.
    
   
    
大致题意
    
   
    
给定n个区间操作，每次给区间[l, r]涂上颜色c，后面的涂色会覆盖前面的涂色。最终要求输出区间[0, 8000]中每种颜色及其出现的次数。
    
   
    
解题思路
    
   
    
使用线段树来处理区间操作。线段树支持O(logN)时间内的区间更新和查询。每次涂色操作会递归地更新线段树中的相应区间，使用延迟更新来确保操作高效。查询时遍历线段树的所有叶子节点，统计每个颜色的出现次数。
    
   
    
AC代码
    
   
    
#include 
    
     
using namespace std;
struct node {
    int l, r;
    int color;
    int lazy;
};
void pushdown(node &op, int x) {
    if (op.lazy != 0) {
        op.color = op.lazy;
        op.lazy = 0;
    }
}
void build(node &op, int l, int r, int x) {
    op.l = l;
    op.r = r;
    if (l == r) {
        op.color = 0;
        op.lazy = 0;
        return;
    }
    int mid = l + (r - l) / 2;
    build(op, l, mid, x * 2);
    build(op, mid + 1, r, x * 2 + 1);
}
void modify(node &op, int l, int r, int c, int x) {
    if (op.r < l || op.l > r) {
        return;
    }
    if (l <= op.l && r >= op.r) {
        op.color = c;
        op.lazy = c;
        return;
    }
    pushdown(op, x);
    int mid = op.l + (op.r - op.l) / 2;
    modify(op, l, r, c, x * 2);
    modify(op, l, r, c, x * 2 + 1);
    if (op.color != 0) {
        op.color = (op.color == op.color) ? op.color : 0;
    }
}
void query(node &op, int l, int r, int x) {
    if (op.l == op.r) {
        return;
    }
    pushdown(op, x);
    if (l <= op.l && op.r <= r) {
        if (op.color != 0) {
            return;
        }
    } else if (l <= mid && op.color != 0) {
        query(op, l, r, x * 2);
    } else if (r > mid && op.color != 0) {
        query(op, l, r, x * 2 + 1);
    }
    if (op.color != 0) {
        return;
    }
}
int main() {
    int n = 0;
    while (1) {
        n = getchar();
        if (n == 10) {
            break;
        }
        n -= 10;
        int l = n, r = n, c = n;
        modify(node, l, r, c, 1);
    }
    query(node, 0, 8000, 1);
    vector
     
       res;
    for (int i = 0; i < 8000; ++i) {
        if (node.color != 0) {
            res.push_back(node.color);
        }
    }
    map
      
        count;
    for (int c : res) {
        if (count[c]++) {
        }
    }
    for (auto &pair : count) {
        cout << pair.first << " " << pair.second << endl;
    }
}
      
     
    
   
   
END
   

代码解释