hdu 5338 ZZX and Permutations(欲張り+線分樹+二分)

ZZX and Permutations
Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 24    Accepted Submission(s): 2
Problem Description
ZZX likes permutations.
ZZX knows that a permutation can be decomposed into disjoint cycles(see https://en.wikipedia.org/wiki/Permutation#Cycle_notation). For example:
145632=(1)(35)(462)=(462)(1)(35)=(35)(1)(462)=(246)(1)(53)=(624)(1)(53)……
Note that there are many ways to rewrite it, but they are all equivalent.
A cycle with only one element is also written in the decomposition, like (1) in the example above.
Now, we remove all the parentheses in the decomposition. So the decomposition of 145632 can be 135462,462135,351462,246153,624153……
Now you are given the decomposition of a permutation after removing all the parentheses (itself is also a permutation). You should recover the original permutation. There are many ways to recover, so you should find the one with largest lexicographic order.
 
Input
First line contains an integer
t , the number of test cases.
Then
t testcases follow. In each testcase:
First line contains an integer
n , the size of the permutation.
Second line contains
n space-separated integers, the decomposition after removing parentheses.
n≤105 . There are 10 testcases satisfying
n≤105 , 200 testcases satisfying
n≤1000 .
 
Output
Output
n space-separated numbers in a line for each testcase.
Don't output space after the last number of a line.
 
Sample Input

   
   
   
   

    
    
    
    2
6
1 4 5 6 3 2
2
1 2
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    4 6 2 5 1 3
2 1
   
   
   
   

 
Source
2015 Multi-University Training Contest 4
題意はあなたに1つのn個の数以内の組み合わせをあげて、各数は1~nを取って、1つの循環変化のマークにまた括弧の後の配列を取り除いて、あなたにこの配列を辞書の順序の最大の組み合わせの配列に還元することを教えます.まず、例えば1 4 5 6 3 2はans[i]で答え位置iの値を表し、a[i]は入力された配列を表し、id[i]はa[]の値iの位置を表す.解を求める時、ans[1]は1あるいは4を取ることができて、この時当然貪欲に4を取るのがよくて、4のこの値に対して私達はマークしてすでに使ったことがあって、ans[1]に対して答えを得て、位置1マークしてすでに答えを解いて、しかし私達は位置4を確定していないで、4は1を取るかもしれないし5を取るかもしれないため、私達は後で討論します;ans[2]は1 5 6 3のいずれかの値をとることができ、4という値は既に用いられているため、これ以上は使えず、貪欲に最大値6をとるので、この動的計算最大値の場合は線分木で最大値を維持する必要がある.最大値6はa[]のi=4であり、2はa[]のi=6であるため、必然的に2<-6<-3<-2というループを構成し、場合によってはans[2]、ans[6]、ans[3]の値を直接決定することができる.位置2,6,3タグについては既に答えが解けており、値6,3,2タグについては既に使用済みであり、線分ツリーから削除(set l=4 r=6 value=0)し、区間[4,6]タグについては既に確定しており、区間の後ろから区間の前の数を跨ぐことはできないので、この区間[l=4,r=6]を2分の構造で投げ込み、私が使用しているmapはどうせ挿入時にlognであることを保証し、ツリー上の二分もlognで、線分ツリーで最大値を検索するたびに、これらの確定位置の区間を越えることはできないので、二分するたびに最大値の区間を検索することができます.ans[3]答えを解いたことがあるので、スキップすればいい.ans[4]は1または5を取ることができ、5がもっと大きくて使われていないので欲張って5を取り、5マークをこの値を使ったことがあり、線分木から5を削除し、4という位置をマークして、すでに確定した.ans[5]は線分樹が区間[1,3]で見つけた最大値を取ることができる.ans[6]答えを解いたことがあるので、スキップすればいい.

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <map>

    using namespace std;

    const int maxn = 100010;
    typedef long long LL;

    int a[maxn], vidx[maxn];
    int vis[maxn], flg[maxn];

    namespace SegmentTree{
        int maxv[maxn<<2]; int setv[maxn<<2];
        #define Lson o<<1
        #define Rson o<<1|1

        void pushup(int o){
            maxv[o] = max(maxv[Lson], maxv[Rson]);
        }

        void build(int o, int l, int r){
            int m = (l+r)>>1;
            if(l == r){
                maxv[o] = a[l];
                setv[o] = -1;
            }
            else {
                build(Lson, l, m);
                build(Rson, m+1, r);
                setv[o] = -1;
                pushup(o);
            }
        }

        void pushdown(int o){
            if (setv[o] >= 0){
                setv[Lson] = setv[Rson] = setv[o];
                maxv[Lson] = maxv[Rson] = setv[o];
                setv[o] = -1;
            }
        }

        int v, ul, ur;
        void update(int o, int l, int r){
            if(l > r) return ;
            if (ul <= l && r <= ur){
                setv[o] = v;
                maxv[o] = v;
            }
            else{
                pushdown(o);
                int m = (l+r)>>1;
                if (ul <= m) update(Lson, l, m);
                if (ur > m) update(Rson, m+1, r);
                pushup(o);
            }
        }

        int _max, ql, qr;
        void query(int o, int l, int r){
            if(l>r) return ;
            if (setv[o] >= 0){
                _max = max(_max, setv[o]);
            }
            else if (ql <= l && r <= qr){
                _max = max(_max, maxv[o]);
            }
            else {
                int m = (l+r)>>1;
                pushdown(o);
                if(ql <= m) query(Lson, l, m);
                if(qr > m) query(Rson, m+1, r);
            }
        }

    }

    namespace BS{

        typedef pair<int,int> seg;
        #define l first
        #define r second
        #define MP make_pair
        int n;

        map<int,int> mp;

        void init(){
            mp.clear();
        }

        void add(int l, int r){
            seg line = MP(l, r);
            mp.insert(line);
        }

        int search(int v){

            map<int,int>::iterator it = mp.upper_bound(v);

            if (it == mp.begin()){
                return 0;
            }
            else{
                --it;
                return it->r;
            }
        }
    }

    int ans[maxn];
    void link(int l, int r){
        for(int i=l; i<r; i++){
            ans[a[i]] = a[i+1];
        }
        ans[a[r]] = a[l];
    }

    int main(){
//        freopen("data.in", "r", stdin);
        int T, n;
        scanf("%d",&T);
        while(T--){
            scanf("%d", &n);
            for(int i=1;i<=n;i++){
                scanf("%d",&a[i]);
                vidx[a[i]] = i;
            }

            memset(vis, 0, sizeof vis);
            memset(flg, 0, sizeof flg);
            SegmentTree::build(1,1,n);
            BS::init();
            for(int _i=1;_i<=n;_i++){
                int i = vidx[_i];
                if (vis[i]) continue;

                int id = i, mx=0;
                if(!flg[_i]) mx = _i;


                SegmentTree::ql = BS::search(i) + 1;
                SegmentTree::qr = id-1;
                SegmentTree::_max = 0;
                SegmentTree::query(1,1,n);

                mx = max(mx, SegmentTree::_max);
                if (!vis[i+1] && i < n){
                    mx = max(mx, a[i+1]);

                    // a[i+1]  i  
                    if (mx == a[i+1]){
                        ans[_i] = a[i+1];
                        flg[a[i+1]] = 1;

                        SegmentTree::ul = i+1;
                        SegmentTree::ur = i+1;
                        SegmentTree::v = 0;
                        SegmentTree::update(1,1,n);

                        continue;
                    }
                }

                // vidx[mx]  i
                int l = min(vidx[mx], i),r = max(vidx[mx], i);
                link(l, r);
                for(int j = l; j <= r; j++){
                    vis[j] = 1;
                    flg[a[j]] = 1;
                }
                BS::add(l, r);
                SegmentTree::ul = l;
                SegmentTree::ur = r;
                SegmentTree::v = 0;
                SegmentTree::update(1,1,n);
            }
            for(int i=1; i <= n; i++){
                printf("%d%c", ans[i], i<n?' ':'
');
            }
        }

        return 0;
    }