[数据结构与算法]2021百度之星Astar 1006毒瘤数据结构

Astar 1006毒瘤数据结构

只需要每次加入的时候维护一下最前面从1开始连续的1的个数即可，用时:9min

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<cstdio>
#define MAXN 5000010
using namespace std; 

int a[MAXN];
int n;
int op,pos;

int main(){
	int poi=1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&op,&pos);
		if(op==1){
			a[pos]=1;
			while(a[poi]==1) poi++;
		}
		else if(op==2){
			bool flag=a[pos]==1;
			a[pos]=1;
			int p=poi;
			while(a[poi]==1) poi++;
			printf("%d\n",poi);
			poi=p;
			a[pos]=flag;			
		}
	}
	return 0;
}