ARC080 E

ARC080 E

要求串q的字典序最小，那我们倒着，考虑最后插入q开头的字符在p串中的位置x,y(x< y)，发现x一定是奇数下标的最小值，y一定是x之后，偶数下标最小值
同时这次操作后，会将区间分为(l,x-1),(x+1,y-1),(y+1,r)
维护个堆，每次取出第一位最小的，将它分裂，找分裂区间的最小值再塞进去
找最小值可以线段树或rmq
注意当操作区间(l,r)的左端点l是偶数时，上文的奇偶会取反

code：

#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1e9
using namespace std;const int maxd = 20;
const int maxn = 210000;int n;
int a[maxn],p[maxn];int pre1[maxn][maxd],pre2[maxn][maxd];
int suf1[maxn][maxd],suf2[maxn][maxd];
int ln[maxn];int q_1(const int l,const int r)
{int ld=ln[r-l+1];return min(suf1[l][ld],pre1[r][ld]);
}
int q_2(const int l,const int r)
{int ld=ln[r-l+1];return min(suf2[l][ld],pre2[r][ld]);
}
int query(const int l,const int r,const int t){return t?q_1(l,r):q_2(l,r);}struct node{int l,r,fir,sec;};
inline bool operator <(const node x,const node y){return x.fir>y.fir;}
priority_queue<node>q;int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),p[a[i]]=i;for(int i=2;i<=n;i<<=1) ln[i]++;for(int i=1;i<=n;i++) ln[i]+=ln[i-1];for(int i=1;i<=n;i++){if(i&1) pre1[i][0]=suf1[i][0]=a[i],pre2[i][0]=suf2[i][0]=inf;else pre2[i][0]=suf2[i][0]=a[i],pre1[i][0]=suf1[i][0]=inf;}for(int d=1;(1<<d)<=n;d++){for(int i=1;i<=n;i++){if(i-(1<<d)>=0) pre1[i][d]=min(pre1[i-(1<<d-1)][d-1],pre1[i][d-1]),pre2[i][d]=min(pre2[i-(1<<d-1)][d-1],pre2[i][d-1]);if(i+(1<<d)-1<=n)suf1[i][d]=min(suf1[i+(1<<d-1)][d-1],suf1[i][d-1]),suf2[i][d]=min(suf2[i+(1<<d-1)][d-1],suf2[i][d-1]);}}int fir=q_1(1,n),sec=q_2(p[fir]+1,n);q.push((node){1,n,fir,sec});while(!q.empty()){const node x=q.top(); q.pop();printf("%d %d ",x.fir,x.sec);int l=x.l,r=x.r;int t1=p[x.fir],t2=p[x.sec];if(l!=t1){int t=l&1;fir=query(l,t1-1,t); sec=query(p[fir]+1,t1-1,!t);q.push((node){l,t1-1,fir,sec});}if(t1+1!=t2){int t=(t1+1)&1;fir=query(t1+1,t2-1,t); sec=query(p[fir]+1,t2-1,!t);q.push((node){t1+1,t2-1,fir,sec});}if(t2!=r){int t=(t2+1)&1;fir=query(t2+1,r,t); sec=query(p[fir]+1,r,!t);q.push((node){t2+1,r,fir,sec});}}return 0;
}