珂朵莉树Chtholly

珂朵莉·诺塔·瑟尼欧里斯

对区间宝具，真正的珂学

struct Chtholly //[l, r]闭区间
{
    ll l, r;
    mutable ll v;
    Chtholly(ll L, ll R = -1, ll V = 0) : l(L), r(R), v(V) {}
    bool operator < (const Chtholly &x)const{ return l < x.l; } //按左端点排序
};
using It = set<Chtholly>::iterator;
set<Chtholly>tr;
It split(int pos) //分割区间
{
    It it = tr.lower_bound(Chtholly(pos)); //找到所需的pos的迭代器
    if(it != tr.end() && it->l == pos) return it; //看看这个迭代器的l是不是所需要的pos，是的话直接返回就行
    --it; //不是的话就说明肯定是在前一个里面
    ll l = it->l, r = it->r, v = it->v;
    tr.erase(it);
    tr.insert(Chtholly(l, pos - 1, v)); //拆分成两个区间[l, pos),[pos, r] //[pos, r]就是闭区间
    return tr.insert(Chtholly(pos, r, v)).first; //返回以pos开头的区间的迭代器
}
void emerge(int l, int r, ll x) //合并区间||区间修改
{
    It itr = split(r + 1), itl = split(l); //先找到r+1的迭代器位置，再找l的迭代器位置
    tr.erase(itl, itr); //删掉这一段迭代器
    tr.insert(Chtholly(l, r, x)); //重新插入所需区间
}
void delta(int l, int r, ll x) //区间值加减,O(m),m为[l,r]内区间个数
{
    It itr = split(r + 1), itl = split(l);
    for(;itl != itr; ++itl) itl->v += x;
}
ll query(ll l, ll r, ll pos) //单点查询
{
    It it = tr.lower_bound(Chtholly(pos));
    if(it != tr.end() && it->l == pos) return it.v;
    return (--it).v;
}
ll query_k(ll l, ll r, ll k) //查询区间[l, r]里排名为k的数,O(mlogm),m为[l,r]内区间个数
{
    It itr = split(r + 1), itl = split(l);
    vector<pair<ll, ll>> tmp;
    for (; itl != itr; ++itl) tmp.pb(make_pair(itl->v, itl->r - itl->l + 1));
    sort(tmp.begin(), tmp.end());
    for (auto it : tmp) if ((k -= it.se) <= 0) return it.fi;
    return -1; //没k个数返回-1
}