[C++知识库]Codeforces Round #449 (Div. 1) C.珂朵莉树模板

珂朵莉树模板，要求支持区间幂次和，注意细节别写挂了。
注意 会爆long long！！！

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

#define int long long

struct node{
    int l, r;
    mutable int val;
    node (int lpos): l(lpos) {}
    node (int lpos, int rpos, int vall): l(lpos), r(rpos), val(vall) {}
    bool operator< (const node &a) const { return l < a.l; }
};

set<node> s;
using sit = set<node>::iterator;

sit split(int pos){
    sit it = s.lower_bound(node(pos));
    if(it != s.end() && it -> l == pos) return it;
    --it;
    int l = it -> l, r = it -> r, 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, int val){
    sit itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(node(l, r, val));
}

void add(int l, int r, int val){
    sit itr = split(r + 1), itl = split(l);
    //for(auto it = itl; it != itr; it++) it -> val += val;
    while(itl != itr) itl -> val += val, itl++;
}

int kth(int l, int r, int k){
    sit itr = split(r + 1), itl = split(l);
    vector<pair<int, int>> v;
    v.clear();
    for(sit it = itl; it != itr; it++) v.emplace_back(make_pair(it -> val, it -> r - it -> l + 1));
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++){
        k -= v[i].second;
        if(k <= 0) return v[i].first;
    }
    return -1;
}

int binpow(int x, int y, int mod, int res = 1){
    for (x %= mod; y; y >>= 1, (x *= x) %= mod) if (y & 1) (res *= x) %= mod;
    return res;
}


int query(int l, int r, int x, int y){
    sit itr = split(r + 1), itl = split(l);
    int res(0);
    for(sit it = itl; it != itr; it++)
        res = (res + (it -> r - it -> l + 1) * binpow(it -> val, x, y)) % y;
    return res;
}

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

inline void solve(){
    cin >> n >> m >> seed >> vmax;
    for(int i = 1; i <= n; i++){
        int a = rnd() % vmax + 1;
        s.insert(node{i, i, (int) a});
    }
    s.insert(node{n + 1, n + 1, 0});
    for(int i = 1; i <= m; i++){
        int l, r, x, y;
        int 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;
        if(op == 1) add(l, r, x);
        else if(op == 2) assign(l, r, x);
        else if(op == 3) cout << kth(l, r, x) << endl;
        else if(op == 4) cout << query(l, r, x, y) << endl;
    }
}

signed main(){
    solve();
    return 0;
}