• 如果您觉得本站非常有看点，那么赶紧使用Ctrl+D 收藏吧

# 算法学习笔记: 珂朵莉树

3个月前 (08-04) 50次浏览

• 区间加
• 区间赋值
• 求区间第k大值
• 求区间n次方和

(CF896C Willem, Chtholly and Seniorious)

After over 500 years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.
Seniorious has n pieces of talisman. Willem puts them in a line, the i-th of which is an integer ai.
In order to maintain it, Willem needs to perform m operations.
There are four types of operations:

1 l r x: For each i such that l ≤ i ≤ r, assign ai + x to ai.
2 l r x: For each i such that l ≤ i ≤ r, assign x to ai.
3 l r x: Print the x-th smallest number in the index range [l, r], i.e. the element at the x-th position if all the elements ai such that l ≤ i ≤ r are taken and sorted into an array of non-decreasing integers. It’s guaranteed that 1 ≤ x ≤ r - l + 1.
4 l r x y: Print the sum of the x-th power of ai such that l ≤ i ≤ r, modulo y, i.e. .

Input
The only line contains four integers n, m, seed, vmax (1 ≤ n, m ≤ 105, 0 ≤ seed < 109 + 7, 1 ≤ vmax ≤ 109).
The initial values and operations are generated using following pseudo code:

def rnd():

ret = seed
seed = (seed * 7 + 13) mod 1000000007
return ret

for i = 1 to n:

a[i] = (rnd() mod vmax) + 1

for i = 1 to m:

op = (rnd() mod 4) + 1
l = (rnd() mod n) + 1
r = (rnd() mod n) + 1

if (l > r):
swap(l, r)

if (op == 3):
x = (rnd() mod (r – l + 1)) + 1
else:
x = (rnd() mod vmax) + 1

if (op == 4):
y = (rnd() mod vmax) + 1

Here op is the type of the operation mentioned in the legend.
Output
For each operation of types 3 or 4, output a line containing the answer.

``````struct node
{
ll l, r;
mutable ll v; // 这里mutable要写不然可能会CE
node(ll l, ll r, ll v) : l(l), r(r), v(v) {} // 构造函数
bool operator<(const node &o) const { return l < o.l; } // 重载小于运算符
};
``````

``````set<node> tree;
``````

``````auto split(ll pos)
// 若不支持C++14，auto须改为set<node>::iterator
{
auto it = tree.lower_bound(node(pos, 0, 0)); // 寻找左端点大于等于pos的第一个节点
// 若不支持C++11，auto须改为set<node>::iterator
if (it != tree.end() && it->l == pos) // 如果已经存在以pos为左端点的节点，直接返回
return it;
it--; // 否则往前数一个节点
ll l = it->l, r = it->r, v = it->v;
tree.erase(it); // 删除该节点
tree.insert(node(l, pos - 1, v)); // 插入<l,pos-1,v>和<pos,r,v>
return tree.insert(node(pos, r, v)).first; // 返回以pos开头的那个节点的迭代器
// insert默认返回值是一个pair，第一个成员是我们要的
}
``````

``````void assign(ll l, ll r, ll v)
{
auto end = split(r + 1), begin = split(l); // 顺序不能颠倒，否则可能RE
tree.erase(begin, end); // 清除一系列节点
tree.insert(node(l, r, v)); // 插入新的节点
}
``````

CF915E Physical Education Lessons 洛谷@小粉兔译）

Alex高中毕业了，他现在是大学新生。虽然他学习编程，但他还是要上体育课，这对他来说完全是一个意外。快要期末了，但是不幸的Alex的体育学分还是零蛋！
Alex可不希望被开除，他想知道到期末还有多少天的工作日，这样他就能在这些日子里修体育学分。但是在这里计算工作日可不是件容易的事情：

``````int sum;
void assign(int l, int r, int v)
{
int tot = 0, len = 0;
auto end = split(r + 1), it = split(l), begin = it;
for (it; it != end; it++)
{
len += (it->r - it->l + 1);
tot += it->v * (it->r - it->l + 1);
}
tree.erase(begin, end);
tree.insert(node(l, r, v));
if (v == 1)
sum += (len - tot);
else
sum -= tot;
}
int main()
{
tree.insert(node(1, n, 1));
sum = n;
while (q--)
{
assign(l, r, k == 1 ? 0 : 1);
printf("%dn", sum);
}
return 0;
}
``````

``````void add(ll l, ll r, ll v)
{
auto end = split(r + 1);
for (auto it = split(l); it != end; it++)
it->v += v;
}
``````

``````ll kth(ll l, ll r, ll k)
{
auto end = split(r + 1);
vector<pair<ll, ll>> v; // 这个pair里存节点的值和区间长度
for (auto it = split(l); it != end; it++)
v.push_back(make_pair(it->v, it->r - it->l + 1));
sort(v.begin(), v.end()); // 直接按节点的值的大小排下序
for (int i = 0; i < v.size(); i++) // 然后挨个丢出来，直到丢出k个元素为止
{
k -= v[i].second;
if (k <= 0)
return v[i].first;
}
}
``````

``````ll sum_of_pow(ll l, ll r, ll x, ll y)
{
ll tot = 0;
auto end = split(r + 1);
for (auto it = split(l); it != end; it++)
tot = (tot + qpow(it->v, x, y) * (it->r - it->l + 1)) % y; // qpow自己写一下
}
``````

（更新）但是……事实上，还有一种暴力+暴力法。就是，先把数据离线下来，然后，根据输入数据的特点（比如有多少次大范围的赋值），选择直接暴力或使用珂朵莉树。因为，如果一个数据具有卡珂朵莉树的特点，那么它肯定大范围赋值较少，那么暴力的复杂度也许就可以接受。

CF896C的完整代码如下（题目专门给了一个随机数生成器就是防hack…）：

``````#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
{
ll ans = 0;
char c = getchar();
while (!isdigit(c))
c = getchar();
while (isdigit(c))
{
ans = ans * 10 + c - '0';
c = getchar();
}
return ans;
}
struct node
{
ll l, r;
mutable ll v;
node(ll l, ll r, ll v) : l(l), r(r), v(v) {}
bool operator<(const node &o) const { return l < o.l; }
};
set<node> tree;
auto split(ll pos)
{
auto it = tree.lower_bound(node(pos, 0, 0));
if (it != tree.end() && it->l == pos)
return it;
it--;
ll l = it->l, r = it->r, v = it->v;
tree.erase(it);
tree.insert(node(l, pos - 1, v));
return tree.insert(node(pos, r, v)).first;
}
void assign(ll l, ll r, ll v)
{
auto end = split(r + 1), begin = split(l);
tree.erase(begin, end);
tree.insert(node(l, r, v));
}
ll qpow(ll a, ll n, ll p)
{
ll ans = 1;
a %= p;
while (n)
{
if (n & 1)
ans = ans * a % p;
n >>= 1;
a = a * a % p;
}
return ans;
}
ll n, m, seed, vmax;
ll rnd()
{
ll ret = seed;
seed = (seed * 7 + 13) % 1000000007;
return ret;
}
void add(ll l, ll r, ll v)
{
auto end = split(r + 1);
for (auto it = split(l); it != end; it++)
it->v += v;
}
ll kth(ll l, ll r, ll k)
{
auto end = split(r + 1);
vector<pair<ll, ll>> v;
for (auto it = split(l); it != end; it++)
v.push_back(make_pair(it->v, it->r - it->l + 1));
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++)
{
k -= v[i].second;
if (k <= 0)
return v[i].first;
}
}
ll sum_of_pow(ll l, ll r, ll x, ll y)
{
ll tot = 0;
auto end = split(r + 1);
for (auto it = split(l); it != end; it++)
tot = (tot + qpow(it->v, x, y) * (it->r - it->l + 1)) % y;
}
int main()
{
for (int i = 1; i <= n; ++i)
{
int r = rnd();
tree.insert(node(i, i, r % vmax + 1));
}
for (int i = 1; i <= m; ++i)
{
ll opr = rnd() % 4 + 1, l = rnd() % n + 1, r = rnd() % n + 1, x, y;
if (l > r)
swap(l, r);
if (opr == 3)
x = rnd() % (r - l + 1) + 1;
else
x = rnd() % vmax + 1;
if (opr == 4)
y = rnd() % vmax + 1;
switch (opr)
{
case 1:
break;
case 2:
assign(l, r, x);
break;
case 3:
printf("%lldn", kth(l, r, x));
break;
case 4:
printf("%lldn", sum_of_pow(l, r, x, y));
}
}
return 0;
}
``````