核心思想
想法的本质是基于数据随机的均摊,不是数据结构
把值相同的区间合并成一个节点保存在$set$中
结点
struct Node
{
int l, r;
mutable int v;
Node(int a = 0, b = 0, c = 0)
{
l = a, r = b, v = c;
}
frined bool operator<(Node a, Node b)
{
return a.l < b.l;
}
};
珂朵莉树的初始化
std::set<Node> S;
珂朵莉树的核心操作
$split$
using S_IT = std::set<Node>::iterator;
S_IT split(int pos)
{
S_IT it = S.lower_bound(Node(pos, 0, 0)); // 在set中查到左端点位置大于等于pos的结点
if (it != S.end() && it->l == pos) // 如果这个结点的左端点恰好是pos,无需分裂直接返回
return it;
// 如果不是pos就一定大于pos,则包含pos的结点是上一个结点
--it;
ll l = it->l, r = it->r, c = it->c;
S.erase(it);
S.insert(Node(l, pos - 1, c));
return S.insert((Node(pos, r, c))).first;
}
$split$操作将包含$pos$的区间$[l,r]$分裂成$[l,pos-1]$和$[pos,r]$,并返回后者的迭代器
有了$split$,任何对于$[l,r]$的区间操作
都能转换成$set$上$[split(l),split(r+1))$的操作
$assign$
using S_IT = std::set<Node>::iterator;
void assign(int l, int r, int c)
{
S_IT it2 = split(r + 1), it1 = split(l);
// 如果要顺便遍历区间里的信息做某些操作
for (auto it = it1; it != it2; ++it)
{
// 做操作
}
S.erase(it1, it2);
S.insert(Node(l, r, c));
}
$assign$用于区间赋值,同时减少$set$中结点个数
注意要先$split(r+1)$,否则可能$RE$
例题:$CF896C$
题目大意
长度为$n$的数列$a$
维护四种操作
$1\ l\ r\ x:$对于$l\leq i\leq r$置$a_i$为$a_i+x$
$2\ l\ r\ x:$对于$l\leq i\leq r$置$a_i$为$x$
$3\ l\ r\ x:$输出$a_l,a_{l+1},\cdots,a_r$这段区间里第$x$小的数
$4\ l\ r\ x\ y:$输出$(\sum_{i=l}^{r}(a_i)^x)\mod y$
解题思路
按照模板每一种操作都很容易实现
具体代码
#include <bits/stdc++.h>
using ll = long long;
using PLL = std::pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 10;
ll n, m, seed, vmax;
ll a[N];
ll rnd()
{
ll res = seed;
seed = (seed * 7 + 13) % MOD;
return res;
}
struct Node
{
ll l, r;
mutable ll v;
Node(ll a = 0, ll b = 0, ll c = 0)
{
l = a, r = b, v = c;
};
friend bool operator<(Node a, Node b)
{
return a.l < b.l;
};
};
std::set<Node> ODT;
using S_IT = std::set<Node>::iterator;
S_IT split(ll pos)
{
auto it = ODT.lower_bound(Node(pos, 0, 0));
if (it != ODT.end() && it->l == pos)
return it;
--it;
ll l = it->l, r = it->r, v = it->v;
ODT.erase(it);
ODT.insert(Node(l, pos - 1, v));
return ODT.insert(Node(pos, r, v)).first;
}
void addx(ll l, ll r, ll x)
{
auto rit = split(r + 1), lit = split(l);
for (auto it = lit; it != rit; ++it)
it->v += x;
}
void modify(ll l, ll r, ll x)
{
auto rit = split(r + 1), lit = split(l);
ODT.erase(lit, rit);
ODT.insert(Node(l, r, x));
}
ll x_th(ll l, ll r, ll x)
{
auto rit = split(r + 1), lit = split(l);
std::vector<PLL> t;
for (auto it = lit; it != rit; ++it)
t.push_back(PLL(it->v, it->r - it->l + 1));
std::sort(t.begin(), t.end());
for (ll i = 0; i < t.size(); ++i)
if (x > t[i].second)
x -= t[i].second;
else
return t[i].first;
}
ll qpow(ll a, ll b, ll p)
{
ll res = 1 % p;
a %= p;
for (; b; b >>= 1)
{
if (b & 1)
res = (res * a) % p;
a = (a * a) % p;
}
return res;
}
ll pow_sum(ll l, ll r, ll x, ll y)
{
auto rit = split(r + 1), lit = split(l);
ll res = 0;
for (auto it = lit; it != rit; ++it)
res = (res + (it->r - it->l + 1) % y * qpow(it->v, x, y) % y) % y;
return res;
}
void solve()
{
std::cin >> n >> m >> seed >> vmax;
for (ll 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 (ll i = 1; i <= m; ++i)
{
ll op, l, r, x, y;
op = (rnd() % 4) + 1;
l = (rnd() % n) + 1;
r = (rnd() % n) + 1;
if (l > r)
std::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)
addx(l, r, x);
else if (op == 2)
modify(l, r, x);
else if (op == 3)
std::cout << x_th(l, r, x) << '\n';
else if (op == 4)
std::cout << pow_sum(l, r, x, y) << '\n';
}
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
ll T = 1;
// std::cin >> T;
while (T--)
solve();
return 0;
}