首页 > 代码库 > BZOJ 1483 HNOI 2009 梦幻布丁 链表+启发式合并
BZOJ 1483 HNOI 2009 梦幻布丁 链表+启发式合并
题目大意：给出一串颜色，有两种操作，1.询问有多少块颜色。2.将一种颜色改变成另一种颜色。
思路：好像和染色什么的比较像，但是看了题解之后发现完全不是那么回事。
对于每一种颜色维护一个链表，然后在修改颜色的时候，暴力修改一种颜色成为另一种颜色，用启发式合并可以保证复杂度不超过O(nlogn)。但是由于是启发式合并，有可能导致你就改了反了颜色，这个时候记录一个映射，然后把修改错的记录下来。各种信息仔细讨论一下。。。
思路：好像和染色什么的比较像，但是看了题解之后发现完全不是那么回事。
对于每一种颜色维护一个链表，然后在修改颜色的时候，暴力修改一种颜色成为另一种颜色，用启发式合并可以保证复杂度不超过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 梦幻布丁 链表+启发式合并
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。