Codeforces Round #285 Div. 2 D. Misha and Permutations Summation

題目鏈接:http://codeforces.com/contest/501/problem/D

題意

給定兩個排列,定義Perm(x)字典序為x的排列
Ord(p)表示排列p的字典序,給定兩個排列p和q
求Perm((Ord(p) + Ord(q)) % (n!))

解法

用康托展開求出來Ord(p) + Ord(q)
對於排列P:{a_1,a_2,.......,a_n}
字典序Rank(P)=count_1 * (n - 1)! + count_2 * (n - 2)! + ........ + count_n * (0)!

count_i表示a_i後面比a_i小的數字的個數
由於n!太大,不能直接求(Ord(p) + Ord(q)) % (n!)
可以統計出來Ord(p) + Ord(q)中 n!, (n - 1)!, (n - 2)!,........, 0! 每個階乘出現的次數

設b[i]表示(n - i)!出現的次數,如果b[i] > (n - i)那麼應該使得b[i-1] += b[i] / (n - i)
同時令b[i] += b[i] % (n - i)

這樣遍歷一邊數組就得到(Ord(p) + Ord(q)) % (n!)每個階乘出現的次數
這裡的b[i]就相當於count_i,維護一棵線段樹,求出來序列即可

新學的線段樹寫法

class Cf501D {
    int[] a,b;
    int n;
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        n = in.nextInt();
        a = new int[n];
        b = new int[n];
        for(int i = 0; i < n; i ++) {
            a[i] = in.nextInt();
        }
        SegmentTree st=new SegmentTree(0, n-1);
        for(int i = 0; i < n; i ++) {
            b[i] += st.sum(a[i]) - 1;
            st.update(a[i]);
        }
        for(int i = 0; i < n; i ++) {
            a[i] = in.nextInt();
        }
        st = new SegmentTree(0, n-1);
        for(int i = 0; i < n; i ++) {
            b[i] += st.sum(a[i]) - 1;
            st.update(a[i]);
        }
        for(int i = n-1; i > 0; i --) {
            int x = b[i] / (n - i);
            b[i - 1] += x;
            b[i] %= (n - i);
        }
        b[0] %= n;
        st =  new SegmentTree(0, n-1);
        for(int i = 0; i < n; i ++) {
            int tmp = st.get(b[i]);
            out.print(tmp + " ");
            st.update(tmp);
        }
        out.println();
    }
    static class SegmentTree {
        SegmentTree left,right;
        int L,R;
        int sum;
        public SegmentTree(int l, int r) {
            L = l; R = r;
            if(l == r) {
                sum = 1;
                return;
            }
            int mid = (l + r) >> 1;
            left = new SegmentTree(l, mid);
            right = new SegmentTree(mid+1, r);
            sum = left.sum + right.sum;
        }
        int get(int k) {
            if(L == R) {
                return L;
            }
            if(left.sum > k) return left.get(k);
            return right.get(k-left.sum);
        }
        int sum(int k) {
            if(L == R) {
                return sum;
            }
            int mid = (L + R) >> 1;
            if(mid >= k) return left.sum(k);
            return left.sum + right.sum(k);
        }
        void update(int k) {
            if(L == R) {
                sum=0;
                return;
            }
            int mid = (L + R) >> 1;
            if(mid >= k) left.update(k);
            else right.update(k);
            sum = left.sum + right.sum;
        }
    }
}