线段树

统计区间数字个数

#include<bits/stdc++.h>
using namespace std;
#define CL(a,b) memset(a,b,sizeof(a))//简化代码
#define MAXN 100010
struct node
{
    int l,r,s;
} t[MAXN<<2];
int L,O,T;
int sum[33];//因为颜色数不多，可以用一个数组来装；1表示该区间有该颜色，0反之
 
void build(int l, int r, int i)
{
    t[i].l = l;
    t[i].r = r;
    t[i].s = 1;
    if(l == r) return ;
    int mid = (l+r)>>1;
    build(l, mid, i<<1);
    build(mid+1, r, i<<1|1);
}
 
void update(int l, int r, int m, int i)
{
    if(t[i].s == m) return ;
    if(t[i].l == l && t[i].r == r)
    {
        t[i].s = m;
        return ;
    }
    if(t[i].s != -1)
    {
        t[i<<1].s = t[i<<1|1].s = t[i].s;
        t[i].s = -1;
    }
    int mid = (t[i].l+t[i].r)>>1;
    if(l > mid) update(l, r, m, i<<1|1);
    else if(r <= mid) update(l, r, m, i<<1);
    else
    {
        update(l, mid, m, i<<1);
        update(mid+1, r, m, i<<1|1);
    }
}
 
void query(int l, int r, int i)
{
    if(t[i].s != -1)//如果纯色把该颜色标记
    {
        sum[t[i].s] = 1;
        return ;
    }
    else//否则继续查询子节点
    {
        int mid = (t[i].l+t[i].r)>>1;
        if(l > mid) query(l, r, i<<1|1);
        else if(r <= mid) query(l, r, i<<1);
        else
        {
            query(l, mid, i<<1);
            query(mid+1, r, i<<1|1);
        }
    }
}
 
int main()
{
    char ch;
    int a,b,c;
    while(scanf("%d%d%d",&L,&T,&O)==3)
    {
        build(1, L, 1);
        while(O--)
        {
            getchar();
            scanf("%c",&ch);
            if(ch == 'C')
            {
                scanf("%d%d%d",&a,&b,&c);
                update(a, b, c, 1);
            }
            int ans = 0;
            if(ch == 'P')
            {
                CL(sum, 0);//每次查询之前清零
                scanf("%d%d",&a,&b);
                query(a, b, 1);
                for(int i=1; i<=T; i++)//统计出现过的颜色数
                    if(sum[i]) ans++;
                printf("%d
",ans);
            }
        }
    }
    return 0;
}