1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
| #include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; typedef long long LL; typedef pair<LL, int> PLI; template <class Type> void read(Type &x) { char c; bool flag = false; while ((c = getchar()) < '0' || c > '9') c == '-' && (flag = true); x = c - '0'; while ((c = getchar()) >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0'; flag && (x = ~x + 1); } template <class Type> void write(Type x) { x < 0 && (putchar('-'), x = ~x + 1); x > 9 && (write(x / 10), 0); putchar(x % 10 + '0'); } const int N = 1e5 + 10, mod = 1e9 + 7; struct Node { int l, r; mutable LL v; bool operator<(const Node &_) const { return l < _.l; } }; typedef set<Node>::iterator SI; set<Node> tr; int n, m, w[N], seed, vmax; int get() { int res = seed; seed = ((LL)seed * 7 + 13) % mod; return res; } int binpow(int b, int k, int p) { int res = 1; while (k) { if (k & 1) res = (LL)res * b % p; b = (LL)b * b % p; k >>= 1; } return res; } SI split(int x) { SI cur = tr.lower_bound((Node){x}); if (cur != tr.end() && cur->l == x) return cur; Node t = *(--cur); tr.erase(cur); tr.insert((Node){t.l, x - 1, t.v}); return tr.insert((Node){x, t.r, t.v}).first; } LL kth(int l, int r, int k) { vector<PLI> p; for (SI R = split(r + 1), L = split(l); L != R; L++) p.push_back(make_pair(L->v, L->r - L->l + 1)); sort(p.begin(), p.end()); for (PLI i : p) { k -= i.second; if (k <= 0) return i.first; } } int main() { read(n), read(m), read(seed), read(vmax); for (int i = 1; i <= n; i++) { w[i] = get() % vmax + 1; tr.insert((Node){i, i, w[i]}); } tr.insert((Node){n + 1, n + 1, 0}); while (m--) { int op = get() % 4 + 1, l = get() % n + 1, r = get() % n + 1; l > r && (swap(l, r), 0); if (op == 1) { int x = get() % vmax + 1; for (SI R = split(r + 1), L = split(l); L != R; L++) L->v += x; } else if (op == 2) { int x = get() % vmax + 1; tr.erase(split(l), split(r + 1)); tr.insert((Node){l, r, x}); } else if (op == 3) { int x = get() % (r - l + 1) + 1; write(kth(l, r, x)), puts(""); } else if (op == 4) { int x = get() % vmax + 1, y = get() % vmax + 1; int res = 0; for (SI R = split(r + 1), L = split(l); L != R; L++) (res += (LL)binpow(L->v % y, x, y) * (L->r - L->l + 1) % y) %= y; write(res), puts(""); } } return 0; }
|