老司机树(Chtholly Tree (珂朵莉树) ODT)模板[codeforces 896C Willem, Chtholly and Seniorious]

http://codeforces.com/contest/896/problem/C

由于题目数据随机生成，而且有合并区间的特性（据说合并后区间个数期望值跟logn有关）。

所以可以利用内置平衡树set合并区间信息并暴力。

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

typedef long long ll;
const int mod7 = 1e9 + 7;
const int maxn = 1e5 + 7;

ll pow(ll a, ll b, ll mod){
    ll res=1;
    for(a%=mod;b;a=a*a%mod,b>>=1)
        if(b&1)res=res*a%mod;
    return res;
}
struct node{
    ll l,r;
    mutable ll v;
    node(ll l,ll r=-1,ll v=0):l(l),r(r),v(v){};
    bool operator<(const node& o) const {
        return l < o.l;
    }
};
set<node>ODT;

ll n,m,seed,vmax;

ll rnd(){
    ll ret=seed;
    seed=(seed*7+13)%mod7;
    return ret;
}
// 拆分操作
set<node>::iterator split(int pos){
    auto it=ODT.lower_bound(node(pos));
    if(it !=ODT.end()&&it->l==pos)return it;
    --it;
    if(pos>it->r)return ODT.end();
    int L=it->l,R=it->r;
    ll V=it->v;
    ODT.erase(it);
    ODT.insert(node(L,pos-1,V));
    return ODT.insert(node(pos,R,V)).first;
}
//区间加操作
void add(int l,int r,ll val){
    for(auto itl=split(l),itr=split(r+1);itl!=itr;++itl)itl->v+=val;
}
//区间加赋值
void up(int l,int r,int val){
    auto itl=split(l),itr=split(r+1);
    ODT.erase(itl,itr);
    ODT.insert(node(l,r,val));
}

ll sum(int l,int r,int ex,int mod){
    ll res=0;
    for(auto itl=split(l),itr=split(r+1);itl!=itr;++itl){
        res =(res+(itl->r-itl->l+1)*pow(itl->v,ex,mod))%mod;
    }
    return res;
}
//求区间第K大值，reversed控制顺序与逆
ll rk(int l, int r, int k, bool reversed=0){
    vector<pair<ll,int>> vp;
    vp.clear();
    if (reversed) k = r-l+2-k;
    for (auto itl=split(l),itr=split(r+1);itl!=itr;++itl)
        vp.push_back({itl->v,itl->r-itl->l+1});
    sort(vp.begin(),vp.end());
    for (auto i:vp){
        k -=i.second;
        if(k<=0)return i.first;
    }
    return -1LL;
}

int main(){
    scanf("%lld%lld%lld%lld",&n,&m,&seed,&vmax);
    for(int i=1;i<=n;i++)
        ODT.insert(node(i,i,rnd()%vmax+1));

    for(;m;--m){
        int x,y,op=rnd()%4+1,l=rnd()%n+1,r=rnd()%n+1;
        if(l>r)swap(l,r);
        if (op == 3)
            x=rnd()%(r-l+1)+1;
        else
            x=rnd()%vmax+1;
        if(op==4)y=rnd()%vmax+1;
        switch(op){
            case 1:add(l,r,x);              break;
            case 2:up(l,r,x);               break;
            case 3:cout<<rk(l,r,x)<<endl;   break;
            case 4:cout<<sum(l,r,x,y)<<endl;break;
        }
    }
    return 0;
}