珂朵莉树学习笔记

xingke233 / 2024-11-09 / 原文

区间操作

$1.$ $\left[L,R\right]$ 区间加上一个数

$2.$ $\left[L,R\right]$区间赋值

适用范围

$1.$ 数据随机 $(因为容易被卡)$

$2.$ 有区间赋值操作 $(核心操作不然和暴力没什么区别了)$

$3.$ 骗分小技巧

习题

CF896C $(起源)$

CF915E

P1840

P4979

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;
}