< siomi sakaさんのAI生成コード置き場

セグメント木（クラウドで作成）

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

#include "stdlib.h"
#include "stdio.h"

// ==================================================================
// 設定エリア:ここはいじる可能性があるのでmainの上に置く
// ==================================================================

#define SEG_N (500005)
#define SEG_MAX_TREES (2)

typedef struct {
    long long val;
    int pos;
} skey_t;

// モードの種類を列挙しておく
enum {
    seg_m_min,
    seg_m_max,
    seg_m_sum
};

static int seg_mode[SEG_MAX_TREES]; // id番目の木がどのモードかを覚えておく

static skey_t seg_identity(int id){ /**valが初期化先 posが番兵 */
    skey_t e;
    switch(seg_mode[id]){
        case seg_m_min:
            e.val = (1LL<<60);
            e.pos = -1;
            return e;
        case seg_m_max:
            e.val = -(1LL<<60);
            e.pos = -1;
            return e;
        case seg_m_sum:
            e.val = 0;
            e.pos = -1;
            return e;
        default:
            e.val = 0;
            e.pos = -1;
            return e;
    }
}

// モードごとの集約ロジック
static skey_t scomb(int id, skey_t a, skey_t b){
    skey_t r;
    switch(seg_mode[id]){
        case seg_m_min:
            if(a.val < b.val){
                return a;
            }else{
                return b;
            }
            break;
        case seg_m_max:
            if(a.val > b.val){
                return a;
            }else{
                return b;
            }
            break;
        case seg_m_sum:
            r.val = a.val + b.val;
            r.pos = -1; // 和では位置に意味がないので使わない
            return r;
            break;
        default:
            return a;
            break;
    }
}



void seg_init(int id, int mode, int n); /**id mode 要素数 n  */
void seg_update(int id, int idx, skey_t val);
skey_t seg_query(int id, int ql, int qr);




int main(void){
    seg_init(0,seg_m_min, (200000+100)*4);
    seg_init(1,seg_m_max,(200000+100)*4);

    return 0;
}


// ==================================================================
// 内部実装:通常はここから下を編集する必要はない
// ==================================================================

static skey_t seg[SEG_MAX_TREES][SEG_N*4+10];
static int seg_n[SEG_MAX_TREES];

static void seg_build(int id, int node, int l, int r){
    if(l==r){
        seg[id][node]=seg_identity(id);
        return;
    }
    int mid=(l+r)/2;
    seg_build(id, node*2, l, mid);
    seg_build(id, node*2+1, mid+1, r);
    seg[id][node]=scomb(id, seg[id][node*2], seg[id][node*2+1]);
}


void seg_init(int id, int mode, int n){
    seg_mode[id]=mode;
    seg_n[id]=n;
    seg_build(id, 1, 0, n-1);
}

static void seg_update_rec(int id, int node, int l, int r, int idx, skey_t val){
    if(l==r){
        seg[id][node]=val;
        return;
    }
    int mid=(l+r)/2;
    if(idx<=mid){
        seg_update_rec(id, node*2, l, mid, idx, val);
    }else{
        seg_update_rec(id, node*2+1, mid+1, r, idx, val);
    }
    seg[id][node]=scomb(id, seg[id][node*2], seg[id][node*2+1]);
}

void seg_update(int id, int idx, skey_t val){
    seg_update_rec(id, 1, 0, seg_n[id]-1, idx, val);
}

static skey_t seg_query_rec(int id, int node, int l, int r, int ql, int qr){
    if(qr<l || r<ql) return seg_identity(id);
    if(ql<=l && r<=qr) return seg[id][node];
    int mid=(l+r)/2;
    skey_t lv=seg_query_rec(id, node*2, l, mid, ql, qr);
    skey_t rv=seg_query_rec(id, node*2+1, mid+1, r, ql, qr);
    return scomb(id, lv, rv);
}

skey_t seg_query(int id, int ql, int qr){
    return seg_query_rec(id, 1, 0, seg_n[id]-1, ql, qr);
}