1. struct ODT {
  2.     const int n;
  3.     map<int, int> mp;
  4.     ODT(int n) : n(n) { mp[-1] = 0; }
  5.     void split(int x) {
  6.         auto it = prev(mp.upper_bound(x)); //找到左端点小于等于x的区间
  7.         mp[x] = it->second; //设立新的区间，并将上一个区间储存的值复制给本区间。
  8.     }
  9.     void assign(int l, int r, int v) { // 注意，这里的r是区间右端点+1
  10.         split(l);
  11.         split(r);
  12.         auto it = mp.find(l);
  13.         while (it->first != r) {
  14.             it = mp.erase(it);
  15.         }
  16.         mp[l] = v;
  17.     }
  18.     void update(int l, int r, int c) { // 其他操作
  19.         split(l);
  20.         split(r);
  21.         auto it = mp.find(l);
  22.         while (it->first != r) {
  23.             // 根据题目需要做些什么
  24.             it = next(it);
  25.         }
  26.     }
  27. };

相关链接

  1. https://zhuanlan.zhihu.com/p/469794466