珂朵莉树

#include<bits/stdc++.h>
using namespace std;

struct node{ // 节点
    long long l,r; // 从 l 到 r
    mutable long long v; // 值是v
    node(long long l,long long r,long long v):l(l),r(r),v(v){}; // 构造函数
    bool operator<(const node &n)const {return l < n.l;} // 重载小于号,左端点小的小
};

set<node> s; // set存储

auto split(long long pos){
    auto it = s.lower_bound(node(pos,0,0)); // 找到第一个左端点大于等于pos的节点
    if(it != s.end() && it->l == pos)return it; // 如果找到的节点左端点等于pos,直接返回
    it--; // 否则找到的节点左端点大于pos,所以要找到的节点是it的前一个节点
    long long l = it->l,r = it->r,v = it->v; // 保存找到的节点的左端点,右端点,值
    s.erase(it); // 删除找到的节点
    s.insert(node(l,pos-1,v)); // 插入左端点到pos-1的节点
    return s.insert(node(pos,r,v)).first; // 插入pos到右端点的节点,并返回pos到右端点的节点的迭代器
}

void assign(long long l,long long r,long long v){ // 区间赋值
    auto end = split(r+1),begin = split(l); // 找到左端点为l的节点和右端点为r+1的节点
    s.erase(begin,end); // 删除左端点为l的节点到右端点为r+1的节点
    s.insert(node(l,r,v)); // 插入左端点为l,右端点为r,值为v的节点
}

void add(long long l,long long r,long long v){ // 区间加值
    auto end = split(r+1),begin = split(l); // 找到左端点为l的节点和右端点为r+1的节点
    for(auto it = begin;it != end;it++)it->v += v; // 对左端点为l的节点到右端点为r+1的节点的值加v
}

long long sum(long long l,long long r){ // 区间求和
    long long ans = 0;
    auto end = split(r+1),begin = split(l); // 找到左端点为l的节点和右端点为r+1的节点
    for(auto it = begin;it != end;it++)ans += it->v; // 对左端点为l的节点到右端点为r+1的节点的值求和
    return ans;
}

long long getNthbig(long long l,long long r,long long k){ // 区间第k大(数字相同算一个)
    set<int> st; // set存储
    auto end = split(r+1),begin = split(l); // 找到左端点为l的节点和右端点为r+1的节点
    for(auto it = begin;it != end;it++){
        st.insert(it->v); // 将左端点为l的节点到右端点为r+1的节点的值插入set
        if(st.size() == k)return *--st.end(); // 如果set的大小等于k,返回set的最后一个元素
    }
    return -1; // 否则返回-1
}

long long getNth(long long l,long long r,long long k){ // 区间第k大(数字相同算多个)
    // auto end = split(r+1);
    // vector<pair<int,int> > v; // vector存储
    // for(auto it = split(l);it != end;it++){
    //  v.push_back(make_pair(it->v,it->r-it->l+1)); // 将左端点为l的节点到右端点为r+1的节点的值和区间长度插入vector
    // }
    // sort(v.begin(),v.end()); // 排序
    // for(auto it:v){
    //  if(k <= it.second)return it.first; // 如果k小于等于区间长度,返回值
    //  k -= it.second; // 否则k减去区间长度
    // }
    auto end = split(r+1);
    for(auto it = split(l);it != end;it++){
        if(k <= it->r-it->l+1)return it->v; // 如果k小于等于区间长度,返回值
        k -= it->r-it->l+1; // 否则k减去区间长度
    }
}

long long ksm(long long a,long long b,long long mod){ // 快速幂
    if(b == 1)return a;
    if(b % 2 == 0)return ksm(a,b/2,mod) * ksm(a,b/2,mod) % mod;
    return ksm(a,b/2,mod) * ksm(a,b/2,mod) % mod * a % mod;
}

long long Multiksm(long long l,long long r,long long x,long long y){
    long long ans = 0;
    auto end = split(r+1),begin = split(l); // 找到左端点为l的节点和右端点为r+1的节点
    for(auto it = begin;it != end;it++){
        ans += ksm(it->v,x,y) * (it->r - it->l + 1); // 对左端点为l的节点到右端点为r+1的节点的值求和
        ans %= y;
    }
    return ans;
}
文章评论
