HDU 6183 Color it 线段树

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6183

题意：

有四种操作：
0:清除所有点
1 x y c : 给点(x, y)添加一种颜色c（颜色不会覆盖）
2 x y1 y2 : 在(0, y1)与(x, y2)所围成的矩形里有多少种颜色
3 : 程序结束

解法：

颜色最多51种。我们就建51棵线段树。每个线段树按y轴建树，每个结点的值是在范围内的最小的x值，这题最关键的就是看到是x轴是查1-x

队友的CDQ+线段树因为写错了一句话，重现赛现场一直WA，我最后关头直接这样暴力过了。。。

#include <bits/stdc++.h>

using namespace std;

const int maxm = 3000010;

int tot, l[maxm], r[maxm], v[maxm], T[51];

void update(int &x,int L,int R,int pos,int val)

{

    if(!x)

    {

        x = ++tot;

        v[x] = val;

    }

    if(v[x]>val) v[x] = val;

    if(L==R)return;

    int mid=(L+R)>>1;

    if(pos<=mid) update(l[x],L,mid,pos,val);

    else update(r[x],mid+1,R,pos,val);

}

int flag;

int X;

int c, d;

void query(int x, int L, int R)

{

    if(flag||!x) return;

    if(c<=L && R<=d)

    {

        if(v[x]<=X)flag=1;

        return;

    }

    int mid=(L+R)>>1;

    if(c<=mid) query(l[x],L,mid);

    if(d>mid) query(r[x],mid+1,R);

}

int main()

{

    for(int i=0; i<=50; i++)

    {

        T[i]=0;

    }

    while(1)

    {

        int op;

        scanf("%d", &op);

        if(op==3)return 0;

        if(op==0)

        {

            for(int i=1; i<=tot; i++)l[i]=r[i]=0;

            for(int i=0; i<=50; i++)T[i]=0;

            tot=0;

        }

        if(op==1)

        {

            int x, y, c;

            scanf("%d %d %d", &x,&y,&c);

            update(T[c], 1, 1000000, y, x);

        }

        if(op==2)

        {

            scanf("%d %d %d", &X,&c,&d);

            int ans=0;

            for(int i=0; i<=50; i++)

            {

                flag=0;

                query(T[i], 1, 1000000);

                if(flag) ans++;

            }

            printf("%d\n",ans);

        }

    }

    return 0;

}

巴特西

HDU 6183 Color it 线段树

最新文章

热门文章