动态开点线段树
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();*/
