首页 > 代码库 > BZOJ 1483 HNOI 2009 梦幻布丁 链表+启发式合并

BZOJ 1483 HNOI 2009 梦幻布丁 链表+启发式合并

2024-08-05 01:10:15   222人阅读

题目大意：给出一串颜色，有两种操作，1.询问有多少块颜色。2.将一种颜色改变成另一种颜色。


思路：好像和染色什么的比较像，但是看了题解之后发现完全不是那么回事。
对于每一种颜色维护一个链表，然后在修改颜色的时候，暴力修改一种颜色成为另一种颜色，用启发式合并可以保证复杂度不超过O(nlogn)。但是由于是启发式合并，有可能导致你就改了反了颜色，这个时候记录一个映射，然后把修改错的记录下来。各种信息仔细讨论一下。。。


CODE：


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 1000010
using namespace std;
 
struct List{
    List *next;
    int pos;
     
    List(int _ = 0) {
        next = NULL;
        pos = _;
    }
}*head[MAX];
 
int cnt,asks;
int src[MAX];
int now,num[MAX];
int C[MAX];
 
void Pretreatment()
{
    for(int i = 1; i < MAX; ++i)
        C[i] = i;
}
 
inline void Add(int col,int pos)
{
    List *temp = new List(pos);
    temp->next = head[col];
    head[col] = temp;
}
 
inline void Change(int from,int aim)
{
    if(from == aim) return ;
    if(num[C[from]] > num[C[aim]])
        swap(C[from],C[aim]);
    from = C[from],aim = C[aim];
    if(head[from] == NULL)  return ;
    for(List *x = head[from]; x != NULL; x = x->next) {
        if(src[x->pos - 1] == aim)   --now;
        if(src[x->pos + 1] == aim)   --now;
        Add(aim,x->pos);
    }
    for(List *x = head[from]; x != NULL; x = x->next)
        src[x->pos] = aim;
    static List *stack[MAX];
    int top = 0;
    for(List *x = head[from]; x != NULL; x = x->next)
        stack[++top] = x;
    while(top)  delete stack[top--];
    head[from] = NULL;
    num[aim] += num[from];
    num[from] = 0;
}
 
int main()
{
    Pretreatment();
    cin >> cnt >> asks;
    int last = 0;
    for(int i = 1; i <= cnt; ++i) {
        scanf("%d",&src[i]);
        Add(src[i],i);
        ++num[src[i]];
        if(src[i] != last) {
            last = src[i];
            ++now; 
        }
    }
    for(int flag,x,y,i = 1; i <= asks; ++i) {
        scanf("%d",&flag);
        if(flag == 1) {
            scanf("%d%d",&x,&y);
            Change(x,y);
        }
        else    printf("%d\n",now);
    }
    return 0;
}


BZOJ 1483 HNOI 2009 梦幻布丁 链表+启发式合并


联系
我们