小熊的果篮

Spasmodic · 2021-10-23 20:23:53 · 题解

提供一个考场上的奇怪做法。

考虑维护所有块，在块之间用链表连，每一块也拉个链表维护块内的元素。

每次如果有一块没了就暴力合并，这个复杂度我算不来，大概过不去。

考虑优化成启发式合并，复杂度就变成最多 O(n\log n)，原因是每个元素至多被合并 \log n 次，然后就过去了。

code：

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define Rep(i,l,r) for(int i=(l);i>=(r);--i)
using namespace std;
typedef deque<int> vec;
const int N=200005;
int n,a[N],cnt,nxt[N],pre[N];
vec block[N];
void merge(int x,int y){
    if(block[x].size()<block[y].size()){
        while(!block[x].empty())block[y].push_front(block[x].back()),block[x].pop_back();
        pre[y]=pre[x];nxt[pre[x]]=y;
    }else{
        for(int t:block[y])block[x].push_back(t);
        nxt[x]=nxt[y];pre[nxt[y]]=x;
    }
}
int main(){
    scanf("%d",&n);
    rep(i,1,n)scanf("%d",&a[i]);
    rep(i,1,n){
        int t=a[i];cnt++;
        while(i<=n&&a[i]==t)block[cnt].push_back(i),i++;
        i--;
    }
    rep(i,1,cnt)pre[i]=i-1,nxt[i-1]=i;
    nxt[cnt]=0,pre[0]=cnt;
    while(nxt[0]){
        for(int i=nxt[0];i;i=nxt[i])printf("%d ",block[i].front()),block[i].pop_front();
        puts("");
        for(int i=nxt[0];i;i=nxt[i])if(!block[i].size()){
            bool domerge=0;int x=pre[i];
            while(i&&!block[i].size())domerge=1-domerge,i=nxt[i];
            if(!x){nxt[0]=i;pre[i]=0;continue;}
            if(!i){nxt[x]=0;pre[0]=x;continue;}
            if(!domerge)nxt[x]=i,pre[i]=x;
            else merge(x,i);
        }
    }
    return 0;
}