acdream 1725 哗啦啦的小彭玉染色问题离散化并查集

哗啦啦的小彭玉染色问题

Time Limit: 1 Sec Memory Limit: 256 MB

题目连接

http://acdream.info/problem?pid=1725

Description

哗啦啦，哗啦啦~

小彭玉很开心，拿着一堆海报就开始宣传明天要开始的哗啦啦大会了~

小彭玉很可爱，他的海报都是五颜六色的~

哗啦啦，哗啦啦~

小彭玉在一个巨大的宣传栏上贴了一大堆海报！

“真是好看呢！”，唐老师说道。

唐老师这时，就想出了一个题目，“这面宣传栏，最后能看见多少颜色呢？”

狗哥噗呲一笑，“这题太简单了！”

那你们会吗？

注意啦：后面贴的海报是会覆盖先前贴的~

Input

第一行，n,m,c，表示宣传栏有n行，m列，一开始颜色是c

第二行, k，表示小彭玉一共贴了k张海报

接下来k行 x1i,y1i,x2i,y2i,ci,ti 六个字母，表示小彭玉在ti的时间，在贴上左下角坐标为（x1i,y1i），右上角坐标为（x2i,y2i），颜色为ci的海报

数据保证每一时间，小彭玉最多贴一张海报~

数据范围：

1<=n<2147483647 1<=m<2147483647 1<=c<2147483647

0<=k<=1000

1<=x1i<=n,1<=y1i<=m,1<=x2i<=n,1<=y2i<=n,1<=ci<2147483647

Output

输出一个整数，表示有多少颜色能够被看见

Sample Input

3 3 1
4
3 3 3 3 5 3
2 1 2 3 3 1
1 1 1 1 1 2
2 2 3 3 2 4

Sample Output

HINT

样例之后，宣传栏变成了：

1 2 2
1 2 2
1 3 1

所以颜色总共有3种

题意

题解：

离散之后，并查集优化一下就好了~

然后直接乱搞

http://pan.baidu.com/s/1sjoLGxn

代码：

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 4005
#define mod 10007
#define eps 1e-9
int Num;
char CH[20];
//const int inf=0x7fffffff;   //§ß§é§à§é¨f§³
const int inf=0x3f3f3f3f;
/*

inline void P(int x)
{
    Num=0;if(!x){putchar('0');puts("");return;}
    while(x>0)CH[++Num]=x%10,x/=10;
    while(Num)putchar(CH[Num--]+48);
    puts("");
}
*/
inline ll read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void P(int x)
{
    Num=0;if(!x){putchar('0');puts("");return;}
    while(x>0)CH[++Num]=x%10,x/=10;
    while(Num)putchar(CH[Num--]+48);
    puts("");
}
//**************************************************************************************

struct node
{
    int x1,y1,x2,y2,t,c;
};
int n,m,c;
int k;
node a[maxn];
vector<int> q1;
vector<int> q2;
map<int,int> H1;
map<int,int> H2;
int fa[2010][2010];
int mp[2010][2010];
map<int,int> flag;
int ans;

bool cmp(node b,node c)
{
    return b.t>c.t;
}

int fi(int x,int y)
{
    if(y!=fa[x][y])
        fa[x][y]=fi(x,fa[x][y]);
    return fa[x][y];
}

int main()
{
    scanf("%d%d%d",&n,&m,&c);
    q1.push_back(n);
    q2.push_back(m);
    q1.push_back(1);
    q2.push_back(1);
    scanf("%d",&k);
    for(int i=0;i<k;i++)
    {
        scanf("%d%d%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&a[i].c,&a[i].t);
        q1.push_back(a[i].x1);
        q1.push_back(a[i].x2);
        q2.push_back(a[i].y1);
        q2.push_back(a[i].y2);
    }
    a[k].x1=1,a[k].y1=1,a[k].x2=n,a[k].y2=m,a[k].c=c,a[k].t=0;

    sort(a,a+k+1,cmp);

    sort(q1.begin(),q1.end());
    sort(q2.begin(),q2.end());
    q1.erase(unique(q1.begin(),q1.end()),q1.end());
    q2.erase(unique(q2.begin(),q2.end()),q2.end());

    for(int i=0;i<q1.size();i++)
        H1[q1[i]]=i+1;
    for(int i=0;i<q2.size();i++)
        H2[q2[i]]=i+1;

    for(int i=1;i<=q1.size()+1;i++)
        for(int j=1;j<=q2.size()+1;j++)
            fa[i][j]=j;

    for(int p=0;p<=k;p++)
    {
        for(int i=H1[a[p].x1];i<=H1[a[p].x2];i++)
        {
            for(int j=H2[a[p].y1];j<=H2[a[p].y2];j++)
            {
                j=fi(i,j);
                if(j>H2[m])
                    break;
                mp[i][j]=a[p].c;
                if(!flag[a[p].c])
                    ans++;
                flag[a[p].c]=1;
                fa[i][j]=j+1;
            }
        }
    }
    printf("%d
",ans);
}

acdream 1725 哗啦啦的小彭玉染色问题 离散化并查集