理解题意以后会发现时比较简单的线段树，理解题意以后首先应该想到一个贪心，就是再寻找最终答案的第i个数时，饿哦们要尽量使这个数尽可能大。那么我们找[1,pos[i]+1]这个区间中已经组队的位置的最大值，记为l,然后找[l+1pos[i]+1]之间未被找过的最大的数。（这里组队的意思是可以详见程序，并不是被找过了）。然后注意一下细节，是一个比较好维护的线段树，复杂付就是线段树的复杂度o(nlogn)。
题解上写维护组队的右端点是用set维护的，比赛当时也想到了用set维护，但是后来感觉好像只需要把PushUp和Modify稍加修改就好了，但是改了一下，感觉有点烦，索性就复制，粘贴，多谢了2个函数（几乎一样的）。
#include#include #include #include #include #define FOR(i,x,y) for(int i = x;i < y;i ++)#define IFOR(i,x,y) for(int i = x;i > y;i --)#define ll long long#define lrt rt<<1#define rrt rt<<1|1#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define N 100010using namespace std;int pos[N],num[N],ans[N],n;bool vis[N];struct Tree{ int l,r; int maxx,en_maxx;}tree[N<<2];void PushUp(int rt){ tree[rt].maxx = max(tree[lrt].maxx,tree[rrt].maxx);}void Build(int rt,int l,int r){ tree[rt].l = l; tree[rt].r = r; tree[rt].maxx = -1,tree[rt].en_maxx = 0; if(l == r){ tree[rt].maxx = num[l]; return; } int mid = (l+r)>>1; Build(lson); Build(rson); PushUp(rt);}void Modify(int rt,int k){ if(tree[rt].l == tree[rt].r){ tree[rt].maxx = -1; return; } int mid = (tree[rt].l+tree[rt].r)>>1; if(k <= mid) Modify(lrt,k); else Modify(rrt,k); PushUp(rt);}int Query(int rt,int l,int r){ if(tree[rt].l == l && tree[rt].r == r) return tree[rt].maxx; int mid = (tree[rt].l + tree[rt].r)>>1; if(r <= mid) return Query(lrt,l,r); else if(l > mid) return Query(rrt,l,r); else{ return max(Query(lson),Query(rson)); }}int Query_en(int rt,int l,int r){ if(tree[rt].l == l && tree[rt].r == r) return tree[rt].en_maxx; int mid = (tree[rt].l + tree[rt].r)>>1; if(r <= mid) return Query_en(lrt,l,r); else if(l > mid) return Query_en(rrt,l,r); else{ return max(Query_en(lson),Query_en(rson)); }}void PushUp_en(int rt){ tree[rt].en_maxx = max(tree[lrt].en_maxx,tree[rrt].en_maxx);}void Modify_en(int rt,int k){ if(tree[rt].l == tree[rt].r){ tree[rt].en_maxx = tree[rt].l; return; } int mid = (tree[rt].l+tree[rt].r)>>1; if(k <= mid) Modify_en(lrt,k); else Modify_en(rrt,k); PushUp_en(rt);}int main(){ //freopen("test.in","r",stdin); int t; scanf("%d",&t); while(t--){ scanf("%d",&n); FOR(i,1,n+1){ scanf("%d",&num[i]); pos[num[i]] = i; ans[i] = -1; vis[i] = false; } Build(1,1,n); FOR(i,1,n+1){ if(ans[i] != -1) continue; int r = pos[i]; int l = Query_en(1,1,r)+1; //if(i == 2) // printf("hahah\n"); if(l > r) ans[i] = ans[i+1]; else{ int tem = Query(1,l,r); if(r == n) ans[i] = tem; else{ if(!vis[num[pos[i]+1]]){ ans[i] = max(tem,num[pos[i]+1]); } else ans[i] = tem; } } vis[ans[i]] = true; Modify(1,pos[ans[i]]); if(pos[ans[i]] <= pos[i]) Modify_en(1,pos[i]); if(pos[ans[i]] < pos[i]){ FOR(j,pos[ans[i]],pos[i]){ ans[num[j]] = num[j+1]; vis[ans[num[j]]] = true; Modify(1,pos[ans[num[j]]]); } } } printf("%d",ans[1]); FOR(i,2,n+1){ printf(" %d",ans[i]); } printf("\n"); } return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。