区间操作
\(1.\) \(\left[L,R\right]\) 区间加上一个数
\(2.\) \(\left[L,R\right]\)区间赋值
适用范围
\(1.\) 数据随机 \((因为容易被卡)\)
\(2.\) 有区间赋值操作 \((核心操作不然和暴力没什么区别了)\)
\(3.\) 骗分小技巧
习题
CF896C \((起源)\)
P4344 \((貌似ODT被卡了....)\)
模板
#include<bits/stdc++.h>
using namespace std;
#define s_it set<node>::iterator
//必须 先左区间 后右区间 s_it it2 = split(r + 1), it1 = split(l);
int n,L,R,m,ans;
struct node{
int l,r;
mutable int v;
node(int a, int b = -1, int c = 0):l(a),r(b),v(c){}
friend bool operator <(const node &a,const node &b){
return a.l<b.l;
}
};
set<node> odt;//初始珂朵莉树
inline int read(){ //快读
int s = 0, w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {
s = (s << 3) + (s << 1) + ch - '0', ch = getchar();
}
return s * w;
}
void print(int x){ //快输
char F[200];
if(x<0){
putchar('-');
x=-x;
}
int cnt=0;
while(x){
F[cnt++]=x%10+'0';
x/=10;
}
while(cnt) putchar(F[--cnt]);
return ;
}
s_it split(int pos){ //分裂
s_it it = odt.lower_bound(node(pos));
if(it!=odt.end()&&it->l==pos){
return it;
}
--it;
int l = it->l, r = it->r,v=it->v;
odt.erase(it);
odt.insert(node(l, pos - 1, v));
return odt.insert(node(pos, r, v)).first;
}
void assign(int l,int r,int v){//推平区间
s_it it2 = split(r + 1), it1 = split(l);
odt.erase(it1,it2);
odt.insert(node(l, r, v));
return;
}
void add(int l,int r,int v){//区间加数
s_it it2 = split(r + 1), it1 = split(l);
for (s_it it = it1; it != it2;++it){
it->v += v;
}
}
void prepare(){
odt.insert(node(1,n+1,1));
}
void work(int l,int r,int v){
s_it it2 = split(r + 1), it1 = split(l);
for (s_it it = it1; it != it2;++it){
//任务
}
}
int main(){
n=read();m=read();
prepare(); //初始化珂朵莉树
work(1,1,1);
return 0;
}