Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays. Specifically, suppose that we wish to support SEARCH and INSERT on a set of n elements. Let k = lg(n+1), and let the binary representation of n be nk1, nk2, … , n0. We have k sorted arrays A0, A1, … , Ak1, where for i = 0, 1, …, k1, the length of array Ai is 2i. Each array is either full or empty, depending on whether ni = 1 or ni = 0, respectively. The total number of elements held in all k arrays is therefore exactly n. Although each individual array is sorted, elements in different arrays bear no particular relationship to each other.

[高演] ? 資料結構
支援插入數字、刪除數字、查找數字。
使用 log n 堆，第 i 堆約有 2^i 個數字。
查找數字一律 O(log^2 n)

(1) 考慮只有插入數字
每一個數字在合併時，整體來說最多從第 0 堆爬到最高堆，
因此根據攤銷分析，每次插入數字僅 O(log n)。
(2) 增加刪除數字操作
要刪除一定要先找到，絕對逃不了 O(log^2 n)。
採用額外陣列標計的懶操作進行刪除動作，
在真正要合併兩堆的時候順便移除。

根據攤銷分析看起來沒有什麼問題。實作起來思考一下，
何時進行合併動作 ? 每次插入時都要檢查是否要合併、
刪除時，檢查這一堆的實際庫存是否還有一半，若沒有，
直接抓前一堆來合併。

那插入如何確保每個數字都要爬升 O(log n) 次。
要使得它插入在第 0 堆，因此插入要確保第 0 堆有辦法為空。
我們只能使用合併進行，一定要合併相鄰兩堆，否則攤銷會有問題。
真的不行，只好將 Load factor 下降到 1/2 左右。
-----
思考一下，塊狀鏈表比較好用，英文為 Unrolled linked list。
但是效率只有 O(sqrt(n))，不過塊狀鏈表特性支援區間查找問題。

實作完上述的資料結構後，也不是說特別難做，但非常不好分析。
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <time.h>
using namespace std;
struct Pt {
    int a, b;
    Pt(int x, int y):a(x),b(y){}
};
struct SpecialArray {
    int *head[32], *mark[32];
    int ncnt[32], dcnt[32];
    int n, hcnt;
    int maxbin;
    int buffer[1048576];
    SpecialArray() {
        maxbin = 20;
        memset(ncnt, 0, sizeof(ncnt));
        memset(dcnt, 0, sizeof(dcnt));
        for(int i = 0; i < maxbin; i++) {
            head[i] = new int[1<<i];
            mark[i] = new int[1<<i];
        }
        n = 0;
        hcnt = 0;
    }
    void insert(int val) {
        int filled = 1;
        for(int i = 0; i < hcnt; i++) {
            if(ncnt[i] != (1<<i))
                filled = 0;
        }
        if(filled == 1) {
            for(int i = hcnt-1; i >= 0; i--) {
                memcpy(head[i+1], head[i], (1<<i) * sizeof(int));
                memcpy(mark[i+1], mark[i], (1<<i) * sizeof(int));
                ncnt[i+1] = ncnt[i];
                dcnt[i+1] = dcnt[i];
            }
            hcnt++;
            ncnt[0] = 0;
            dcnt[0] = 0;
        }
        if(ncnt[0] != 0) {
            /*for(int i = hcnt-1; i >= 1; i--) {
                int p = i-1, q = i;
                if(ncnt[p] >= (1<<(i-1))/2 && ncnt[p] + ncnt[q] - dcnt[p] - dcnt[q] <= (1<<i))
                    merge(p, q);        
            }*/
            //for(int k = hcnt-1; k >= 0; k--) {
                for(int i = 1; i < hcnt; i++) {
                    int p = i-1, q = i;
                    if(ncnt[p] >= (1<<p)/2 && ncnt[p] + ncnt[q] - dcnt[p] - dcnt[q] <= (1<<q)) {
                        merge(p, q);
                        if(ncnt[q] > (1<<q))
                            printf("test %d %d\n", ncnt[q], 1<<q);
                    }
                }
            //}
            if(ncnt[0]) {    
                for(int i = hcnt-1; i >= 0; i--) {
                    memcpy(head[i+1], head[i], (1<<i) * sizeof(int));
                    memcpy(mark[i+1], mark[i], (1<<i) * sizeof(int));
                    ncnt[i+1] = ncnt[i];
                    dcnt[i+1] = dcnt[i];
                }
                hcnt++;
                ncnt[0] = 0;
                dcnt[0] = 0;
                if(hcnt >= maxbin) {
                    puts("err");
                    exit(0);
                }
            }
            if(ncnt[0]) {
                puts("err");
                for(int i = 0; i < hcnt; i++)
                    printf("%d ", ncnt[i]);
                puts("");
                exit(0);
            }/*                
            for(int i = 0; i < hcnt; i++)
                printf("%d ", ncnt[i]);
            puts("");*/
        }
        head[0][0] = val;
        mark[0][0] = 0;
        ncnt[0] = 1;
        dcnt[0] = 0;
        n++;
    }
    int find(int val) {
        for(int i = 0; i < hcnt; i++) {
            int idx = lower_bound(head[i], head[i]+ncnt[i], val) - head[i];
            if(head[i][idx] == val && mark[i][idx] == 0)
                return 1;
        }
        return 0;
    }
    int remove(int val) {
        for(int i = 0; i < hcnt; i++) {
            int l = lower_bound(head[i], head[i]+ncnt[i], val) - head[i];
            int r = upper_bound(head[i], head[i]+ncnt[i], val) - head[i] - 1;
            if(ncnt[i] == 0 || head[i][l] != val)
                continue;
            int mid, didx = -1;
            while(l <= r) {
                mid = (l + r)/2;
                if(mark[i][mid] == 0)
                    l = mid+1, didx = mid;
                else
                    r = mid-1;                    
            }
            if(didx == -1)    continue;
            if(mark[i][didx] == 0 && head[i][didx] == val) {
                mark[i][didx] = 1;
                dcnt[i]++;
                if(dcnt[i] >= (1<<i)/2 && i) {            
                    for(int i = 1; i < hcnt; i++) {
                        int p = i-1, q = i;
                        if(ncnt[p] >= (1<<(p))/2 && ncnt[p] + ncnt[q] - dcnt[p] - dcnt[q] <= (1<<q))
                            merge(p, q);        
                    }
                    //printf("del merge\n");
                }
                return 1;
            }
        }
        return 0;
    }
    void merge(int p, int q) {
        int idx1 = 0, idx2 = 0, idx3 = 0;
        while(idx1 < ncnt[p] && idx2 < ncnt[q]) {
            if(mark[p][idx1])        idx1++;
            else if(mark[q][idx2])    idx2++;
            else {
                if(head[p][idx1] < head[q][idx2])
                    buffer[idx3++] = head[p][idx1++];
                else
                    buffer[idx3++] = head[q][idx2++];
            }
        }
        while(idx1 < ncnt[p])    {
            if(mark[p][idx1])        idx1++;
            else buffer[idx3++] = head[p][idx1++];
        }
        while(idx2 < ncnt[q])    {
            if(mark[q][idx2])        idx2++;
            else buffer[idx3++] = head[q][idx2++];
        }
        for(int i = 0; i < idx3; i++) {
            head[q][i] = buffer[i];
            mark[q][i] = 0;
        }
        ncnt[p] = 0;
        ncnt[q] = idx3;
        dcnt[q] = 0;
    }
    void free() {
        for(int i = 0; i < 32; i++) {
            if(head[i])    delete[] head[i];
            if(mark[i])    delete[] mark[i];
        }            
    }
};
SpecialArray arr;
int main() {    
    freopen("in.txt","r+t",stdin);
    clock_t st, ed;
    st = clock();
    int n, p;
    int delAC = 0;
    while(scanf("%d %d", &p, &n) == 2) {
        if(p == 0)
            arr.insert(n);
        else if(p == 1) ;
            //arr.find(p);
        else if(p == 2)
            delAC += arr.remove(n);
    }
    long long sum = 0;
    for(int i = 0; i < arr.hcnt; i++) {
        for(int j = 0; j < arr.ncnt[i]; j++) {
            if(arr.mark[i][j] == 0)
                sum += arr.head[i][j];
            //printf("[%d %d]", arr.head[i][j], arr.mark[i][j]);
        }
        //puts("");
    }
    printf("%d %lld\n", delAC, sum);
    arr.free();
    ed = clock();
    printf("%f\n", (float)(ed - st )/CLOCKS_PER_SEC);
    return 0;
}