CF 896C - Willem, Chtholly and Seniorious （珂朵莉树）

给 $n$n 个整数 $\{a_i\}${ai​}，进行 $m$m 次操作，操作类型如下：

• 1 l r x ：区间 [l,r] 上每个数 +x
• 2 l r x ：区间 [l,r] 上每个数 =x
• 3 l r x ：区间 [l,r] 上第 x 小的数
• 4 l r x y：计算 $(\sum_{i=l}^ra_i^x)\bmod y$(∑i=lr​aix​)mody

输入为 n,m,seed,v_max ，根据以下函数来生成 $\{a_i\}${ai​} 以及每次的具体操作：

def rnd():

    ret = seed
    seed = (seed * 7 + 13) mod 1000000007
    return ret

for i = 1 to n:

    a[i] = (rnd() mod vmax) + 1

for i = 1 to m:

    op = (rnd() mod 4) + 1
    l = (rnd() mod n) + 1
    r = (rnd() mod n) + 1

    if (l > r): 
         swap(l, r)

    if (op == 3):
        x = (rnd() mod (r - l + 1)) + 1
    else:
        x = (rnd() mod vmax) + 1

    if (op == 4):
        y = (rnd() mod vmax) + 1

珂朵莉树的起源就是这道题（CF 896C），作者先后将其命名为 Old Driver Tree（老司机树）、Chtholly Tree（珂朵莉树）

其核心思想是用结点来维护一段连续的区间，该连续区间上每个元素的值是相同的，所以所有的初始结点被划分成了许多小区间，这些小区间形成的结点用一个 set 来维护（其背后用红黑树来实现，保证插入/查找/删除都是 $\log n$logn 的复杂度），结点定义如下：

struct Node{
    int l,r;
    mutable ll v; // mutable 保证在add中可以对v进行修改
    Node(){}
    Node(int _l,int _r=-1,ll _v=0):l(_l),r(_r),v(_v){}
    bool operator<(const Node& b)const {return l<b.l;}
};

珂朵莉树的复杂度由随机的数据来保证，因为在随机数据下，有 $\dfrac{1}{4}$41​ 的操作是 assign 操作，即区间赋值，或者说是“推平一段区间”，这个操作使得许多结点可以合并成一个结点，从而使 set 中的元素个数迅速减少（大约是 $O(m\log n)$O(mlogn)）。

其核心操作是一个 split(l,r,pos) ，目的是将 [l,r] 拆成 [l,pos-1],[pos,r] 两个区间，从而将 pos 这个位置露出来，方便区间加、区间赋值、第 k 大查询等操作。

IT split(int pos){
    IT it=s.lower_bound(Node(pos)); 
    // lower_bound: 第一个>=val的下标（upper_bound是第一个>val的下标）
    if(it!=s.end()&&it->l==pos)return it; // 存在左界为pos的Node
    --it; // 此时it指向的结点保证pos在其左右区间内
    int l=it->l,r=it->r;ll v=it->v;
    s.erase(it);s.insert(Node(l,pos-1,v));
    return s.insert(Node(pos,r,v)).first;
    // insert函数返回的是一个pair<iterator,bool>,first是指向新插入元素的iterator
}

完整代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<utility> // pair
#define M7 1000000007
#define MAXN 100007
#define IT set<Node>::iterator
using namespace std;
typedef long long ll;
int n,m;
ll seed,vmax,a[MAXN];
struct Node{
    int l,r;
    mutable ll v; // mutable 保证在add中可以对v进行修改
    Node(){}
    Node(int _l,int _r=-1,ll _v=0):l(_l),r(_r),v(_v){}
    bool operator<(const Node& b)const {return l<b.l;}
};
set<Node> s;
IT split(int pos){
    IT it=s.lower_bound(Node(pos)); 
    // lower_bound: 第一个>=val的下标（upper_bound是第一个>val的下标）
    if(it!=s.end()&&it->l==pos)return it; // 存在左界为pos的Node
    --it; // 此时it指向的结点保证pos在其左右区间内
    int l=it->l,r=it->r;ll v=it->v;
    s.erase(it);s.insert(Node(l,pos-1,v));
    return s.insert(Node(pos,r,v)).first;
    // insert函数返回的是一个pair<iterator,bool>,first是指向新插入元素的iterator
}
void add(int l,int r,ll val=1){ // 首先需要通过split将l,r能分成某些结点的左右
    // 因为set中的Node表示是[L,R]上都为v,而需要操作的两个区间端点l,r可能在结点的区间内部，
    // 如 L<l<R 或 L<r<R，所以要通过split，将 [L,R] 分裂成两个结点 [L,l-1],[l,R]
    IT itl=split(l),itr=split(r+1);
    for(;itl!=itr;itl++)itl->v+=val;
}
void assign(int l,int r,ll val=0){ // 区间推平成一个相同的值
    IT itl=split(l),itr=split(r+1); // 也是首先通过split操作把l,r暴露出来
    s.erase(itl,itr); // 删掉l,r区间的所有结点
    s.insert(Node(l,r,val)); // 插入一个新的结点，表示[l,r]上都是val
}
ll rnk(int l,int r,int k){
    vector<pair<ll,int>> vp;
    IT itl=split(l),itr=split(r+1);
    for(;itl!=itr;++itl) // 用vector存储区间元素，便于排序
        vp.push_back(pair<ll,int>(itl->v,itl->r-itl->l+1));
    sort(vp.begin(),vp.end());
    for(vector<pair<ll,int>>::iterator it=vp.begin();it!=vp.end();it++){
        k-=it->second;
        if(k<=0)return it->first;
    }
    return -1ll;
}
ll pow(ll a,ll b,ll M){ // 快速幂
    ll res=1,p=a%M;
    while(b){
        if(b&1)res=res*p%M;
        p=p*p%M;b>>=1;
    }
    return res;
}
ll sum(int l,int r,int e,int M){
    IT itl=split(l),itr=split(r+1);
    ll res=0;
    for(;itl!=itr;itl++) // 遍历所有的小区间
        res=(res+ll(itl->r-itl->l+1)*pow(itl->v,ll(e),ll(M)))%M;
    return res;
}
ll rnd(){
    ll res=seed;
    seed=(seed*7+13)%M7;
    return res;
}
int main(){
#ifdef WINE
    freopen("data.in","r",stdin);
#endif
    scanf("%d%d%lld%lld",&n,&m,&seed,&vmax);
    for(int i=1;i<=n;i++){
        a[i]=(rnd()%vmax)+1;
        s.insert(Node(i,i,a[i]));
    }
    s.insert(Node(n+1,n+1,0));
    for(int i=1;i<=m;i++){
        int op=int(rnd()%4)+1;
        int l=int(rnd()%m)+1;
        int r=int(rnd()%n)+1;
        if(l>r)swap(l,r);
        int x,y;
        if(op==3)x=int(rnd()%(r-l+1))+1;
        else x=int(rnd()%vmax)+1;
        if(op==4)y=int(rnd()%vmax)+1;
        if(op==1)add(l,r,ll(x)); // 区间加
        else if(op==2)assign(l,r,ll(x)); // 区间赋值
        else if(op==3)printf("%lld\n",rnk(l,r,x)); // 区间第k大
        else printf("%lld\n",sum(l,r,x,y)); // 区间幂和
    }
    return 0;
}