珂朵莉树ODT 模板

构造 set ：

struct node{
    int l , r;
    mutable int v;
    node(int l,int r,int v = 0) : l(l) , r(r) , v(v) {}
    bool operator<(const node &a) const {
        return l < a.l;
    }
};
set<node> s;

分裂 set ：

auto split(int pos) {
    auto 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;
    int r = it->r;
    int v = it->v;
    s.erase(it);
    s.insert(node(l , pos - 1 , v));
    return s.insert(node(pos , r , v)).first;
}

推平区间：

void pushdown(int l,int r,int x) {
    auto itr = split(r + 1) , itl = split(l);
    s.erase(itl , itr);
    s.insert(node(l , r , x));
}

void add(int l,int r,int x) {
    auto itr = split(r + 1) , itl = split(l);
    for(auto it = itl;it != itr;it++)
        it->v += x;
}

Rank 结构体定义：

struct Rank {
    int num , cnt;
    Rank(int num , int cnt) : num(num) , cnt(cnt) {}
    bool operator<(const Rank &a) const {
        return num < a.num;
    }
};

区间 第x小 ：

int rnk(int l,int r,int x) {
    auto itr = split(r + 1) , itl = split(l);
    vector<Rank> v;
    for(auto i = itl;i != itr;i++)
        v.push_back(Rank(i->v , i->r - i->l + 1));
    sort(v.begin() , v.end());
    int flag = v.size() - 1;
    for(int i=0;i < v.size();i++)
        if(v[i].cnt < x) x -= v[i].cnt;
            else {
                flag = i;
                break;
            }
    return v[flag].num;
}

区间每个数 x次方 求和：

int calp(int l,int r,int x,int y) {
    auto itr = split(r + 1) , itl = split(l);
    int ans = 0;
    for(auto i = itl;i != itr;i++)
        ans = (ans + ksm(i->v , x , y) * (i->r - i->l + 1) % y) % y;
    return ans;
}