Submission #2701566

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 998244353
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 200003
#define pc(x) putchar_unlocked(x);
int state[mx*4],tree[mx*4][2],lazy[mx*4],a[mx],di[mx],n,mini[mx*4];
set<int>batas;
vector<int>ans;
void build(int idx,int l,int r){
	state[idx]=1;
	if(l==r){
		if(l&1){
			tree[idx][1]=a[l];
			tree[idx][0]=1e9;
		}
		else{
			tree[idx][0]=a[l];
			tree[idx][1]=1e9;
		}
		mini[idx]=tree[idx][state[idx]];
		return;
	}
	build(2*idx,l,MID);
	build(2*idx+1,MID+1,r);
	for(int i=0;i<2;i++)tree[idx][i]=min(tree[idx*2][i],tree[2*idx+1][i]);
	mini[idx]=min(mini[idx*2],mini[2*idx+1]);
}

void pd(int idx,int l,int r){
	lazy[idx]^=1;
	state[idx]^=1;
	mini[idx]=tree[idx][state[idx]];
}

void ganti(int idx,int l,int r,int fl,int fr){
	if(fl>r || fr<l)return;
	if(fl<=l && r<=fr){
		lazy[idx]^=1;
		state[idx]^=1;
		mini[idx]=tree[idx][state[idx]];
		return;
	}
	if(lazy[idx]){
		pd(2*idx,l,MID);
		pd(2*idx+1,MID+1,r);
		lazy[idx]=0;
	}
	ganti(2*idx,l,MID,fl,fr);
	ganti(2*idx+1,MID+1,r,fl,fr);
	for(int i=0;i<2;i++)tree[idx][i]=min(tree[idx*2][i],tree[2*idx+1][i]);
	mini[idx]=min(mini[idx*2],mini[2*idx+1]);
}

int cari(int t,int idx,int l,int r,int fl,int fr){
	if(fl>r || fr<l)return 1e9;
	if(fl<=l && r<=fr)return tree[idx][t];
	if(lazy[idx]){
		pd(2*idx,l,MID);
		pd(2*idx+1,MID+1,r);
		lazy[idx]=0;
	}
	return min(cari(t,idx*2,l,MID,fl,fr),cari(t,2*idx+1,MID+1,r,fl,fr));
}

void upd(int idx,int l,int r,int in){
	if(in>r || in<l)return;
	if(l==r){
		mini[idx]=tree[idx][0]=tree[idx][1]=1e9;
		return;
	}
	if(lazy[idx]){
		pd(2*idx,l,MID);
		pd(2*idx+1,MID+1,r);
		lazy[idx]=0;
	}
	upd(2*idx,l,MID,in);
	upd(2*idx+1,MID+1,r,in);
	for(int i=0;i<2;i++)tree[idx][i]=min(tree[idx*2][i],tree[2*idx+1][i]);
	mini[idx]=min(mini[idx*2],mini[2*idx+1]);
}

int main(){
	cin>>n;
	batas.insert(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		di[a[i]]=i;
	}
	build(1,1,n);
	for(int i=1;i<=n;i+=2){
		int x=mini[1];
		int pos=di[x];
		auto it=batas.lower_bound(pos);
		int y=*it-1;
		int t=1;
		if(pos&1)t=0;
		int z=cari(t,1,1,n,pos+1,y);
		int cnt=0;
		if(z==1e9){
			while(1)cnt++;
		}
	//	debug(x);
	//	debug(z);
		int tmp=di[z];
		ganti(1,1,n,pos+1,tmp-1);
		batas.insert(pos);
		batas.insert(tmp);
		upd(1,1,n,pos);
		upd(1,1,n,tmp);
		ans.pb(x);
		ans.pb(z);
	}
	for(int i:ans)cout<<i<<' ';
}

Submission Info

Judge Result