typedef long long LL;
const int N = 100003;
const LL INF = 4611686018427387904;
LL raw [N], st [N], outk [N];
int p [N], ver [N][2], pneg [N], outi [N];
inline void del ( int i ){
int pre = ver [i][0], nxt = ver [i][1];
ver [pre][1] = nxt; ver [nxt][0] = pre;
}
inline void lnk ( int l, int r ){ ver [l][1] = r; ver [r][0] = l; }
inline bool cmp ( int x, int y ){ return raw [x] < raw [y]; }
int main (){
int n; rd (n);
for ( int i = 1; i <= n; ++i ) lrd ( raw [i] );
for ( int i = 1; i <= n; ++i ) st [i] = raw [i];
sort ( st+1, st+n +1 );
for ( int i = 1; i <= n; ++i ) pneg [i] = i;
sort ( pneg+1, pneg+n +1, cmp );
for ( int i = 1; i <= n; ++i ) p [ pneg[i] ] = i;
for ( int i = 1; i < n; ++i ) lnk ( i, i+1 );
lnk ( 0, 1 ); lnk ( n, N-1 );
for ( int i = n; i > 1; --i ){
int nw = p [i]; int pr = ver [nw][0], nx = ver [nw][1];
LL prk = INF, nxk = INF;
if ( pr != 0 ) prk = abs ( st [nw] - st [pr] );
if ( nx !=N-1) nxk = abs ( st [nw] - st [nx] );
if ( prk <= nxk ){ outk [i] = prk; outi [i] = pneg [pr]; }
else{ outk [i] = nxk; outi [i] = pneg [nx]; }
del ( p [i] );
}
for ( int i = 2; i <= n; ++i ) printf ( "%lld %d\n", outk [i], outi [i] );
return 0;
}
raw 以输入顺序储存原始值;
st 以递增顺序储存原始值;
p [i] = j(等于号,后同)表示 raw [i] = st [j];
pneg [i] = j 表示 st [i] = raw [j];
ver [i][0] = j 表示 st [i] 的前驱是 st [j];
ver [i][1] = j 表示 st [i] 的后继是 st [j];
outi 和 outk 储存输出信息。
是不是还是觉得看图更容易理解~
这是136的代码吧..