题意
给你一个长为 \(n\) 的序列 \(a_i\) 需要支持四个操作。
- \(1~l~r~x:\) 把 \(i \in [l, r]\) 的 \(a_i\) 加 \(x\) 。
- \(2~l~r~x:\) 把 \(i \in [l, r]\) 的 \(a_i\) 赋值成 \(x\) 。
- \(3~l~r~x:\) 求 \([l, r]\) 区间的第 \(x\) 小元素。
- \(4~l~r~x~y:\) 求 \((\sum_{i = l}^{r} {a_i}^x) \mod y\) 。
一共会操作 \(m\) 次。
保证数据随机（给了你一个随机数据生成器）。
\(1 \le n, m \le 10^5, 1 \le a_i \le 10^9\)
题解
对于这种 数据随机 并且有 区间赋值 的题，常常有一个很牛逼的乱搞算法，叫做 \(\mathrm{ODT(Old~Driver~Tree)}\) ，也有叫 \(\mathrm{Chtholly Tree}\) 的。
至于这个怎么做的呢？其实核心就一条，优化暴力。
如何优化呢？因为有赋值操作，考虑把相邻的数值一样的点合并成一个整的区间就行了。
至于如何实现呢？我们用 std :: set<Node> 维护一段段区间就行了。
Node 内容如下 mutalbe 是为了支持指针修改 ：
struct Node {
int l, r; mutable ll val;
}
inline bool operator < (const Node &lhs, const Node &rhs) {
return lhs.l < rhs.l;
}
修改的时候，我们把 \([l, r]\) 这段区间 \(Split\) 出来，也就是我们把 \(l\) 与 \(l-1\) 分开，\(r\) 与 \(r + 1\) 分开就行了。
具体实现如下：
void Split(int pos) {
auto it = S.lower_bound((Node){pos, 0, 0});
if (it == S.end() || it -> l > pos) {
-- it;
S.emplace(it -> l, pos - 1, it -> val);
S.emplace(pos, it -> r, it -> val);
S.erase(it);
}
} // 将 pos 与 pos - 1 分开。
然后对于操作 \([l, r]\) 区间，只需要暴力遍历指针就行了。（怎么暴力怎么来）
只有区间赋值那里需要搞搞操作，一次可以抹去一连续区间的迭代器。
也就是 S.erase(itl, itr) 会把 [itl, itr) 的所有元素全部删除，复杂度也挺优秀的。（比单个删除快）
然后这样操作后复杂度就变成 \(O(m \log n)\) 的，十分的优秀。
总结
乱搞大法好啊！！\(o)/~
代码
好写好调，真是一个优秀的暴力做法。
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, int> PII;
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("C.in", "r", stdin);
freopen ("C.out", "w", stdout);
#endif
}
const int N = 1e5 + 1e3;
int n, m, seed, v, a[N];
inline int rnd() {
int res = seed;
seed = (seed * 7ll + 13) % 1000000007;
return res;
}
inline int Get(int lim) {
return rnd() % lim + 1;
}
struct Node {
int l, r; mutable ll val;
Node(int l_ = 0, int r_ = 0, ll val_ = 0): l(l_), r(r_), val(val_) {
}
};
inline bool operator < (const Node &lhs, const Node &rhs) {
return lhs.l < rhs.l;
}
multiset<Node> S;
vector<PII> V;
void Split(int pos) {
auto it = S.lower_bound((Node){pos, 0, 0});
if (it == S.end() || it -> l > pos) {
-- it;
S.emplace(it -> l, pos - 1, it -> val);
S.emplace(pos, it -> r, it -> val);
S.erase(it);
}
}
int Mod;
inline int fpm(int x, int power) {
int res = 1;
for (; power; power >>= 1, x = 1ll * x * x % Mod)
if (power & 1) res = 1ll * res * x % Mod;
return res;
}
int main () {
File();
n = read(); m = read(); seed = read(); v = read();
For (i, 1, n) a[i] = Get(v);
for (int i = 1, j = 1; i <= n; i = j) {
while (a[j] == a[i]) ++ j;
S.emplace(i, j - 1, a[i]);
}
For (i, 1, m) {
int opt = Get(4), l = Get(n), r = Get(n), x, y;
if (l > r) swap(l, r);
x = opt == 3 ? Get(r - l + 1) : Get(v);
y = opt == 4 ? Get(v) : 0;
Split(l); if (r < n) Split(r + 1);
auto itl = S.lower_bound((Node) {l, 0, 0}),
itr = S.upper_bound((Node) {r, 0, 0});
if (opt == 1) {
for (auto it = itl; it != itr; ++ it)
it -> val += x;
}
if (opt == 2) {
S.erase(itl, itr);
S.emplace(l, r, x);
}
if (opt == 3) {
V.clear();
for (auto it = itl; it != itr; ++ it)
V.pb(mp(it -> val, it -> r - it -> l + 1));
sort(V.begin(), V.end());
for (auto it : V)
if (x <= it.sec) {
printf ("%lld\n", it.fir); break;
} else x -= it.sec;
}
if (opt == 4) {
int ans = 0; Mod = y;
for (auto it = itl; it != itr; ++ it)
ans = (ans + 1ll * fpm(it -> val % Mod, x) * (it -> r - it -> l + 1)) % Mod;
printf ("%d\n", ans);
}
}
return 0;
}