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

题意：

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

题解：

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

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

 #include<bits/stdc++.h>

 #define pb push_back

 #define ls l,m,rt<<1

 #define rs m+1,r,rt<<1|1

 #define F(i,a,b) for(int i=a;i<=b;++i)

 using namespace std;

 const int N=1e5+;

 int col[N*];

 vector<int>cnt[N*];

 int t,n,q;

 struct node{int l,r,val;}tr[N*];

 void up(int rt)

 {

     tr[rt].l=tr[rt<<].l;

     tr[rt].r=tr[rt<<|].r;

     tr[rt].val=tr[rt<<].val+tr[rt<<|].val;

     if(tr[rt<<].r==tr[rt<<|].l)tr[rt].val--;

 }

 void build(int l=,int r=n,int rt=)

 {

     if(l==r)

     {

         scanf("%d",&tr[rt].l);

         tr[rt].r=tr[rt].l,tr[rt].val=;

         cnt[tr[rt].l].pb(l);

         return;

     }

     int m=l+r>>;

     build(ls),build(rs);

     up(rt);

 }

 void update(int pos,int b,int l=,int r=n,int rt=)

 {

     if(l==r)

     {

         tr[rt].r=tr[rt].l=b,tr[rt].val=;

         return;

     }

     int m=l+r>>;

     if(pos<=m)update(pos,b,ls);

     else update(pos,b,rs);

     up(rt);

 }

 node query(int x,int y,int l=,int r=n,int rt=)

 {

     if(l==r)return tr[rt];

     if(x<=l&&r<=y)return tr[rt];

     int m=l+r>>;

     node ll,rr,ans;

     if(y<=m)ans=query(x,y,ls);

     else if(x>m)ans=query(x,y,rs);

     else

     {

         ll=query(x,y,ls);

         rr=query(x,y,rs);

         ans.l=ll.l,ans.r=rr.r;

         if(ll.r!=rr.l)ans.val=ll.val+rr.val;

         else ans.val=ll.val+rr.val-;

     }

     return ans;

 }

 int main(){

     scanf("%d",&t);

     while(t--)

     {

         F(i,,)cnt[i].clear(),col[i]=i;

         scanf("%d%d",&n,&q);

         build();

         F(i,,q)

         {

             int a,b,c;

             scanf("%d%d%d",&a,&b,&c);

             if(a==)

             {

                 int x=col[b],y=col[c];

                 if(x==y)continue;

                 if(cnt[x].size()<cnt[y].size())

                 {

                     int en=cnt[x].size()-;

                     F(j,,en)

                     {

                         update(cnt[x][j],y);

                         cnt[y].pb(cnt[x][j]);

                     }

                     cnt[x].clear();

                 }else

                 {

                     col[b]=y,col[c]=x;

                     int en=cnt[y].size()-;

                     F(j,,en)

                     {

                         update(cnt[y][j],x);

                         cnt[x].pb(cnt[y][j]);

                     }

                     cnt[y].clear();

                 }

             }else printf("%d\n",query(b,c).val);

         }

     }

     return ;

 }

巴特西

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

最新文章

热门文章