题解 P3201 【[HNOI2009]梦幻布丁】

· · 题解

一个奇怪的思路

map<pair<int,int>,list> mp;//list是手写链表支持两个链表连接

想法就是对每个相邻的点建一条边，根据边两侧的点的颜色把边扔进map+链表，每次把x改成y时只要遍历对应的链表即可找到所有变成相邻的同色点对的相邻的不同色点对，同时要把所有连接x的边并到y里（map上upper_bound+连接链表）

完了？

完了

若干坑点：边要建两条（无向边）；一个颜色被改变后要把原本颜色的链表删空（因为可能有1 1 2 1 1 3这种情况，不删就会把1的边加到3上，但这时已经没有1了）；删边也要两条都删

（边是用pair表示的）

代码：（好像是写过的最简洁的题解了）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;

int n,m,i,a[100005],ans,opt,x,y;

char Getchar()
{
    return getchar();
    static const int len=10000000;
    static char space[len],*p=space,*t=space;
    if(p==t)
      t=space+fread(p=space,sizeof(char),len,stdin);
    return *(p++);
}
char rc;int flag;
void read(int &x)
{
    x=0;rc=Getchar();flag=1;
    while(rc<'0'||rc>'9')
      flag=(rc=='-'?-1:1),rc=Getchar();
    while(rc>='0'&&rc<='9')
      x=x*10+rc-'0',rc=Getchar();
    x*=flag;
}

struct node
{
    int x;
    node *next;
    node(int num=0)
    {
        x=num;next=NULL;
    }
};
struct list
{
    node *head,*end;
    void push_back(int x)
    {
        if(head==NULL)
          head=new node(x),end=head;
        else end->next=new node(x),end=end->next;
    }
    void link(list x)
    {
        if(x.head==NULL)
          return;
        if(head==NULL)
          head=x.head,end=x.end;
        else end->next=x.head,end=x.end;
    }
};
list l;

map<pair<int,int>,list> mp;//listÊÇÊÖдÁ´±íÖ§³ÖÁ½¸öÁ´±íÁ¬½Ó 
map<pair<int,int>,list> ::iterator it,nit;

int f[100005];
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}

inline void del(map<pair<int,int>,list> ::iterator x)
{
    mp.erase(make_pair(x->first.second,x->first.first));
    mp.erase(x);
}

int main()
{
    read(n);read(m);ans=n;
    for(i=1;i<=n;i++)
      read(a[i]),f[i]=i;
    for(i=2;i<=n;i++)
      if(a[i]==a[i-1])
        f[i]=find(f[i-1]),ans--;
      else mp[make_pair(min(a[i],a[i-1]),max(a[i],a[i-1]))].push_back(i-1),mp[make_pair(max(a[i],a[i-1]),min(a[i],a[i-1]))].push_back(i-1);
    for(i=1;i<=m;i++)
    {
        read(opt);
        if(opt==1)
        {
            read(x);read(y);
            if(x==y)
              continue;
            l=mp[make_pair(x,y)];
            for(node *now=l.head;now!=NULL;now=now->next)
              if(find(now->x)!=find(now->x+1))
                ans--,f[find(now->x)]=find(now->x+1);
            it=mp.upper_bound(make_pair(x,0));
            for(;it->first.first==x&&it!=mp.end();nit=it++,del(nit))
              if(y!=it->first.second)
                mp[make_pair(min(y,it->first.second),max(y,it->first.second))].link(it->second),
                  mp[make_pair(max(y,it->first.second),min(y,it->first.second))].link(it->second);
        }
        if(opt==2)
          printf("%d\n",ans);
    }
    return 0;
}