HDU6183 Color it【线段树】

题意：一个二维平面，三种操作，1.清空所有点，2.在(x,y)上加一种颜色（不是覆盖），3.查询区域1~x,y1~y2这个二维区域内有几种颜色

思路：考虑给每种颜色建一颗线段树，维护的是一段y(几行)内这种颜色出现的最小的x，查询：y1-y2内的最小值比x小，那么区域内有这种颜色。由于空间的限制，需要动态开点。还可以把坐标离散化。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1.5e5+10;
struct data
{
	int l,r,num;
}node[maxn*30];

int p[maxn][4],tot;
int row,con,root[55],flag;
vector<int> v1,v2;

int newnode()
{
	node[tot].num = 0x3f3f3f3f;
	node[tot].l = node[tot].r = -1;
	return tot++;	
}

void up(int ny,int x,int y,int &cnt,int val)
{
	if(cnt == -1) cnt = newnode();
	node[cnt].num = min(node[cnt].num,val);
	if(x == y) return;
	int mid = (x+y) / 2;
	if(ny <= mid)
		up(ny,x,mid,node[cnt].l,val);
	else
		up(ny,mid+1,y,node[cnt].r,val);
}

void fid(int qx,int qy,int x,int y,int cnt,int k)
{
	if(flag) return;
	if((node[cnt].l == -1 && node[cnt].r == -1) || (qx == x && qy ==y))
	{
		if(node[cnt].num <= k)
			flag = 1;
		return;
	}
	int mid = (x+y) / 2;
	if(qy <= mid)
	{
		if(node[cnt].l != -1)
			fid(qx,qy,x,mid,node[cnt].l,k);
	}	
	else if(qx >= mid+1)
	{
		if(node[cnt].r != -1)
			fid(qx,qy,mid+1,y,node[cnt].r,k);
	}	
	else
    {
    	if(node[cnt].l != -1)
        	fid(qx,mid,x,mid,node[cnt].l,k);
        if(node[cnt].r != -1)
			fid(mid+1,qy,mid+1,y,node[cnt].r,k);
    }
}

int qurey(int x2,int y1,int y2)
{
    int num = 0;
    for(int i = 0; i <= 50; i++)
    {
    	flag = 0;
		fid(y1,y2,1,row,root[i],x2);
    	num += flag;
	}
    return num;
}

int main()
{
    int op,t,en = 0;
    while(scanf("%d",&op)!=EOF && op != 3)
    {
        t = 1;
        if(op != 0)
        {
            p[1][0] = op;
            scanf("%d%d%d",&p[1][1],&p[1][2],&p[1][3]);
            t++;
        }
        while(scanf("%d",&op)!=EOF)
        {
            if(op == 3)
            {
                en = 1;
                break;
            }
            if(op != 0)
            {
                p[t][0] = op;
                scanf("%d%d%d",&p[t][1],&p[t][2],&p[t][3]);
                t++;
            }
            else
                break;
        }
        v1.clear();
        v2.clear();
        for(int i = 1; i < t; i++)
        {
            if(p[i][0] == 1)
            {
                v1.push_back(p[i][1]);
                v2.push_back(p[i][2]);
            }
            else
            {
                v1.push_back(p[i][1]);
                v2.push_back(p[i][2]);
                v2.push_back(p[i][3]);
            }
        }
        sort(v1.begin(),v1.end());
        sort(v2.begin(),v2.end());
        v1.erase(unique(v1.begin(),v1.end()),v1.end());
        v2.erase(unique(v2.begin(),v2.end()),v2.end());
        con = v1.size();
        row = v2.size();
        tot = 0;
        for(int i = 0; i <= 50; i++)
        {
            root[i] = newnode();
        }
        for(int i = 1; i < t; i++)
        {
            if(p[i][0] == 1)
            {
                int x1 = lower_bound(v1.begin(),v1.end(),p[i][1]) - v1.begin() + 1;
                int y1 = lower_bound(v2.begin(),v2.end(),p[i][2]) - v2.begin() + 1;
                up(y1,1,row,root[p[i][3]],x1);
            }
            else
            {
                int x2 = lower_bound(v1.begin(),v1.end(),p[i][1]) - v1.begin() + 1;
                int y1 = lower_bound(v2.begin(),v2.end(),p[i][2]) - v2.begin() + 1;
                int y2 = lower_bound(v2.begin(),v2.end(),p[i][3]) - v2.begin() + 1;
                printf("%d\n",qurey(x2,y1,y2));
            }
        }
        if(en)
            break;
    }
    return 0;
}