洛谷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;
}