当前位置：首页 > news >正文

hdu 5997 rausen loves cakes(线段数合并+启发式修改)

news 来源：原创 2024/5/18 14:06:40

题目链接：hdu 5997 rausen loves cakes

题意：

给你n个点，每个点有一个颜色，现在有两个操作，第一个操作，将颜色x改为颜色y，第二个操作，询问[x,y]区间有多少颜色段(颜色段的定义为从左往右相同的颜色为一段，遇到不相同的为下一段，ie：144112为4段颜色)

题解：

对于第二个操作我们可以写一个线段树合并来搞定，对于第一个操作，就要用启发式修改来进行，如何启发式?

我们开一个数组来记录每个颜色对应的颜色，最开始都是对应自己，然后开一个vector来记录每个颜色的位置，然后遇到将a颜色改为b颜色，就暴力修改位置数最小的那个，然后记录一下对应的颜色就行了，这样就能将修改操作的总复杂度降到log级别。

  1 #include<bits/stdc++.h>
  2 #define pb push_back
  3 #define ls l,m,rt<<1
  4 #define rs m+1,r,rt<<1|1
  5 #define F(i,a,b) for(int i=a;i<=b;++i)
  6 using namespace std;
  7 
  8 const int N=1e5+7;
  9 int col[N*10];
 10 vector<int>cnt[N*10];
 11 int t,n,q;
 12 struct node{int l,r,val;}tr[N*4];
 13 
 14 void up(int rt)
 15 {
 16     tr[rt].l=tr[rt<<1].l;
 17     tr[rt].r=tr[rt<<1|1].r;
 18     tr[rt].val=tr[rt<<1].val+tr[rt<<1|1].val;
 19     if(tr[rt<<1].r==tr[rt<<1|1].l)tr[rt].val--;
 20 }
 21 
 22 void build(int l=1,int r=n,int rt=1)
 23 {
 24     if(l==r)
 25     {
 26         scanf("%d",&tr[rt].l);
 27         tr[rt].r=tr[rt].l,tr[rt].val=1;
 28         cnt[tr[rt].l].pb(l);
 29         return;
 30     }
 31     int m=l+r>>1;
 32     build(ls),build(rs);
 33     up(rt);
 34 }
 35 
 36 void update(int pos,int b,int l=1,int r=n,int rt=1)
 37 {
 38     if(l==r)
 39     {
 40         tr[rt].r=tr[rt].l=b,tr[rt].val=1;
 41         return;
 42     }
 43     int m=l+r>>1;
 44     if(pos<=m)update(pos,b,ls);
 45     else update(pos,b,rs);
 46     up(rt);
 47 }
 48 
 49 node query(int x,int y,int l=1,int r=n,int rt=1)
 50 {
 51     if(l==r)return tr[rt];
 52     if(x<=l&&r<=y)return tr[rt];
 53     int m=l+r>>1;
 54     node ll,rr,ans;
 55     if(y<=m)ans=query(x,y,ls);
 56     else if(x>m)ans=query(x,y,rs);
 57     else
 58     {
 59         ll=query(x,y,ls);
 60         rr=query(x,y,rs);
 61         ans.l=ll.l,ans.r=rr.r;
 62         if(ll.r!=rr.l)ans.val=ll.val+rr.val;
 63         else ans.val=ll.val+rr.val-1;
 64     }
 65     return ans;
 66 }
 67 
 68 int main(){
 69     scanf("%d",&t);
 70     while(t--)
 71     {
 72         F(i,1,1000000)cnt[i].clear(),col[i]=i;
 73         scanf("%d%d",&n,&q);
 74         build();
 75         F(i,1,q)
 76         {
 77             int a,b,c;
 78             scanf("%d%d%d",&a,&b,&c);
 79             if(a==1)
 80             {
 81                 int x=col[b],y=col[c];
 82                 if(x==y)continue;
 83                 if(cnt[x].size()<cnt[y].size())
 84                 {
 85                     int en=cnt[x].size()-1;
 86                     F(j,0,en)
 87                     {
 88                         update(cnt[x][j],y);
 89                         cnt[y].pb(cnt[x][j]);
 90                     }
 91                     cnt[x].clear();
 92                 }else
 93                 {
 94                     col[b]=y,col[c]=x;
 95                     int en=cnt[y].size()-1;
 96                     F(j,0,en)
 97                     {
 98                         update(cnt[y][j],x);
 99                         cnt[x].pb(cnt[y][j]);
100                     }
101                     cnt[y].clear();
102                 }
103             }else printf("%d\n",query(b,c).val);
104         }
105     }
106     return 0;
107 }