CF896C 珂朵莉树

题目链接：https://www.luogu.com.cn/problem/CF896C
题目大意：

这个数据读入有点毒瘤，其他解是模板了。

#include <bits/stdc++.h>
#define ll long long
#define sit set<node>::iterator
using namespace std;

struct node{
    int l, r;
    mutable ll val;
    int operator<(const node &a) const{
        return l<a.l;
    }
    node(int L, int R, ll Val): l(L), r(R), val(Val){}
    node(int L) : l(L){}
};

struct odTree{
    set<node> s;
    sit Split(int pos){//一个节点分裂[l, r]->[l, pos-1]+[pos, r]
        sit it=s.lower_bound(node(pos));
        if(it!=s.end()&&it->l==pos) return it;
        --it;
        int l=it->l, r=it->r;
        ll val=it->val;
        s.erase(it);
        s.insert(node(l, pos-1, val));
        return s.insert(node(pos, r, val)).first;
    }
    void Assign(int l, int r, ll val){//区间赋值
        sit it2=Split(r+1), it1=Split(l);
        s.erase(it1, it2);
        s.insert(node{l, r, val});
    }
    void Add(int l, int r, ll val){//区间[l, r]+=val
        sit it2=Split(r+1), it1=Split(l);
        for(sit it=it1; it!=it2; ++it) it->val+=val;
    }
    ll Kth(int l, int r, int k){//区间[l, r]的第k小
        sit it2=Split(r+1), it1=Split(l);
        vector<pair<ll, int> > aa;
        aa.clear();
        for(sit it=it1; it!=it2; ++it){
            aa.push_back(pair<ll, int>(it->val, it->r-it->l+1) );
        }
        sort(aa.begin(), aa.end());
        for(int i=0; i<aa.size(); ++i){
            k-=aa[i].second;
            if(k<=0) return aa[i].first;
        }
    }
    ll qpow(ll a, int x, ll y){//求a^x%y
        ll b=1ll;
        a%=y;
        while(x){
            if(x&1) b=b*a%y;
            a=a*a%y;
            x>>=1;
        }
        return b;
    }
    ll Query(int l, int r, int x, ll y){//求[l, r], a[i]^x%y的和 暴力枚举+快速幂
        sit it2=Split(r+1), it1=Split(l);
        ll res=0;
        for(sit it=it1; it!=it2; ++it){
            res=(res+(it->r-it->l+1)*qpow(it->val, x, y)%y)%y;
        }
        return res;
    }
}Tree;

int n, m, vmax;
ll seed;
int rd(){
    int ret=(int)seed;
    seed=(seed*7+13)%1000000007;
    return ret;
}

int main(){

    scanf("%d%d%lld%d", &n, &m, &seed, &vmax);
    for(int i=1; i<=n; i++){
        int a=rd()%vmax+1;
        Tree.s.insert(node(i, i, (ll)a));
    }
    Tree.s.insert(node(n+1, n+1, 0));
    for(int i=1; i<=m; i++){
        int l, r, x, y;
        int op=rd()%4+1;
        l=rd()%n+1, r=rd()%n+1;
        if(l>r) swap(l, r);
        if (op == 3) x = rd() % (r - l + 1) + 1;
        else x = rd() % vmax + 1;
        if (op == 4) y = rd() % vmax + 1;
        if (op == 1) Tree.Add(l, r, (ll)x);
        else if (op == 2) Tree.Assign(l, r, (ll)x);
        else if (op == 3) printf("%lld\n", Tree.Kth(l, r, x));
        else if (op == 4) printf("%lld\n", Tree.Query(l, r, x, (ll)y));
    }

    return 0;
}