线段树

acm

# include<iostream>
# include<string>
# include<algorithm>
#include<numeric>
#include <vector>
#include <queue>
using namespace std;
int countColors[40] = { 0 };
// 创建一个树的节点数组
struct Node {
    int l, r;
    int flag;
}tree[1000000];
//建树
void BuildTree(int node, int start, int end) {
    int mid = (end + start) / 2;
    tree[node].l = start;
    tree[node].r = end;
    tree[node].flag = 1;                         // 初始化颜色为1
    if (start != end) {                          // 如果不是节点，递归建树 
        BuildTree(2 * node, start, mid);         
        BuildTree(2 * node + 1, mid + 1, end);
    }
}
//对区间[start, end]进行染色
void colorTree(int node, int start, int end, int color) {
    int mid = (tree[node].l + tree[node].r) / 2;                 // 左右节点区间为[start, mid]和[mid+1, end]
    if (tree[node].l >= start && tree[node].r <= end)           //染色区间包含整个节点区间
        tree[node].flag = color;
    else
    {
        //if (tree[node].flag != 0)                 //对左右节点区间的color初始化？
            //tree[2 * node].flag = tree[2 * node + 1].flag = tree[node].flag;
        if (start <= mid)
            colorTree(2 * node, start, end, color);
        if (end > mid)
            colorTree(2 * node + 1, start, end, color);
        if (tree[2 * node].flag == tree[2 * node + 1].flag)           //染色完之后对根节点区间color重新赋值
            tree[node].flag = tree[2 * node].flag;     
        else
            tree[node].flag = 0;
    }
}
// 对区间[start, end]进行查询
void que(int node, int start, int end) {
    int mid = (tree[node].l + tree[node].r) / 2;
    if (tree[node].flag != 0)
        countColors[tree[node].flag] = 1;
    else
    {
        if (start <= mid)
            que(2 * node, start, end);
        if (end > mid)
            que(2 * node + 1, start, end);
        //if (tree[2 * node].flag == tree[2 * node + 1].flag)   //有啥用？
            //tree[node].flag = tree[2 * node].flag;
        //else
            //tree[node].flag = 0; 
    }
}
int main() {
    //输入节点数，颜色数量，操作次数
    int L, T, o;
    int a, b, c;
    char x;
    cin >> L >> T >> o;
    BuildTree(1, 1, L);
    for (int i = 0; i < o; i++) {
        cin >> x;
        // 区间染色
        if (x == 'C') {
            cin >> a >> b >> c;
            colorTree(1, a, b, c);
        }
        // 区间颜色查询
        if (x == 'P') {
            cin >> a >> b;
            memset(countColors, 0, sizeof(countColors));
            que(1, a, b);
            int ans = 0;
            for (int j = 1; j <= T; j++)
                if (countColors[j] != 0)ans++;
            cout << ans << endl;
        }
    }
    system("pause");
    return 0;
}