题目大意:有$n$个数,有$m$次$4$种操作:
- 1 l r x :将$[l,r]$区间所有数加上$x$
- 2 l r x :将$[l,r]$区间所有数变成$x$
- 3 l r k :输出$[l,r]$区间第$k$大
- 4 l r x p :输出$\sum\limits_{i=l}^rs_i^x\pm
$n,m\leqslant10^5$
题解:珂朵莉树模板题
卡点:$split$中写错,写成 it==s.end()
C++ Code:
#include <cstdio> #include <algorithm> #include <iostream> #include <set> #include <vector> #define mul(a, b) (static_cast<long long> (a) * (b) % mod) #define _mul(a, b) (a = static_cast<long long> (a) * (b) % mod) inline int pw(int base, int p, int mod) { static int res; for (res = 1; p; p >>= 1, _mul(base, base)) if (p & 1) _mul(res, base); return res; } int n, m, seed, vmax; int rnd() { static const int mod = 1e9 + 7; static int t; t = seed; seed = (7ll * seed + 13) % mod; return t; } namespace ODT { struct node { int l, r; mutable long long v; inline bool operator < (const node &rhs) const { return l < rhs.l; } } ; typedef std::set<node>::iterator SIT; typedef std::pair<long long, int> PLI; std::set<node> s; SIT split(int pos) { SIT it = s.lower_bound((node) { pos, 0, 0 }); if (it != s.end() && it -> l == pos) return it; --it; const int l = it -> l, r = it -> r; const long long v = it -> v; s.erase(it), s.insert((node) { l, pos - 1, v }); return s.insert((node) { pos, r, v }).first; } void assign(int l, int r, int v) { SIT R = split(r + 1), L = split(l); s.erase(L, R), s.insert((node) { l, r, v }); } void add(int l, int r, int v) { SIT R = split(r + 1), L = split(l); for (SIT it = L; it != R; ++it) it -> v += v; } long long rnk(int l, int r, int k) { static std::vector<PLI> v; v.clear(); SIT R = split(r + 1), L = split(l); for (SIT it = L; it != R; ++it) v.push_back(std::make_pair(it -> v, it -> r - it -> l + 1)); std::sort(v.begin(), v.end()); for (PLI i : v) { k -= i.second; if (k <= 0) return i.first; } } int query(int l, int r, int x, int mod) { SIT R = split(r + 1), L = split(l); int ans = 0; for (SIT it = L; it != R; ++it) ans = (ans + mul(pw(it -> v % mod, x, mod), it -> r - it -> l + 1)) % mod; return ans; } } int main() { std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0); std::cin >> n >> m >> seed >> vmax; for (int i = 1, x; i <= n; ++i) { x = (rnd() % vmax) + 1; ODT::s.insert((ODT::node) { i, i, x }); } while (m --> 0) { static int op, l, r, x, y; op = (rnd() % 4) + 1; l = (rnd() % n) + 1; r = (rnd() % n) + 1; if (l > r) std::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: ODT::add(l, r, x); break; case 2: ODT::assign(l, r, x); break; case 3: std::cout << ODT::rnk(l, r, x) << '\n'; break; case 4: std::cout << ODT::query(l, r, x, y) << '\n'; } } return 0; }