珂朵莉最可爱了 珂朵莉树最不可爱了
首先,珂朵莉树 一个十分暴力的算法,仅限于大量的随机数据,否则时间复杂度起飞,所以只要出题人想卡 就很容易GG

珂朵莉

出自《末日时在干什么?有没有空?可以来拯救吗?》的治愈番(万物皆可致郁)
(快去看!出门左转樱x动漫!)
珂朵莉的萌娘百科!


回归正题

到底珂朵莉可爱在哪里珂朵莉树是什么

珂朵莉树

又称 ODT(old driver tree)老司机树
最初出现在 CF896C

用于实现序列操作 包括了一下几种:

  1. 将$[l, r]$区间所有数加上$x$
  2. 将$[l, r]$区间所有数改为$x$
  3. 求出$[l, r]$区间内的第$k$大的数
  4. 求出$[l, r]$区间每个数字的$x$次方的和模$y$的值 即$(\sum ^r_{i=l}a^x_i)\ mod\ y$
    数据随机生成

那么珂朵莉树是如何实现的呢?

把值相同的区间合并成一个结点保存在 set 里面。

显然 这样做如果退化成一个数变成一个区间就裂开了 所以这很需要数据随机(将某一段改为同一个值这种操作)
所以 珂朵莉树可以用来骗分。只要是有区间赋值操作的数据结构题都可以用来骗分。在数据随机的情况下一般效率较高 有可能被精心构造的特殊数据卡到超时。(lxl直呼内行)

储存结构

1
2
3
4
5
6
7
8
struct Node{
int l, r;
mutable LL v;
Node (int L, int R, LL V): l(L), r(R), v(V) {}
bool operator < (const Node &x) const { //这一个为了后续set的insert方便 可以不写 写了这个可以 s.insert(Node(l, r, x))之类的 等价于 s.insert((Node){l, r, x})
return l < x.l;
}
};

assign区间赋值

这是保证珂朵莉树在随机数据下优秀的时间复杂度的根本

1
2
3
4
5
6
void ass_ign(int l, int r, LL x)
{
iter itr = split(r + 1), itl = split(l);
kdl.erase(itl, itr);
kdl.insert(Node(l, r, x));
}

拆开区间
将$[l, r]$区间所有都区间删掉
变成一个插入set

split拆分区间

珂朵莉树如何区间操作呢
把你想操作的区间从整个里面拆出来 然后暴力求解(没错)

1
2
3
4
5
6
7
8
9
10
11
12
13
#define iter set<Node >::iterator //打起来方便  后续不再写入代码
iter split(int pos)
{
iter it = kdl.lower_bound(Node(pos, 0, 0));
if (it != kdl.end() && it->l == pos) return it;
--it;
int L = it->l, R = it->r;
LL V = it->v;
kdl.erase(it);
kdl.insert(Node(L, pos-1, V));
return kdl.insert(Node(pos, R, V)).first;
}

split函数可以将区间从pos位置断开(pos被留在右边的区间) 并返回右边这个区间在set中的迭代器

于是 各种暴力的求解就来了

暴力の第k大

思路:拆出来$[l, r]$区间 排个序(没错)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LL Rank(int l, int r, int k)
{
vector<pair<LL, int> > vp;//临时存放拆出来的节点
iter itr = split(r + 1), itl = split(l);
vp.clear();
for (; itl != itr; ++itl)
vp.push_back(pair<LL, int>(itl->v, itl->r - itl->l + 1));
sort(vp.begin(), vp.end());//暴力+++++
for (vector<pair<LL, int> >::iterator i = vp.begin(); i != vp.end(); ++i)
{
k -= i->second;
if (k <= 0) return i->first;
}
return -1LL;
}

暴力の求和

简单明了 直接拆开for循环

1
2
3
4
5
6
7
8
LL sum(int l, int r, int x, int mod)
{
iter itr = split(r + 1), itl = split(l);
LL ans = 0;
for (; itl != itr; ++itl)
ans = (ans + (LL)(itl->r - itl->l + 1) * pow(itl->v, LL(x), LL(mod)) ) % mod;
return ans;
}

注意:

在不是随机数据的绝大多数情况下
珂朵莉树只能骗到一些分数 很可能被卡
所以扎扎实实去磨线段树(虽然骗分打一打这个还是很香的

完整代码

本题目的完整代码

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
121
122
123
124
125
126
127
#include <bits/stdc++.h>

typedef long long LL;
#define iter set<Node >::iterator

const int MOD7 = 1e9 + 7;
const int MOD9 = 1e9 + 9;
const int MAXN = 1e5 + 7;

using namespace std;

struct Node{
int l, r;
mutable LL v;
Node (int L, int R, LL V): l(L), r(R), v(V) {}
bool operator < (const Node &x) const {
return l < x.l;
}
};

set<Node > kdl;
LL n, m, seed, vmax, a[MAXN];

iter split(int pos)
{
iter it = kdl.lower_bound(Node(pos, 0, 0));
if (it != kdl.end() && it->l == pos) return it;
--it;
int L = it->l, R = it->r;
LL V = it->v;
kdl.erase(it);
kdl.insert(Node(L, pos-1, V));
return kdl.insert(Node(pos, R, V)).first;
}

void add(int l, int r, LL s)
{
iter itr = split(r + 1), itl = split(l);
for (; itl != itr; ++itl) itl->v += s;
}

void ass_ign(int l, int r, LL x)
{
iter itr = split(r + 1), itl = split(l);
kdl.erase(itl, itr);
kdl.insert(Node(l, r, x));
}

LL Rank(int l, int r, int k)
{
vector<pair<LL, int> > vp;
iter itr = split(r + 1), itl = split(l);
vp.clear();
for (; itl != itr; ++itl)
vp.push_back(pair<LL, int>(itl->v, itl->r - itl->l + 1));
sort(vp.begin(), vp.end());
for (vector<pair<LL, int> >::iterator i = vp.begin(); i != vp.end(); ++i)
{
k -= i->second;
if (k <= 0) return i->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 x, int mod)
{
iter itr = split(r + 1), itl = split(l);
LL ans = 0;
for (; itl != itr; ++itl)
ans = (ans + (LL)(itl->r - itl->l + 1) * pow(itl->v, LL(x), LL(mod)) ) % mod;
return ans;
}

LL rnd()
{
LL ret = seed;
seed = (seed * 7 + 13) % MOD7;
return ret;
}

int main()
{
scanf("%d %d %lld %lld", &n, &m, &seed, &vmax);
for (int i=1; i<=n; ++i)
{
a[i] = (rnd() % vmax) + 1;
kdl.insert(Node(i,i,a[i]));
}

//kdl.insert(Node(n+1, n+1, 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)
ass_ign(l, r, LL(x));
else if (op == 3)
printf("%lld\n",Rank(l, r, x));
else
printf("%lld\n",sum(l, r, x, y));
}
return 0;
}

评论