hdu5338 貪心+線段樹+二分+樹狀數組

位置x要麼放x+1位置的值，要麼找到前面沒有循環節中最大的一個值，判斷最左邊的非尋環節的位置用樹狀數組+二分，找最大值用線段樹維護

#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1 | 1
#define lowbit(x) x&(-x)
using namespace std;
const int N=1e5+10;
int INF=0x7f7f7f7;
int T,n,k;
const int MOD=1e9+7;
int a[N];
int ans[N];
int m[N<<2];
int pos[N];
int vis[N];
int sum(int x){
    int res=0;
    for(;x;x-=lowbit(x)){
        res+=vis[x];
    }
    return res;
}
void add(int x,int y){
    for(;x<=n;x+=lowbit(x)){
        vis[x]+=y;
    }
}
void pushup(int rt){
    m[rt]=max(m[rt<<1],m[rt<<1|1]);
}
void build(int l,int r,int rt){
    if(l==r){
        m[rt]=a[l];
        return;
    }
    int m=l+r>>1;
    build(lson);
    build(rson);
    pushup(rt);
}

void init(){
    build(1,n,1);
    memset(vis,0,sizeof vis);
}
int query(int L,int R,int l,int r,int rt){
    if(L<=l && R>=r){
        return m[rt];
    }
    int m=l+r>>1;
    int res=-1;
    if(L<=m) res=max(res,query(L,R,lson));
    if(R>m) res=max(res,query(L,R,rson));
    return res;
}
void update(int x,int y,int l,int r,int rt){
    if(l==r){
        m[rt]=y;
        return;
    }
    int m=l+r>>1;
    if(x<=m) update(x,y,lson);
    else update(x,y,rson);
    pushup(rt);
}
int bsearch(int x){ /*找x左邊最遠的沒有通路的點*/
    int l=1,r=x;
    int res=r;
    while(l<=r){
        int m=l+r>>1;
        if(sum(x)-sum(m-1)>0){
           l=m+1;
        }else{
            res=min(res,m);
            r=m-1;
        }
    }
    return res;
}

void solve(int x){/*找第x個位置放最大的值*/
     int p=pos[x];
     int l=bsearch(p);
     int ma=query(l,p,1,n,1);
     if(p==n || ma>a[p+1] || (sum(p+1)-sum(p)>0)) {
         for(int j=pos[ma];j<=p;j++) {
            add(j,1);
            if(j<p) ans[a[j]]=a[j+1];
            else ans[x]=ma;
        }

     }else{
        update(p+1,-1,1,n,1);/*更新p+1位置的值為-1 防止後面找最大的時候找到它*/
        ans[x]=a[p+1];
     }
}
int main()
{
#ifndef  ONLINE_JUDGE
 freopen("aaa","r",stdin);
#endif
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
            pos[a[i]]=i;
        }
        init();
        for(int i=1;i<=n;i++) {
            if(sum(pos[i])-sum(pos[i]-1)==0)  solve(i);
        }
        for(int i=1;i<=n;i++) printf("%d%c",ans[i],i<n?' ':'\n');
    }

    return 0;
}