Codeforces Round #285 (Div. 1), problem: (B) Misha and Permutations Summation

定義：
a in S_n
Ord(a) = a在Sn裏面的字典序
Perm(x) = 第x個元素（大小以字典序）
現在給兩個S_n裏面的元素a, b
問Perm(Ord(a) + Ord(b))

首先是：
Ord(a)可以被表成： a_0 * (n-1)! + a_1 * (n-2)! ....
算出要構造的
(a_0+b_0) * (n-1)! + (a_1+b_1) * (n-2)! .... （記得進位）
再反轉回去

主要需要以下兩種操作(lgN)：
1. 在set裏面丟入一個數    
2. 問set比t小的數有多少個

反轉時會需要用操作2做二分搜，所以總複雜度會是O(N(lgN)^2)

#include<cstdio>
#include<cmath>

using namespace std;

int tree[800001];
int base;

int arr1[200001];
int arr2[200001];

void build(int n){
    base = (1<<((int)(ceil(log2(n+3))))) - 1;
    for(int lx = 1;lx <= 2*base + 1;lx++)
        tree[lx] = 0;
    for(int lx = 0;lx < n;lx++)
        tree[base + 2 + lx] = 1;
    for(int lx = base;lx;lx--)
        tree[lx] = tree[lx*2] + tree[lx*2 + 1];    
    return;
}

void touch(int n){
    int ptr = base + 2 + n;
    tree[ptr] = 0;
    for(ptr>>=1;ptr;ptr>>=1)
        tree[ptr] = tree[ptr*2] + tree[ptr*2 + 1];
    return;
}

int query(int n){
    int ret = 0;
    for(int a = base+1, b= base+2+n + 1;
            a^b^1;a>>=1, b>>=1){
        if(~a&1) ret += tree[a^1];
        if(b&1) ret += tree[b^1];
    }
    return ret;
}

void get(int* arr, int n){
    build(n);
    for(int lx = 0;lx < n;lx++){
        int a = arr[lx];
        arr[lx] = query(arr[lx])-1;
        touch(a);
    }
    return;
}

void parr(int* arr, int n){
    for(int lx = 0;lx < n;lx++)
        printf("%d ", arr[lx]);
    puts("");
    return;
}

int main(){
    int n; scanf("%d", &n);
    for(int lx = 0;lx < n;lx++) scanf("%d", arr1 + lx);
    for(int lx = 0;lx < n;lx++) scanf("%d", arr2 + lx);
    get(arr1, n), get(arr2, n);
    //parr(arr1, n);
    //parr(arr2, n); 
    for(int lx = 0;lx < n;lx++)
        arr1[lx] += arr2[lx];
    for(int lx = n-1;lx;lx--)
        if(arr1[lx] >= n-lx)
            arr1[lx] -= n-lx, arr1[lx-1]++;
    arr1[0] %= n;
    //parr(arr1, n);
    build(n);
    for(int lx = 0;lx < n;lx++){
        int low = 0, hig = n-1;
        while(low < hig){
            int test = (low + hig)/2;
            int nn = query(test);
            if(nn < arr1[lx]+1)
                low = test+1;
            else
                hig = test;
        }
        touch(low);
        printf("%d ", low);
    }
    printf("\n");
    return 0;
}

Codeforces Round #285 (Div. 1), problem: (A) Misha and Forest

給定每個點的degree, sigma_xor adj_index，找出原圖
一直戳degree = 1的點

#include<cstdio>
#include<cstdlib>
#include<vector>
#include<queue>
#include<utility>

using namespace std;

int deg[1000000];
int val[1000000];
int que[1000000];

int main(){
    int n; scanf("%d", &n);
    for(int lx = 0;lx < n;lx++)
        scanf("%d %d", deg + lx, val + lx);
    int qs = 0, qe = 0;
    for(int lx = 0;lx < n;lx++)
        if(deg[lx] == 1)
            que[qe++] = lx;
    vector<pair<int,int> > ans;
    while(qe > qs){
        int prc = que[qs++];
        if(deg[prc] < 1) continue;
        int to = val[prc];
        ans.push_back(pair<int,int>(prc, to));
        val[to] ^= prc;
        deg[to]--;
        if(deg[to] == 1) 
            que[qe++] = to;
    }
    printf("%d\n", (int)ans.size());
    for(int lx = 0;lx < ans.size();lx++){
        printf("%d %d\n", ans[lx].first, ans[lx].second);
    }
    return 0;
}