洛谷P7912 [CSP-J 2021] 小熊的果篮 题解

题目链接：P7912 [CSP-J 2021] 小熊的果篮

题意：

小熊的水果店里摆放着一排 \(n\) 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 \(1, 2, \ldots, n\) 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里，具体方法是：每次都把每一个“块”中最左边的水果同时挑出，组成一个果篮。重复这一操作，直至水果用完。注意，每次挑完一个果篮后，“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后，两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。

输入格式：

第一行，包含一个正整数 \(n\)，表示水果的数量。

第二行，包含 \(n\) 个空格分隔的整数，其中第 \(i\) 个数表示编号为 \(i\) 的水果的种类，\(1\) 代表苹果，\(0\) 代表桔子。

输出格式：

输出若干行。

第 \(i\) 行表示第 \(i\) 次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号，每两个编号之间用一个空格分隔。

数据范围：

对于 \(100 \%\) 的数据，\(1 \le n \le 2 \times {10}^5\)。

去年的自己真搞笑，居然觉得这是dp想半天不会做，甚至暴力都不打

考虑用个队列维护每个块，然后每次取出一个块改一改扔到另一个队列里

另一个队列的用途是把这些块合并，这么写可以少掉很多麻烦。

然后这里有个坑，合并的时候编号不连续，所以要搞个懒惰删除，防止跳左端点跳到已经删掉的位置。

这样做复杂度不知道，注意到这个懒惰删除可以用并查集维护下一个未标记的位置。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(2e5+15))

int n,a[N],f[N];
struct node { int l,r,v; };
queue<node> q1,q2;
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); for(int i=1; i<=n; i++) read(a[i]), f[i]=i;
    a[n+1] = !a[n]; f[n+1] = n+1;
    for(int i=2,l=1; i<=n+1; i++)
    {
        if(a[i] == a[l]) continue;
        else q1.push({l,i-1,a[l]}),l=i;
    }
    for(int cnt=n; cnt; )
    {
        while(!q1.empty())
        {
            node u = q1.front(); q1.pop();
            u.l=find(u.l);
            write(u.l); pc(" \n"[q1.empty()]);
            f[u.l]=find(u.l+1); --cnt;
            ++u.l; if(u.l <= u.r) q2.push(u);
        }
        if(q2.empty()) break;
        node t = q2.front(); q2.pop();
        while(!q2.empty())
        {
            node u = q2.front(); q2.pop();
            if(t.v == u.v) t = {t.l, u.r, t.v};
            else q1.push(t), t = u;
        }q1.push(t);
    }
    return 0;
}