本人尝试使用MAP用更为简单的方式来实现珂朵莉树(ODT)。
以下是Luogu P1047 校门外的树的MAP珂朵莉树解法。
这个程序在输入完所有数据以后死循环。经判断,怀疑是query函数炸了,但是不会改。
在运算过程中很可能还有其他的问题,如果有发现,也烦请答主一并提醒下。
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
template<typename any>struct odt {
std::map<int, any> Senio;
inline void insert(int l, any val) {Senio.insert(pair<int, any>(l, val));}
inline any find(any target) {return Senio.lower_bound(target) -> second;}
inline auto begin() {return Senio.begin();}
inline auto end() {return Senio.end();}
inline auto split(int p) {
any pos = find(p);
Senio.insert(pair<int, any>(p, pos));
return pos;
}
inline auto range(int l, int r) {
auto left = split(l-1);
auto right = split(r);
return make_pair(left ,right);
}
//public:
inline auto assign(int l, int r, any k) {
auto border = range(l, r);
auto st = border.first;
auto ed = border.second;
while (st != ed) Senio.erase(ed--);
insert(r, k);
}
};
odt<int> ODT;
inline int query() {
int ans = 0;
auto st = ODT.begin();
auto ed = ODT.end();
while (st != ed) ans += (ed -> second - st -> second) + 1;
return ans;
}
int l, m, lbound, rbound;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> l >> m;
ODT.insert(l, true);
for(int i = 0; i < m; ++i) {
cin >> lbound >> rbound;
ODT.assign(lbound, rbound, false);
}
cout << query() << "\n";
return 0;
}