主打一个看到别人学什么我学什么，反正什么也不会。
什么是 ODT
是一种数据结构
类比线段树的话，他的每一条线段（一个基本单位）记录了相同 "颜色" 的东西的信息
使用一个结构体的 \(set\)，记录 区间 \([l,r]\) 的信息都为 \(k\)
时间复杂度
随机数据可能是 \(O(n)\) 的，一般可以认为是 \(O(nlogn)\) ，但有时也可以卡到 \(nlog^2n\)
不知道，差不多用就是了
解决什么问题
根据其特性，可以解决区间 \(k\) 大，区间元素幂的和...
还有什么做到了再说.....
ODT 怎么维护
核心是 Split 操作
对于一个 \(pos\) 的修改，找到覆盖 \(pos\) 的区间 \([l,r]\) ，将他分开变成 \([l,pos-1],[pos,r]\) ，然后返回 \([pos,r]\) 区间的迭代器
区间修改操作
将 \([l,r]\) 赋值为 \(x\) ，先 \(split(r+1)\) ,再 \(split(l)\)
原因就是 \(split(l)\) 会影响后面的值
然后删掉两个迭代器中间的信息，全部变成一个 \([l,r],x\)
所以我们得到模版代码，有一些不常用的东西
模版
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IT set<node>::iterator
struct node{int l,r;mutable ll v;//mutable就是你在用迭代器访问的时候也可以直接赋值 bool operator < (const node &a)const {return l<a.l;}
};
set<node> s;
IT split(int pos){IT it=s.lower_bound(node{pos,0,0});if(it!=s.end()&&is->l==pos)return it;it--;if((it->r)<pos)return s.end();//写指针注意加括号int l=it->l,r=it->r;ll v=it->v;s.erase(it);s.insert(node{l,pos-1,v});return s.insert(node{pos,r,v}).first;//set.insert返回一个 pair ：first指向插入后该元素的迭代器，second则为bool表示插入是否成功。
}
void upd(int l,int r,int x){IT itr=split(r+1);//因为我们要拆出 $[l,r]$ 而split会拆出 [l,pos-1]所以应该是r+1IT itl=split(l);s.erase(itl,itr);//表示删除两迭代器中间的所有元素s.insert(node{l,r,x});
} 例题
对于 \(ODT\) 的题，答案的维护一般就在 \(upd\) 函数里，没有固定模版
CF915E
非工作日为 \(0\) ，工作日为 \(1\) ，就是维护全局和，那就每次减去旧区间和加上新的
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
#define ll long long
#define IT set<node>::iterator
int n,q;
struct node{int l,r;mutable ll v;bool operator < (const node &a)const {return l<a.l;}
};
set<node>s;
IT split(int pos){IT it=s.lower_bound(node{pos,0,0});if(it!=s.end()&&it->l==pos)return it;it--;if(it->r<pos)return s.end();int l=it->l,r=it->r;ll v=it->v;s.erase(it);s.insert(node{l,pos-1,v});return s.insert(node{pos,r,v}).first;
}
ll ans=0;
void upd(int l,int r,int x){IT itr=split(r+1),itl=split(l);for(IT it=itl;it!=itr;it++)ans-=1ll*(it->v)*((it->r)-(it->l)+1);ans+=1ll*(r-l+1)*x;s.erase(itl,itr);s.insert(node{l,r,x});
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>q;ans=n;s.insert(node{1,n,1});while(q--){int l,r,x;cin>>l>>r>>x;upd(l,r,x-1);cout<<ans<<"\n";}return 0;
}