HDU6183(线段树)

╰+哭是因爲堅強的太久メ 2021-11-01 10:54 355阅读 0赞

Do you like painting? Little D doesn’t like painting, especially messy color paintings. Now Little B is painting. To prevent him from drawing messy painting, Little D asks you to write a program to maintain following operations. The specific format of these operations is as follows.

0 : clear all the points.

1 x y c : add a point which color is c at point (x,y).

2 x y1 y2 : count how many different colors in the square (1,y1) and (x,y2). That is to say, if there is a point (a,b) colored c, that 1≤a≤x and y1≤b≤y2, then the color c should be counted.

exit.  
Input  
The input contains many lines.  
Each line contains a operation. It may be ‘0’, ‘1 x y c’ ( 1≤x,y≤106,0≤c≤50 ), ‘2 x y1 y2’ (1≤x,y1,y2≤106 ) or ‘3’.

x,y,c,y1,y2 are all integers.

Assume the last operation is 3 and it appears only once.

There are at most 150000 continuous operations of operation 1 and operation 2.

There are at most 10  
operation 0.

Output  
For each operation 2, output an integer means the answer .  
Sample Input  
0  
1 1000000 1000000 50  
1 1000000 999999 0  
1 1000000 999999 0  
1 1000000 1000000 49  
2 1000000 1000000 1000000  
2 1000000 1 1000000  
0  
1 1 1 1  
2 1 1 2  
1 1 2 2  
2 1 1 2  
1 2 2 2  
2 1 1 2  
1 2 1 3  
2 2 1 2  
2 10 1 2  
2 10 2 2  
0  
1 1 1 1  
2 1 1 1  
1 1 2 1  
2 1 1 2  
1 2 2 1  
2 1 1 2  
1 2 1 1  
2 2 1 2  
2 10 1 2  
2 10 2 2  
3

Sample Output  
2  
3  
1  
2  
2  
3  
3  
1  
1  
1  
1  
1  
1  
1

参考博客：[https://blog.csdn.net/creatorx/article/details/77771528][https_blog.csdn.net_creatorx_article_details_77771528]  
分析：  
做题还是要善于观察题目的数据范围。  
像这个题，我们可以看到c的范围是0到50.这是一个很有用的信息。

所以我们可以对每个颜色都建立一颗线段树。并且这颗线段树是按y坐标建的。  
不过，如果50颗线段树肯定爆空间，所以采用动态开点的方式。  
我们在每颗线段树的结点里增加一个min\_val属性，维护这一段区间的最小值。  
那么我们在每次查询的时候，只要在y1-y2这个区间里面找到最小值，并将最小值与给出的x相比。如果比x值小，那就证明了在这个颜色的树里面有一个结点的值是在（1<= val<=x && y1<= val<= y2）这个范围里面的。

代码须多敲，又是一次wa了重敲的经历。555

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    #define INF 1000000 + 10
    
    struct Node
    {
        int l,r;
        int min_val;
        int lson,rson;
        Node()
        {
            min_val = INF;
            lson = rson = 0;
            l = r = 0;
        }
    } node[INF << 2];
    
    int top;
    int judge;
    int root[51];
    
    void init()
    {
        for(int i = 0; i <= 50; i ++) root[i] = 0;
        top = 0;//初始值要全都赋值到
        for(int i = 0; i < INF << 2; i ++)
        {
            node[i].l = node[i].r = node[i].lson = node[i].rson = 0;
            node[i].min_val = INF;
        }
    }
    
    void Update(int &id,int l,int r,int x,int val)
    {
        if(id == 0)
            id = ++ top;
        node[id].l = l;
        node[id].r = r;
        if(l == r)
        {
            node[id].min_val = min(node[id].min_val,val);
            //printf("l = %d r = %d\n",l,r);
            return ;
        }
        int mid = (l + r) >> 1;
        if(x <= mid)
        {
            if(node[id].lson == 0)
                node[id].lson = ++ top;
            Update(node[id].lson,l,mid,x,val);
        }
        else
        {
            if(node[id].rson == 0)
                node[id].rson = ++ top;
            Update(node[id].rson,mid + 1,r,x,val);
        }
        node[id].min_val = min(node[node[id].lson].min_val,node[node[id].rson].min_val);
    }
    
    void Query(int id,int l,int r,int x)
    {
        //printf("id = %d l = %d r = %d\n",id,l,r);
        if(id == 0 || judge == 1)
            return ;
        int L = node[id].l;
        int R = node[id].r;
       // printf("L = %d R = %d\n",L,R);
        if(l <= L && r >= R)
        {
            if(node[id].min_val <= x)
                judge = 1;
            return ;
        }
        int mid = (L + R) >> 1;
        if(l <= mid)
            Query(node[id].lson,l,r,x);
        if(r > mid)
            Query(node[id].rson,l,r,x);
    }
    
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            if(n == 3)
                return 0;
            if(n == 0)
                init();
            if(n == 1)
            {
                int x,y,c;
                scanf("%d%d%d",&x,&y,&c);
                Update(root[c],1,1e6,y,x);
            }
            if(n == 2)
            {
                int x,y1,y2;
                scanf("%d%d%d",&x,&y1,&y2);
                int ans = 0;
                for(int i = 0; i <= 50; i ++)
                {
                    judge = 0;
                    Query(root[i],y1,y2,x);
                    if(judge == 1)
                        ans ++;
                }
                printf("%d\n",ans);
            }
        }
    }

[https_blog.csdn.net_creatorx_article_details_77771528]: https://blog.csdn.net/creatorx/article/details/77771528