# Untitled

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(){

}```