HDU - 6183 Color it（线段树）

点我看题

题意：有下面四个操作

0：情况所有数据

1 x y c：给点（x，y）添加一个颜色c

2 x y1 y2：问所有满足1<=a<=x&&y1<=b<=y2条件的点（a，b）共有多少中颜色

3：退出程序

分析：首先要仔细读题，题目说1 x y c是给（x，y）这个点加一个颜色c,也就是说一个点可以有多种颜色。

最多有51种颜色，那我们就根据每种颜色来建线段树，共51棵线段树，每颗线段树结点保存的值是当前区间的最小x（因为我们的x选择范围在[1,x]

（有点像二维线段树…

参考代码：

/*线段树*/
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn = 1e6+10;
//线段树
int tot;//结点数
int s[55];//根据颜色来建线段树，最多51种颜色，所有最多也只会建50棵线段树
int lson[maxn],rson[maxn],v[maxn];//左右儿子，每个结点对应范围内的最小ｘ值
int flag;

void Update( int &k, int l, int r, int y, int x)
{
    if( !k)//以前没出现过这种颜色
    {
        k = ++tot;
        lson[k] = rson[k] = 0;
        v[k] = x;
    }
    v[k] = min(v[k],x);
    if( l == r)
        return;
    int mid = (l+r)>>1;
    if( y <= mid)
        Update(lson[k],l,mid,y,x);
    else
        Update(rson[k],mid+1,r,y,x);
}

void Query( int k, int l, int r, int L, int R, int x)
{
    if( flag || !k)
        return;
    if( L <= l && R >= r)
    {
        if( v[k] <= x)//[1,x]
            flag = 1;
        return;
    }
    int mid = (l+r)>>1;
    if( R <= mid)
        Query(lson[k],l,mid,L,R,x);
    else if( L > mid)
        Query(rson[k],mid+1,r,L,R,x);
    else
    {
        Query(lson[k],l,mid,L,mid,x);
        Query(rson[k],mid+1,r,mid+1,R,x);
    }
}

int main()
{
    int op;
    while( ~scanf("%d",&op))
    {
        if( op == 0)
        {
            tot = 0;
            mem(s,0);
        }
        else if( op == 1)
        {
            int x,y,c;
            scanf("%d%d%d",&x,&y,&c);
            Update(s[c],1,1000000,y,x);
        }
        else if( op == 2)
        {
            int x,y1,y2;
            scanf("%d%d%d",&x,&y1,&y2);
            int ans = 0;
            for( int i = 0; i <= 51; i++)
            {
                flag = 0;
                Query(s[i],1,1000000,y1,y2,x);
                if( flag)
                    ans++;
            }
            printf("%d\n",ans);
        }
        else if( op == 3)
            break;
    }

    return 0;
}