map 的实现非常好写。

· · 题解

题解区咋没有 std::map 的做法。

常规 ODT 都是用 std::set 实现的，然而注意到 std::set 中每个节点的 r 都是其后继节点的 l 减一，故我们可以直接用一个 std::map 维护，key 表示区间左端点，val 表示区间的值。

下面是操作的具体实现。记一个节点的 l 为 key，v 为 val。

split 操作：

即分裂出一个以 l 为左端点的节点。

找到最后一个左端点 \le x 的节点 it，并将其分裂，分裂的话直接在 it 和 \text{next}(it) 之间插入一个节点，其 l 为 x，v 为 v_{it}。

void split(int x) {
    auto it = prev(mp.upper_bound(x));
    mp[x] = it -> second;
}

assign 操作：

即区间赋值。

怎么遍历一个区间呢？只需要先 split 出来，再把中间的节点一个一个访问过去即可。

::::info[note] 在 std::map 实现的 ODT 中，遍历一个区间 [l, r]，需要 split 出一个表示 [l, r] 的节点，即让 l 为左端点的节点的后继变为 r + 1 为左端点的节点，所以需要 split 的是 r + 1 而非 r。

同样的，访问时的终止条件也是 l_it = r + 1，于是为了方便，可以统一让 r \leftarrow r + 1。 ::::

void assign(int l, int r, ll v) {
    r++;
    split(l); split(r);
    auto it = mp.find(l);
    while (it -> first != r) it = mp.erase(it);
    mp[l] = v;
}

perform 操作：

即区间操作，本题中是区间加。

和 assign 操作是类似的。

void perform(int l, int r, ll v) {
    r++;
    split(l); split(r);
    auto it = mp.find(l);
    while (it -> first != r) {
        // Operation
        it -> second += v;
        it = next(it);
    }
}

kth 操作

同上。

ll kth(int l, int r, int k) {
    r++;
    split(l); split(r);
    vector<pair<ll, int>>vec;
    auto it = mp.find(l);
    while (it -> first != r) {
        vec.push_back({it -> second, next(it) -> first - it -> first});
        it = next(it);
    }
    sort(vec.begin(), vec.end());
    for (auto [x, y] : vec) {
        if (k <= y) return x;
       k -= y;
    }
    return -1;
}

query 操作

还是类似的。

ll ask(int l, int r, ll x, ll y) {
    r++;
    split(l); split(r);
    auto it = mp.find(l);
    ll res = 0;
    while (it -> first != r) {
        res = (res + qpow(it -> second % y, x, y) * (next(it) -> first - it -> first) % y) % y;
        it = next(it);
    }
    return res;
}

最终实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 2e5 + 10, MOD = 1e9 + 7;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {
    cout << arg << ' ';
    dbg(args...);
}
namespace Loop1st {
ll qpow(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1, a = a * a % mod) if (b & 1) res = res * a % mod;
    return res;
}
map<int, ll>mp;
struct ODT {
    void split(int x) {
        auto it = prev(mp.upper_bound(x));
        mp[x] = it -> second;
    }
    void assign(int l, int r, ll v) {
        r++;
        split(l); split(r);
        auto it = mp.find(l);
        while (it -> first != r) it = mp.erase(it);
        mp[l] = v;
    }
    void perform(int l, int r, ll v) {
        r++;
        split(l); split(r);
        auto it = mp.find(l);
        while (it -> first != r) {
            // Operation
            it -> second += v;
            it = next(it);
        }
    }
    ll kth(int l, int r, int k) {
        r++;
        split(l); split(r);
        vector<pair<ll, int>>vec;
        auto it = mp.find(l);
        while (it -> first != r) {
            vec.push_back({it -> second, next(it) -> first - it -> first});
            it = next(it);
        }
        sort(vec.begin(), vec.end());
        for (auto [x, y] : vec) {
            if (k <= y) return x;
            k -= y;
        }
        return -1;
    }
    ll ask(int l, int r, ll x, ll y) {
        r++;
        split(l); split(r);
        auto it = mp.find(l);
        ll res = 0;
        while (it -> first != r) {
            res = (res + qpow(it -> second % y, x, y) * (next(it) -> first - it -> first) % y) % y;
            it = next(it);
        }
        return res;
    }
} odt;
ll n, m, seed, vmax, a[N];
ll rnd() {
    ll res = seed;
    seed = (seed * 7 + 13) % MOD;
    return res;
}
void main() {
    cin >> n >> m >> seed >> vmax;
    mp[1] = -1; mp[n + 1] = -1;
    for (int i = 1; i <= n; i++) {
        a[i] = rnd() % vmax + 1;
        mp[i] = a[i];
    }
    for (int i = 1; i <= m; i++) {
        int op = rnd() % 4 + 1, l = rnd() % n + 1, r = rnd() % n + 1;
        if (l > r) swap(l, r);
        ll x = -1, y = -1;
        if (op == 1) {
            x = rnd() % vmax + 1;
            odt.perform(l, r, x);
        } else if (op == 2) {
            x = rnd() % vmax + 1;
            odt.assign(l, r, x);
        } else if (op == 3) {
            x = rnd() % (r - l + 1) + 1;
            cout << odt.kth(l, r, x) << '\n';
        } else {
            x = rnd() % vmax + 1, y = rnd() % vmax + 1;
            cout << odt.ask(l, r, x, y) << '\n';
        }
        // dbg("In case", i, "Query is", op, l, r, x, y);
    }
}

}
int main() {
    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) { Loop1st::main(); }
    return 0;
}