珂朵莉树的map实现

文章目录

• 1 引入
• 2 珂朵莉树的map实现原理
• 3 珂朵莉树的map实现方法
• • 3.1 初始化操作
  • 3.2 split操作
  • 3.3 assign操作
  • 3.4 其他操作
• 4 CF1638E的珂朵莉树实现代码

1 引入

最近看jiangly的CF1638E代码，发现jiangly的珂朵莉树是用map实现的。于是研究学习了一下。

CF1638E jiangly代码

如果没有接触过珂朵莉树，请先学习下面的内容。

珂朵莉树原理及set实现

珂朵莉树的复杂度分析

CF1638E 珂朵莉树题解

2 珂朵莉树的map实现原理

珂朵莉树的set实现中，一个区间被记为 $[l,r,val]$ ，分别表示区间左端点，区间右端点，和区间所储存的值。

但是，由于珂朵莉树的区间和区间时相邻的，本区间的右端点一定为下一个区间的左端点，所以我们可以将一个区间简单记为 $[l,val]$ ，分别表示区间的左端点和区间所储存的值。

这样，我们就可以直接用标准库里map，对于一个区间，我们将 $l$ 记为map里的key值，将 $val$ 记为map里的value值。这样写起来更容易，代码量也更小。

3 珂朵莉树的map实现方法

先直接上完整代码。

struct ODT {const int n;map<int, int> mp;ODT(int n) : n(n) { mp[-1] = 0 }void split(int x) {auto it = prev(mp.upper_bound(x)); //找到左端点小于等于x的区间mp[x] = it->second; //设立新的区间，并将上一个区间储存的值复制给本区间。}void assign(int l, int r, int v) { // 注意，这里的r是区间右端点+1split(l);split(r);auto it = mp.find(l);while (it->first != r) {it = mp.erase(it);}mp[l] = v;}void update(int l, int r, int c) { // 其他操作split(l);split(r);auto it = mp.find(l);while (it->first != r) {// 根据题目需要做些什么it = next(it);}}
};

然后我们逐一进行讲解

3.1 初始化操作

设区间下标为$[0,n-1]$。
由于一开始只有一个区间，即$[0,n-1]$，那么我们初始化时，只用插入一个左端点为 $0$ 的区间。

	ODT(int n) : n(n) { mp[-1] = 0 }

3.2 split操作

假设我们需要以 $x$ 为左端点建立新区间，我们直接在map中找到左端点小于等于 $x$ 的区间，设立新的区间，并将上一个区间储存的值复制给本区间。

	void split(int x) {auto it = prev(mp.upper_bound(x)); //找到左端点小于等于x的区间mp[x] = it->second; //设立新的区间，并将上一个区间储存的值复制给本区间。}

3.3 assign操作

对于assign操作，我们需要把$[l,r-1]$内所有区间左端点删除，再建立新的区间。

    void assign(int l, int r, int v) { // 注意，这里的r是区间右端点+1split(l);split(r);auto it = mp.find(l);while (it->first != r) {it = mp.erase(it);}mp[l] = v;}
};

3.4 其他操作

	void update(int l, int r, int c) { // 其他操作split(l);split(r);auto it = mp.find(l);while (it->first != r) {// 根据题目需要做些什么it = next(it);}}

4 CF1638E的珂朵莉树实现代码

#include 
using namespace std;using i64 = long long;
using ldb = long double;
#define int i64
#define double ldbtemplate <typename T>
struct BIT {const int n;std::vector<T> a;BIT(int n) : n(n), a(n) {}void add(int x, T v) {for (int i = x + 1; i <= n; i += i & -i) {a[i - 1] += v;}}void rangeAdd(int l, int r, T v) {add(l, v);add(r, -v);}T sum(int x) {T ans = 0;for (int i = x + 1; i > 0; i -= i & -i) {ans += a[i - 1];}return ans;}T rangeSum(int l, int r) {return sum(r) - sum(l);}
};struct ODT {const int n;map<int, int> mp;vector<int> lazy;BIT<int> bit;ODT(int n) : n(n), lazy(n), bit(n) { mp[-1] = 0; }void split(int x) {auto it = prev(mp.upper_bound(x));mp[x] = it->second;}void assign(int l, int r, int v) {split(l);split(r);auto it = mp.find(l);while (it->first != r) {it = mp.erase(it);}mp[l] = v;}void update(int l, int r, int c) {split(l);split(r);auto it = mp.find(l);while (it->first != r) {bit.rangeAdd(it->first, next(it)->first, lazy[it->second] - lazy[c]);it = next(it);}}void add(int c, int x) {lazy[c] += x;}int query(int x) {split(x);return bit.sum(x) + lazy[mp[x]];}
};signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, q;cin >> n >> q;ODT odt(n);for (int i = 0; i < q; i++) {string op;cin >> op;if (op == "Color") {int l, r, c;cin >> l >> r >> c;l--;c--;odt.update(l, r, c);odt.assign(l, r, c);}else if (op == "Add") {int c, x;cin >> c >> x;c--;odt.add(c, x);}else if (op == "Query") {int x;cin >> x;x--;cout << odt.query(x) << "\n";}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！