动态开点线段树
Problem One
P2781 传教 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
动态开点,注意 long long
。
区间加 + 区间求和。
#include<bits/stdc++.h>
using namespace std;
#define N 80010
typedef long long ll;
int n, m, root, tot;
int ls[N], rs[N];
ll sum[N], add[N];
void pushup(int u){
sum[u] = sum[ls[u]] + sum[rs[u]];
}
void pushdown(int u, int l, int r){
if(!add[u]) return ;
if(!ls[u]) ls[u] = ++ tot;
if(!rs[u]) rs[u] = ++ tot;
int mid = l + r >> 1;
sum[ls[u]] += add[u] * (mid - l + 1);
sum[rs[u]] += add[u] * (r - mid);
add[ls[u]] += add[u];
add[rs[u]] += add[u];
add[u] = 0;
}
void change(int &u, int l, int r, int x, int y, ll k){
if(!u) u = ++ tot; // 动态开点
if(x <= l && y >= r){
sum[u] += (r - l + 1) * k;
add[u] += k;
return ;
}
int mid = l + r >> 1;
pushdown(u, l, r);
if(x <= mid) change(ls[u], l, mid, x, y, k);
if(y > mid) change(rs[u], mid + 1, r, x, y, k);
pushup(u);
}
ll ask(int &u, int l, int r, int x, int y){
if(!u) u = ++ tot;
if(x <= l && y >= r) return sum[u];
int mid = l + r >> 1;
pushdown(u, l, r);
ll res = 0;
if(x <= mid) res += ask(ls[u], l, mid, x, y);
if(y > mid) res += ask(rs[u], mid + 1, r, x, y);
return res;
}
signed main(){
cin >> n >> m;
for(int i = 1, l, r, opt; i <= m; i ++){
ll k;
cin >> opt >> l >> r;
if(opt == 1){
cin >> k;
change(root, 1, n, l, r, k);
}
else{
cout << ask(root, 1, n, l, r) << '\n';
}
}
return 0;
}
Problem Two
2276. 统计区间中的整数数目 - 力扣(LeetCode)
给你区间的 空 集,请你设计并实现满足要求的数据结构:
- 新增:添加一个区间到这个区间集合中。
- 统计:计算出现在至少一个区间中的整数个数。
实现
CountIntervals
类:
CountIntervals()
使用区间的空集初始化对象void add(int left, int right)
添加区间[left, right]
到区间集合之中。int count()
返回出现在 至少一个 区间中的整数个数。注意:区间
[left, right]
表示满足left <= x <= right
的所有整数x
。
区间修改为 1 1 1 + 区间求和。使用动态开点线段树实现。
int n = 1000000000;
constexpr int N = 100000 * 3 * __lg(100000);
int tot = 0, root = 0;
int ls[N], rs[N], sum[N], tag[N];
class CountIntervals {
public:
CountIntervals() {
memset(tag, 0, sizeof tag);
memset(sum, 0, sizeof sum);
memset(ls, 0, sizeof ls);
memset(rs, 0, sizeof rs);
}
void pushup(int u){
sum[u] = sum[ls[u]] + sum[rs[u]];
}
void pushdown(int u, int l, int r){
if(tag[u] == 0) return ;
if(!ls[u]) ls[u] = ++ tot;
if(!rs[u]) rs[u] = ++ tot;
int mid = l + r >> 1;
sum[ls[u]] = (mid - l + 1);
sum[rs[u]] = r - mid;
tag[ls[u]] = tag[rs[u]] = 1;
tag[u] = 0;
}
void change(int &u, int l, int r, int x, int y){
if(!u) u = ++ tot;
if(x <= l && y >= r){
sum[u] = r - l + 1;
tag[u] = 1;
return ;
}
int mid = l + r >> 1;
pushdown(u, l, r);
if(x <= mid) change(ls[u], l, mid, x, y);
if(y > mid) change(rs[u], mid + 1, r, x, y);
pushup(u);
}
void add(int left, int right) {
change(root, 1, n, left, right);
}
int ask(int &u, int l, int r, int x, int y){
if(!u) u = ++ tot;
if(x <= l && y >= r) return sum[u];
int mid = l + r >> 1;
pushdown(u, l, r);
int res = 0;
if(x <= mid) res += ask(ls[u], l, mid, x, y);
if(y > mid) res += ask(rs[u], mid + 1, r, x, y);
return res;
}
int count() {
return sum[root];
}
};
/**
* Your CountIntervals object will be instantiated and called as such:
* CountIntervals* obj = new CountIntervals();
* obj->add(left,right);
* int param_2 = obj->count();
*/