@[咸鱼吖](/user/428690) 在印象里洛谷换行符不是 `\n`
by qwq___qaq @ 2022-01-09 14:49:05
@[_sto_pengzijun_orz_](/user/556362) 谁说不是的
by stOtue @ 2022-01-09 20:29:29
### CF896C:在 八中OJ 98分的代码
```cpp
#include <cstdio>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define set_iter set<node> :: iterator
using namespace std;
typedef long long ll;
struct node {
int l, r;
mutable int v;
node(int L, int R = -1, ll V = 0) : l(L), r(R), v(V) {}
bool operator < (const node& o) const {
return l < o.l;
}
};
set<node> s;
set_iter split(int pos) {
set_iter it = s.lower_bound(node(pos));
if (it != s.end() && it -> l == pos)
return it;
--it;
int L = it -> l, R = it -> r;
ll val = it -> v;
s.erase(it);
s.insert(node(L, pos-1, val));
return s.insert(node(pos, R, val)).first;
}
void assign(int l, int r, int val = 0) {
set_iter itr = split(r + 1), itl = split(l);
s.erase(itl, itr);
s.insert(node(l, r, val));
}
void add(int l, int r, ll val = 1) {
set_iter itr = split(r + 1), itl = split(l);
for (; itl != itr; ++itl)
itl -> v += val;
}
ll rk(int l, int r, int k) {
vector<pair<ll, int> > t;
set_iter itr = split(r + 1), itl = split(l);
t.clear();
for (; itl != itr; ++itl)
t.push_back(pair<ll, int>(itl -> v, itl -> r - itl -> l + 1));
sort(t.begin(), t.end());
for (vector<pair<ll,int> > :: iterator it = t.begin();it != t.end(); ++it) {
k -= it -> second;
if (k <= 0) return it -> first;
}
return -1LL;
}
ll pow(ll a, ll b, ll mod) {
ll res = 1;
ll ans = a % mod;
while (b) {
if (b & 1) res = res * ans % mod;
ans = ans * ans % mod;
b >>= 1;
}
return res;
}
ll sum(int l, int r, int ex, int mod) {
set_iter itl = split(l), itr = split(r + 1);
ll res = 0;
for (; itl != itr; ++itl)
res = (res + (ll)(itl -> r - itl -> l + 1) * pow(itl -> v, ll(ex), ll(mod))) % mod;
return res;
}
int n, m;
ll seed, vmax;
ll rnd() {
ll ret = seed;
seed = (seed * 7 + 13) % 1000000007;
return ret;
}
ll a[10005];
int main() {
scanf("%d %d %lld %lld", &n, &m, &seed, &vmax);
for (int i = 1; i <= n; i++) {
a[i] = (rnd() % vmax) + 1;
s.insert(node(i, i, a[i]));
}
s.insert(node(n + 1, n + 1, 0));
int lines = 0;
for (int i = 1; i <= m; i++) {
int op = int(rnd() % 4) + 1;
int l = int(rnd() % n) + 1;
int r = int(rnd() % n) + 1;
if (l > r) swap(l,r);
int x, y;
if (op == 3)
x = int(rnd() % (r - l + 1)) + 1;
else
x = int(rnd() % vmax) +1;
if (op == 4)
y = int(rnd() % vmax) + 1;
if (op == 1)
add(l, r, ll(x));
else if (op == 2)
assign(l, r, ll(x));
else if (op == 3)
printf("%lld\n", rk(l, r, x));
else
printf("%lld\n", sum(l, r, x, y));
}
return 0;
}
```
by zhou_ziyi @ 2022-01-10 14:05:57