珂朵莉树
这个名字我猜是来源于初次诞生这个算法的题目->Willem, Chtholly and Seniorious
算法
适用于数据随机， 并且有区间推平操作， 也就是区间赋值操作， 就可以用set维护， 达到优秀的 \(O(nlogn)\) 时间复杂度。
定义
struct Node{
int l, r;
mutable int v;
Node(int l, int r = 0, int v = 0) : l(l), r(r), v(v) {}
bool operator < (const Node &x) const {
return l < x.l;
}
};
set<Node> odt;
每个节点代表一个区间
split操作
就是把 \(x\) 所在区间分裂成 \([l, x - 1]\) 和 \([x, r]\)。
auto split(int x) {
auto it = odt.lower_bound(Node(x));
if (it != odt.end() && it->l == x) return it;
--it;
if (it->r < x) return odt.end();
int l = it->l, r = it->r, v = it->v;
odt.erase(it);
odt.insert(Node(l, x - 1, v));
return odt.insert(Node(x, r, v)).first;
}
assign操作
就是把 \([l, r]\) 区间重构了， 需要先把 \(l\) 和 \(r + 1\) split一下， 才能刚好提出 \([l, r]\) 这个区间， 然后暴力把这之间的全部推平。
void assign(int l, int r, int v) {
auto itr = split(r + 1), itl = split(l);
odt.erase(itl, itr);
odt.insert(Node(l, r, v));
}
例题
Willem, Chtholly and Seniorious
其他各种操作都直接暴力搞， 时间复杂度在数据随机的时候都很优秀。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
struct Node{
int l, r;
mutable int v;
Node(int l, int r = 0, int v = 0) : l(l), r(r), v(v) {}
bool operator < (const Node &x) const {
return l < x.l;
}
};
set<Node> odt;
int n, m, seed, vmax, a[N];
auto split(int x) {
auto it = odt.lower_bound(Node(x));
if (it != odt.end() && it->l == x) return it;
--it;
if (it->r < x) return odt.end();
int l = it->l, r = it->r, v = it->v;
odt.erase(it);
odt.insert(Node(l, x - 1, v));
return odt.insert(Node(x, r, v)).first;
}
void assign(int l, int r, int v) {
auto itr = split(r + 1), itl = split(l);
odt.erase(itl, itr);
odt.insert(Node(l, r, v));
}
void add(int l, int r, int v) {
auto itr = split(r + 1), itl = split(l);
for (auto it = itl; it != itr; ++it)
it->v += v;
}
struct Rk{
int val, cnt;
bool operator < (const Rk &x) const { return val < x.val; }
Rk(int val, int cnt) : val(val), cnt(cnt) { }
};
int rk(int l, int r, int k) {
auto itr = split(r + 1), itl = split(l);
vector<Rk> q;
for (auto it = itl; it != itr; ++it)
q.push_back(Rk(it->v, it->r - it->l + 1));
sort(q.begin(), q.end());
for (auto i : q) {
if (i.cnt < k) k -= i.cnt;
else return i.val;
}
}
int qpow(int a, int b, int p) {
int res = 1;
a %= p;
for ( ; b; b >>= 1, a = a * a % p) if (b & 1) res = res * a % p;
return res;
}
int calP(int l, int r, int x, int y) {
auto itr = split(r + 1), itl = split(l);
int res = 0;
for (auto it = itl; it != itr; it++)
(res += qpow(it->v, x, y) * (it->r - it->l + 1) % y) %= y;
return res;
}
int rnd() {
int ret = seed;
seed = (seed * 7 + 13) % mod;
return ret;
}
signed main() {
cin >> n >> m >> seed >> vmax;
for (int i = 1; i <= n; ++i) {
a[i] = (rnd() % vmax) + 1;
odt.insert(Node(i, i, a[i]));
}
for (int i = 1; i <= m; ++i) {
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 << rk(l, r, x) << endl;
} else {
cout << calP(l, r, x, y) << endl;
}
}
return 0;
}