珂朵莉树-ODT

原文链接

珂朵莉树 : Old Driver Tree.

ODT 是一种基于随机数据的暴力数据结构

主要是应用于维护区间信息。 通过不断地分裂与合并,可证明其均摊复杂度是$log$的

可以解决区间赋值,区间查询等问题。 当然前提是数据随机。

题目

cf896C

操作:

  1. 区间赋值
  2. 区间加
  3. 区间第k大
  4. 区间幂和。
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
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int a[maxn];
int n, m, seed, vmax;
ll Pow(ll a, ll b, int p) {
ll ret = 1;
a %= p; // !!!
while (b) {
if (b & 1) ret = ret * a % p;
a = a * a % p;
b >>= 1;
}
return ret;
}
inline int rnd() {
ll ret = seed;
seed = ((seed * 7LL) + 13) % mod;
return ret;
}
struct Node {
int l, r;
mutable ll val;
Node(int l = 0, int r = 0, ll val = 0) : l(l), r(r), val(val) {}
bool operator<(const Node& A) const { return l < A.l; }
};
set<Node> odt;

set<Node>::iterator split(int pos) {
auto it = odt.lower_bound(Node(pos));
if (it != odt.end() && it->l == pos) return it;
--it;
int L = it->l, R = it->r;
ll v = it->val;
odt.erase(it);
odt.insert(Node(L, pos - 1, v));
return odt.insert(Node(pos, R, v)).first;
}

void assign(int l, int r, int val) {
auto itl = split(l), itr = split(r + 1);
odt.erase(itl, itr);
odt.insert(Node(l, r, val));
}

void add(int l, int r, int val) {
auto itl = split(l), itr = split(r + 1);
for (; itl != itr; itl++) itl->val += val;
}
ll Rank(int l, int r, int k) {
vector<pair<ll, int>> vp;
auto itl = split(l), itr = split(r + 1);
vp.clear();
for (; itl != itr; itl++) vp.push_back(mp(itl->val, itl->r - itl->l + 1));
sort(vp.begin(), vp.end());
for (auto& it : vp) {
k -= it.second;
if (k <= 0) return it.first;
}
}
ll sum(int l, int r, int x, int p) {
auto itl = split(l), itr = split(r + 1);
ll ret = 0;
for (; itl != itr; itl++)
ret = (ret + 1LL * (itl->r - itl->l + 1) * Pow(itl->val, x, p) % p) % p;
return ret;
}

int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
scanf("%d%d%d%d", &n, &m, &seed, &vmax);
for (int i = 1; i <= n; i++) {
a[i] = (rnd() % vmax) + 1;
odt.insert(Node(i, i, a[i]));
}
odt.insert(Node(n + 1, n + 1, 0));
for (int i = 1, op, l, r, x, y; i <= m; i++) {
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)
printf("%lld\n", Rank(l, r, x));
else
printf("%lld\n", sum(l, r, x, y));
}
}
Thank you for your support!