HDU 6183 Color it（线段树+思维+高端的优化技巧）

Bertha 。 2022-06-09 13:19 160阅读 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 0 : clear all the points.  
  
1 1 x x y y c c : add a point which color is c c at point (x,y) (x,y).  
  
2 2 x x y1 y1 y2 y2 : count how many different colors in the square (1,y1) (1,y1) and (x,y2) (x,y2). That is to say, if there is a point (a,b) (a,b) colored c c, that 1≤a≤x 1≤a≤x and y1≤b≤y2 y1≤b≤y2, then the color c c should be counted.  
  
3 3 : 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 1≤x,y≤106,0≤c≤50), '2 x y1 y2' ( 1≤x,y1,y2≤106 1≤x,y1,y2≤106 ) or '3'.  
  
x,y,c,y1,y2 x,y,c,y1,y2 are all integers.  
  
Assume the last operation is 3 and it appears only once.  
  
There are at most 150000 150000 continuous operations of operation 1 and operation 2.  
  
There are at most 10 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

题解：

题意：

操作1 x y c 就是在x，y点涂上c这种颜色，操作 2 x y1 y2表示从矩形左下角（1，y1）到矩形右上角（x，y2)范围内有多少种颜色，0 表示清空，3表示退出

思路：

比赛的时候的思路是50棵二维线段树+离散化。。。然后果断放弃了。。。补题的时候也完全没思路，50棵二维线段树也太难操作了，也会爆内存，orz只好搜大佬题解

大佬题解：[http://blog.csdn.net/jaihk662/article/details/77750894][http_blog.csdn.net_jaihk662_article_details_77750894]

看完了大佬题解原来可以用一维的线段树做，根据思路还以为自己凭自己的理解可以自己做出来。。。然后又失败了orz，因为开t\[51\]\[1000005\*4\]的内存太醉了，系统不允许，估计也是爆炸，这个也要优化。。然后就老老实实根据大佬的博客打了一遍qwq。。哭晕

这题做法就是因为每次那个矩阵横坐标范围都是1开始，根据这个性质我们只要把y轴做成一颗线段树，保存距离y轴最近的那个点的横坐标就行了，然后不停得更新，询问的时候就询问y1，y2范围内离y轴最近的那个点的横坐标，与x做比较，如果比x小就说明该颜色在区域内，颜色++，否则就说明不在

关于线段树的优化也是很厉害。。。自己完全不会，只要保存每一组颜色的最前面那个的横坐标就好了，如果在y轴范围更新一下，因为这个题目没说会被覆盖，直接加上和

照着打了一遍的代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define eps 1e-7
    #define lson k*2
    #define rson k*2+1
    const int maxn=1000005;
    int L[maxn],R[maxn],v[maxn];
    int tag,ll,rr,xx,cent;
    int root[55];
    void update(int &k,int l,int r,int a,int b)
    {
        int m;
        if(k==0)
        {
            k=++cent;
            v[k]=b;
        }
        if(v[k]>b)
            v[k]=b;
        if(l==r)
            return;
        m=(l+r)/2;
        if(a<=m)
            update(L[k],l,m,a,b);
        else
            update(R[k],m+1,r,a,b);
    }
    void query(int x,int l,int r)
    {
        int m;
        if(tag||x==0)
            return;
        if(l>=ll&&r<=rr)
        {
            if(v[x]<=xx)
                tag=1;
            return;
        }
        m=(l+r)/2;
        if(ll<=m)
            query(L[x],l,m);
        if(rr>=m+1)
            query(R[x],m+1,r);
    }
    int main()
    {
        int i,ans,x,y,d,c;
        while(1)
        {
            scanf("%d",&d);
            if(d==3)
                break;
            else if(d==0)
            {
                for(i=0;i<=cent;i++)
                    L[i]=R[i]=0;
                memset(root,0,sizeof(root));
                cent=0;
            }
            else if(d==1)
            {
                scanf("%d%d%d",&x,&y,&c);
                update(root[c],1,1000000,y,x);
            }
            else if(d==2)
            {
                scanf("%d%d%d",&xx,&ll,&rr);
                ans=0;
                for(i=0;i<=50;i++)
                {
                    tag=0;
                    query(root[i],1,1000000);
                    ans+=tag;
                }
                printf("%d\n",ans);
            }
        }
        return 0;
    }

[http_blog.csdn.net_jaihk662_article_details_77750894]: http://blog.csdn.net/jaihk662/article/details/77750894