标题：采用败者树(?)的多路归并
出处：Felix021
时间：Tue, 23 Jun 2009 10:15:15 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1667

内容：
坦白说，我不确定这个东西是不是叫做败者树，因为我觉得它就是以前写过n遍的线段树的一个简单变种。
在线段树的每个节点存储v, i，分别表示该区间内最小值和最小值所在单元的索引。
建立好线段树以后，每次取出整个区间的最小值，然后将该值来源的那一路的下一个数字填充进去
如果那一路已经没有下一个数字了，就填一个max进去，然后递归地更新其所有祖先节点。
这个过程有点像heap的sift_up。

代码如下:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

struct node_t{
    int l, r, v, i;
};
node_t d[1024];
int n;
int a[][5] = {
    {7,8,10,13,14},
    {0,3,6,12,19},
    {2,4,5,7,10},
    {15,17,19,21,23},
    {5,8,9,20,22}
};
int idx[5] = {1,1,1,1,1};

void make(int l, int r, int i = 1){
    if(l > r) return;
    int m = (l + r) / 2;
    /*
    printf("[%d, %d, %d] @ %d, ", l, m, r, i);
    if(l == r) printf("%d", a[l][0]);
    printf("\n");
    */
    d[i].l = l, d[i].r = r;
    if(l < r){
        make(l, m, 2 * i);
        make(m + 1, r, 2 * i + 1);
        if(d[2*i].v < d[2*i+1].v){
            d[i].v = d[2*i].v;
            d[i].i = d[2*i].i;
        }else{
            d[i].v = d[2*i + 1].v;
            d[i].i = d[2*i+1].i;
        }
    }else if(l == r){
        d[i].v = a[l][0];
        d[i].i = i;
    }
}

void dump(int i = 1, int dep = 0){
    for (int j = 0; j < dep; ++j) printf("  ");
    printf("[%d, %d] @ %d (%d @ %d)\n", d[i].l, d[i].r, i, d[i].v, d[i].i);
    if(d[i].l < d[i].r) {
        dump(2*i, dep+1);
        dump(2*i+1, dep+1);
    }
}

int main(){
    make(0, 4);
    dump();
    int cnt = 0;
    while(cnt < 25){
        int t = d[1].i;
        int i = d[t].l;
        printf("%2d @ %d FROM %d\n", d[t].v, d[t].i, i);

        if(idx[i] < 5){
            d[t].v = a[i][idx[i]++];
        }else{
            //printf("QUEUE %d OVER\n", i);
            d[t].v = 1000000;
        }

        while(t > 1){
            t /= 2;
            if(d[2*t].v < d[2*t+1].v){
                d[t].v = d[2*t].v;
                d[t].i = d[2*t].i;
            }else{
                d[t].v = d[2*t + 1].v;
                d[t].i = d[2*t+1].i;
            }
        }

        cnt++;
    }
    return 0;
}



Generated by Bo-blog 2.1.0