|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
#define int long long // 太多的long long,太讨厌了，我喜欢重定义成int
|
|
|
|
|
|
const int MOD = 1000000007;
|
|
|
const int N = 100010;
|
|
|
typedef pair<int, int> PII;
|
|
|
|
|
|
int n, m; // n 片护符,m 次操作
|
|
|
int seed, vmax; // 后两个变量用于生成随机数据,生成办法给了一段伪代码
|
|
|
|
|
|
// 柯朵莉树模板
|
|
|
struct Node {
|
|
|
int l, r; // l和r表示这一段的起点和终点
|
|
|
mutable int v; // v表示这一段上所有元素相同的值是多少,注意关键字 mutable,使得set中结构体属性可修改
|
|
|
bool operator<(const Node &b) const {
|
|
|
return l < b.l; // 规定按照每段的左端点排序
|
|
|
}
|
|
|
};
|
|
|
set<Node> s; // 柯朵莉树的区间集合
|
|
|
|
|
|
// 分裂:[l,x-1],[x,r]
|
|
|
set<Node>::iterator split(int x) {
|
|
|
auto it = s.lower_bound({x});
|
|
|
if (it != s.end() && it->l == x) return it; // 一击命中
|
|
|
it--; // 没有找到就减1个继续找
|
|
|
if (it->r < x) return s.end(); // 真的没找到,返回s.end()
|
|
|
|
|
|
int l = it->l, r = it->r, v = it->v; // 没有被返回，说明找到了,记录下来，防止后面删除时被破坏
|
|
|
s.erase(it); // 删除整个区间
|
|
|
s.insert({l, x - 1, v}); //[l,x-1]拆分
|
|
|
// insert函数返回pair，其中的first是新插入结点的迭代器
|
|
|
return s.insert({x, r, v}).first; //[x,r]拆分
|
|
|
}
|
|
|
|
|
|
// 区间加
|
|
|
void add(int l, int r, int v) {
|
|
|
// 必须先计算itr,后计算itl
|
|
|
auto R = split(r + 1), L = split(l);
|
|
|
for (auto it = L; it != R; it++) it->v += v;
|
|
|
}
|
|
|
// 区间赋值
|
|
|
void assign(int l, int r, int v) {
|
|
|
auto R = split(r + 1), L = split(l);
|
|
|
s.erase(L, R); // 删除旧区间
|
|
|
s.insert({l, r, v}); // 增加新区间
|
|
|
}
|
|
|
|
|
|
// 排名第x位的数值
|
|
|
int rnk(int l, int r, int x) {
|
|
|
vector<PII> v;
|
|
|
auto R = split(r + 1), L = split(l);
|
|
|
for (auto it = L; it != R; it++)
|
|
|
v.push_back({it->v, it->r - it->l + 1}); // 值，个数
|
|
|
sort(v.begin(), v.end()); // 默认按PII的第一维，也就是值由小到大排序
|
|
|
|
|
|
// 暴力拼接出排名第x大数的数值是多少
|
|
|
for (auto c : v)
|
|
|
if (c.second < x)
|
|
|
x -= c.second;
|
|
|
else
|
|
|
return c.first;
|
|
|
}
|
|
|
|
|
|
// 快速幂 (x^y)%p
|
|
|
// #define int long long
|
|
|
int qmi(int x, int y, int p) {
|
|
|
int res = 1;
|
|
|
x %= p;
|
|
|
while (y) {
|
|
|
if (y & 1) res = res * x % p;
|
|
|
y >>= 1;
|
|
|
x = x * x % p;
|
|
|
}
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
//[l,r]之间，每个值的x次方，求和，对y取模
|
|
|
int calc(int l, int r, int x, int y) {
|
|
|
auto R = split(r + 1), L = split(l);
|
|
|
int res = 0;
|
|
|
for (auto it = L; it != R; it++)
|
|
|
// it枚举的是每个区间段，每个区间段内的值是一样的：it->v
|
|
|
// 区间段的长度 = it->r - it->l + 1
|
|
|
// 总和 = SUM(区间段的值 * 区间段的长度)
|
|
|
// 注意一步一取模
|
|
|
res = (res + qmi(it->v, x, y) * (it->r - it->l + 1) % y) % y;
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
// 用C++翻译伪代码
|
|
|
int rnd() {
|
|
|
int ret = seed;
|
|
|
seed = (seed * 7 + 13) % MOD;
|
|
|
return ret;
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
参考答案：
|
|
|
2
|
|
|
1
|
|
|
0
|
|
|
3
|
|
|
*/
|
|
|
signed main() {
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("CF896C.in", "r", stdin);
|
|
|
#endif
|
|
|
// 加快读入
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
|
|
|
cin >> n >> m >> seed >> vmax;
|
|
|
for (int i = 1; i <= n; i++) { // n 片护符
|
|
|
int ai = (rnd() % vmax) + 1; // 每个护符上有一个数字 a[i]
|
|
|
s.insert({i, i, ai}); // 一个格子一个数，从i~i,值为a[i]，这是在初始化构建柯朵莉树啊
|
|
|
}
|
|
|
|
|
|
for (int i = 1; i <= m; i++) { // m 个操作
|
|
|
int op, l, r, x, y;
|
|
|
op = (rnd() % 4) + 1;
|
|
|
l = (rnd() % n) + 1;
|
|
|
r = (rnd() % n) + 1;
|
|
|
|
|
|
if (l > r) swap(l, r);
|
|
|
|
|
|
if (op == 3)
|
|
|
x = (rnd() % (r - l + 1)) + 1;
|
|
|
else
|
|
|
x = (rnd() % vmax) + 1;
|
|
|
|
|
|
if (op == 4)
|
|
|
y = (rnd() % vmax) + 1;
|
|
|
// 上面的都是翻译伪代码
|
|
|
|
|
|
// 真正的处理开始了
|
|
|
if (op == 1)
|
|
|
add(l, r, x); // 区间全部加
|
|
|
else if (op == 2)
|
|
|
assign(l, r, x); // 区间全部改
|
|
|
else if (op == 3)
|
|
|
cout << rnk(l, r, x) << endl; // 查询第x大数
|
|
|
else
|
|
|
cout << calc(l, r, x, y) << endl; // 查询区间 [l,r] 上的数的 x 次方之和对 y 取模的值
|
|
|
}
|
|
|
return 0;
|
|
|
} |
