题解|小熊的果篮

https://www.luogu.com.cn/problem/P7912

先按题目要求分块，可以用两个链表来模拟，一个链表表示块，一个链表表示水果。块链表储存块的头水果指针和尾水果指针。开始遍历块链表，吃掉一个水果，相当于删除水果链表中的一个水果，并更新块中储存的头水果指针，如果块为空则删掉这个块。每次吃完一轮之后在遍历一次块链表，来合并相同水果的相邻块。 时间复杂整个过程中相当遍历两遍水果，时间复杂度O(n)。 代码如下

#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define PII pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
const int N = 2e5+10;

struct Fnode {
    int l,r;
};

struct Knode {
    int l, r, s, e;
};

int n, f[N],kc, cnt;
Fnode fl[N];
Knode kl[N];

void fdel(int x) {
    int l = fl[x].l, r = fl[x].r;
    fl[l].r = r;
    fl[r].l = l;
}

void kdel(int x) {
    int l = kl[x].l, r = kl[x].r;
    kl[l].r = r;
    kl[r].l = l;
}

void solve() {
    int nk = kl[0].r;
    while(nk != kc+1) {
        int s = kl[nk].s, e = kl[nk].e;
        if(s == e) {
            fdel(s);
            kdel(nk);
        }else {
            fdel(s);
            kl[nk].s = fl[s].r;
        }
        cout << s << ' ';
        cnt++;
        nk = kl[nk].r;
    }
    nk = kl[0].r;
    while(nk!=kc+1) {
        int r = kl[nk].r;
        if(r==kc+1)break;
        if(f[kl[r].s] == f[kl[nk].s]) {
            kl[r].s = kl[nk].s;
            kdel(nk);
        }
        nk = r;
    }
    cout << '\n';
}

int main()
{
    IOS
    cin >> n;
    fl[0].r = 1;
    kl[0].r = 1;
    for(int i = 1; i <= n; i++) {
        cin >> f[i];
        fl[i].l = i - 1;
        fl[i].r = i +1;
    }
    f[n+1] = !f[n];
    for(int i = 2, si = 1; i <= n+1; i++) {
        if(f[i] != f[i-1]) {
            kc++;
            kl[kc].l = kc - 1;
            kl[kc].r = kc + 1;
            kl[kc].s = si;
            kl[kc].e = i-1;
            si = i;
        }
    }
    while(cnt < n) {
        solve();
    }
    return 0;
}