Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.7 kB
2
Indexable
Never
#include<bits/stdc++.h>
using namespace std;

struct Segment_tree{
    int x, la; //node值, lazy
    pair<int, int> seg; //segment
}tree[800000];

void create_tree(int L, int R, int node){ //範圍
    tree[node].la = 0;
    tree[node].seg.first = L;
    tree[node].seg.second = R;
    tree[node].x = 0;
    int mid = (L + R) / 2;
    if(L != R){
        create_tree(L, mid, node * 2);
        create_tree(mid + 1, R, node * 2 + 1);
    }
}

int add_sub_segment(int l, int r, int value, int node){//左值, 右值, 加減的value, 目前的node
    //node區間完全在想要的區間以內,不需再往下做
    if(tree[node].seg.first >= l && tree[node].seg.second <= r){
        tree[node].x = tree[node].x + value;
        tree[node].la = tree[node].la + value;
        return tree[node].x;
    }
    //把lazy值往下做
    tree[node * 2].x += tree[node].la;
    tree[node * 2 + 1].x += tree[node].la;
    tree[node * 2].la += tree[node].la;
    tree[node * 2 + 1].la += tree[node].la;
    tree[node].la = 0;
    int mid = (tree[node].seg.first + tree[node].seg.second) / 2;
    //左右子樹都做
    if(l <= mid && r > mid){
        tree[node].x = min(add_sub_segment(l, mid, value, node * 2), add_sub_segment(mid + 1, r, value, node * 2 + 1));
    }
    //右子樹
    if(l > mid && r >= l){
        tree[node].x = min(tree[node * 2].x ,add_sub_segment(l, r, value, node * 2 + 1));
    }
    //左子樹
    if(l <= r && r <= mid){
        tree[node].x = min(add_sub_segment(l, r, value, node * 2), tree[node * 2 + 1].x);
    }
    return tree[node].x;
}

int search_segment_tree(int l, int r, int node, int save){ // 查找的左值, 查找的右值, 目前的node, 有沒有安全的位置
    if(tree[node].seg.first >= l && tree[node].seg.second <= r){
        if(tree[node].x <= 0){
            save++;
            //cout << node << " node\n";
        }
        return save;
    }
    tree[node * 2].x += tree[node].la;
    tree[node * 2 + 1].x += tree[node].la;
    tree[node * 2].la += tree[node].la;
    tree[node * 2 + 1].la += tree[node].la;
    tree[node].la = 0;
    int mid = (tree[node].seg.first + tree[node].seg.second) / 2;
    if(l <= mid && r > mid){
        save += search_segment_tree(l, mid, node * 2, save);
        save += search_segment_tree(mid + 1, r, node * 2 + 1, save);
        return save;
    }
    if(l > mid && r >= l){
        save += search_segment_tree(l, r, node * 2 + 1, save);
        return save;
    }
    if(l <= r && r <= mid){
        save += search_segment_tree(l, r, node * 2, save);
        return save;
    }
}

int main(){
    
}