双链表30分求助
查看原帖
双链表30分求助
718928
Mr_Egg楼主2023/10/19 18:31
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct block{
	int st,ed,v;
	bool operator== (const block &b) const{
		return v==b.v;
	}
}e[N];
bool vis[N];
int a[N],nxt[N],pre[N],idx=2,size=0;
void init(){
    e[0]=e[1]={-1,-1,-1};
    nxt[0]=1,pre[1]=0;
}
void add_back(block x){
    e[idx]=x;
    nxt[pre[1]]=idx,pre[idx]=pre[1];
    nxt[idx]=1,pre[1]=idx++;
    size++;
}
void del(int k){
    nxt[pre[k]]=nxt[k];
    pre[nxt[k]]=pre[k];
    size--;
}
int main(){
	int n;
	scanf("%d",&n);
	init();
	block now={0,0,2};
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]!=now.v){
			if(now.v!=2) add_back(now);
			now={i,i,a[i]};
		}else now.ed++;
	}
	add_back(now);
//	for(int i=nxt[0];i!=1;i=nxt[i])
//		printf("%d %d %d\n",e[i].st,e[i].ed,e[i].v);
	while(size){
		bool flag=0;
		for(int i=nxt[0];i!=1;i=nxt[i]){
			int &l=e[i].st,&r=e[i].ed;
			if(!vis[l]){printf("%d ",l);flag=1;};
			vis[l]=1;
			if(l==r)del(i);
			l++;
		}
		if(flag) printf("\n");
		for(int i=nxt[0];i!=1;i=nxt[i]){
			if(e[i]==e[nxt[i]]&&nxt[i]!=1){
				e[i].ed=e[nxt[i]].ed;
				del(nxt[i]);
			}
		}
	}
	return 0;
}
2023/10/19 18:31
加载中...