AtCoder Regular Contest 080 E

Regular Contest 080 E"/>

AtCoder Regular Contest 080 E

其实细想其本质是一道拓扑序的题，选了当前点，才能选分裂出的三段。

#include<bits/stdc++.h>
#define pb push_back 
#define mp make_pair
using namespace std;const int maxn=2e5+7;
typedef long long ll;struct My{int l,r;pair<int,int> p;My(int L,int R,pair<int,int>P):l(L),r(R),p(P) {}
};bool operator<(const My &a,const My &b)
{if(a.p>b.p) return 1;return 0;
}priority_queue<My>q;vector<pair<int,int> >ans;vector<int>b1,b2;int n;
int h1,h2;int a[maxn];
int pos[maxn];
//int f[maxn];struct node{int l,r;int min;void update(int v){min+=v;}}tree[maxn*4],tree2[maxn*4];void push_up(int o)
{tree[o].min=min(tree[o<<1].min,tree[o<<1|1].min);
}void build(int l,int r,int o)
{tree[o].l=l;tree[o].r=r;if(l==r){tree[o].min=b1[l];}else{int mid=(l+r)/2;build(l,mid,o<<1);build(mid+1,r,o<<1|1);push_up(o);}
}void update(int p,int x,int o)
{}int qmin;
void query(int ql,int qr,int o)
{int l=tree[o].l,r=tree[o].r;if(ql<=l&&r<=qr){qmin=min(qmin,tree[o].min);}else{int mid=(l+r)/2;if(ql<=mid) query(ql,qr,o<<1);if(qr>mid) query(ql,qr,o<<1|1);}
}///
///void push_up2(int o)
{tree2[o].min=min(tree2[o<<1].min,tree2[o<<1|1].min);
}void build2(int l,int r,int o)
{tree2[o].l=l;tree2[o].r=r;if(l==r){tree2[o].min=b2[l];}else{int mid=(l+r)/2;build2(l,mid,o<<1);build2(mid+1,r,o<<1|1);push_up2(o);}
}void update2(int p,int x,int o)
{}void query2(int ql,int qr,int o)
{int l=tree2[o].l,r=tree2[o].r;if(ql<=l&&r<=qr){qmin=min(qmin,tree2[o].min);}else{int mid=(l+r)/2;if(ql<=mid) query2(ql,qr,o<<1);if(qr>mid) query2(ql,qr,o<<1|1);}
}int Q1(int l,int r)
{l=(l+1)/2;r=(r+1)/2;qmin=1e9;query(l,r,1);return pos[qmin];
}int Q2(int l,int r)
{l=(l)/2;r=(r)/2;qmin=1e9;query2(l,r,1);return pos[qmin];
}int num1,num2;pair<int,int> work(int l,int r)
{   if(l+1==r){return mp(a[l],a[r]);}int i,j,k;if(l%2==1)num1=Q1(l,r);else num1=Q2(l,r);if(l%2==1) num2=Q2(num1+1,r);else num2=Q1(num1+1,r);//ans.pb(mp(a[num1],a[num2]));/*work(l,num1-1);work(num2+1,r);work(num1+1,num2-1);*/return mp(a[num1],a[num2]);
}void doit()
{q.push(My(1,n,work(1,n)));while(!q.empty()){My now=q.top();q.pop();ans.pb(now.p);int l,r,l1,r1;l=now.l;r=now.r;l1=pos[now.p.first];r1=pos[now.p.second];if(l<l1-1) q.push(My(l,l1-1,work(l,l1-1)));if(l1+1<r1-1) q.push(My(l1+1,r1-1,work(l1+1,r1-1)));if(r1+1<r) q.push(My(r1+1,r,work(r1+1,r)));}
}int main()
{int i,j,k;scanf("%d",&n);b1.pb(0);b2.pb(0);for(i=1;i<=n;++i){scanf("%d",&a[i]);pos[a[i]]=i;if(i&1){b1.pb(a[i]);}else b2.pb(a[i]);} h1=b1.size()-1;h2=b2.size()-1;build(1,h1,1);build2(1,h2,1);doit();int len=ans.size();for(i=0;i<len-1;++i){printf("%d %d ",ans[i].first,ans[i].second);}printf("%d %d\n",ans[len-1].first,ans[len-1].second);return 0;
}

另解：斌大爷的分块