lessons/参考实现/11-平衡树/CodeForces-896C.cpp

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

using int64 = long long;

struct Node {
    int left;
    mutable int right;
    mutable int64 value;
    bool operator<(const Node &other) const { return left < other.left; }
};

set<Node> intervals;
int array_size;

set<Node>::iterator split(int position) {
    if (position > array_size) return intervals.end();
    auto it = prev(intervals.upper_bound({position, 0, 0}));
    if (it->left == position) return it;
    int right = it->right;
    int64 value = it->value;
    it->right = position - 1;
    return intervals.insert({position, right, value}).first;
}

void add_range(int left, int right, int64 value) {
    auto end = split(right + 1);
    for (auto it = split(left); it != end; ++it) it->value += value;
}

void assign_range(int left, int right, int64 value) {
    auto end = split(right + 1);
    auto begin = split(left);
    intervals.erase(begin, end);
    intervals.insert({left, right, value});
}

int64 kth(int left, int right, int rank) {
    auto end = split(right + 1);
    vector<pair<int64, int>> values;
    for (auto it = split(left); it != end; ++it) {
        values.push_back({it->value, it->right - it->left + 1});
    }
    sort(values.begin(), values.end());
    for (auto [value, count] : values) {
        if (rank <= count) return value;
        rank -= count;
    }
    return -1;
}

int64 mod_power(int64 base, int64 exponent, int64 modulus) {
    int64 result = 1 % modulus;
    base %= modulus;
    while (exponent > 0) {
        if (exponent & 1) result = result * base % modulus;
        base = base * base % modulus;
        exponent >>= 1;
    }
    return result;
}

int64 power_sum(int left, int right, int64 exponent, int64 modulus) {
    auto end = split(right + 1);
    int64 result = 0;
    for (auto it = split(left); it != end; ++it) {
        int64 count = it->right - it->left + 1;
        result = (result + count % modulus * mod_power(it->value, exponent, modulus)) % modulus;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int operations;
    int64 seed, maximum;
    cin >> array_size >> operations >> seed >> maximum;
    auto random_value = [&]() {
        int64 result = seed;
        seed = (seed * 7 + 13) % 1'000'000'007LL;
        return result;
    };
    for (int i = 1; i <= array_size; ++i) {
        intervals.insert({i, i, random_value() % maximum + 1});
    }
    while (operations--) {
        int type = random_value() % 4 + 1;
        int left = random_value() % array_size + 1;
        int right = random_value() % array_size + 1;
        if (left > right) swap(left, right);
        int64 x;
        if (type == 3) x = random_value() % (right - left + 1) + 1;
        else x = random_value() % maximum + 1;
        if (type == 1) add_range(left, right, x);
        else if (type == 2) assign_range(left, right, x);
        else if (type == 3) cout << kth(left, right, static_cast<int>(x)) << '\n';
        else {
            int64 modulus = random_value() % maximum + 1;
            cout << power_sum(left, right, x, modulus) << '\n';
        }
    }
    return 0;
}