题解 CF896C 【Willem, Chtholly and Seniorious】

2018-07-25 11:26:25


珂朵莉树模板题。

一、什么是珂朵莉树

珂朵莉树,又称Old Driver Tree(ODT)。是一种基于std::set的暴力数据结构。B站上有UESTC的讲解视频

二、什么时候用珂朵莉树

关键操作:推平一段区间,使一整段区间内的东西变得一样。保证数据随机。

就像这道题。

$n$ 个数, $m$ 次操作 $(n,m\leq10^5)$ 。

操作:

  1. 区间加
  2. 区间赋值
  3. 区间第k小
  4. 求区间幂次和

数据随机,时限2s。

三、珂朵莉树的初始化

这道题里,这样定义珂朵莉树的节点:

struct node
{
    int l,r;
    mutable LL v;
    node(int L, int R=-1, LL V=0):l(L), r(R), v(V) {}
    bool operator<(const node& o) const
    {
        return l < o.l;
    }
};

这样的一个节点表示 $[l,r]$ 内的所有数都是v。需要注意的是mutable,意为易变的,不定的。它对v的修饰,使得我们可以在add操作中修改v的值。没有它的修饰会在add函数里导致CE。

我们把节点存在set里。

set<node> s;

像CF896C这道题就这样初始化。

cin>>n>>m>>seed>>vmax;
for (int i=1; i<=n; ++i)
{
    a[i] = (rnd() % vmax) + 1;
    s.insert(node(i,i,a[i]));
}

初始化完了?初始化完了。

四、珂朵莉树的核心操作:split

split(pos)操作是指将原来含有pos位置的节点分成两部分: $[l,pos-1]$ 和 $[pos,r]$ 。

看这个操作的代码:

#define IT set<node>::iterator
IT split(int pos)
{
    IT it = s.lower_bound(node(pos));
    if (it != s.end() && it->l == pos) return it;
    --it;
    int L = it->l, R = it->r;
    LL V = it->v;
    s.erase(it);
    s.insert(node(L, pos-1, V));
    return s.insert(node(pos, R, V)).first;
}

一行一行来看。

#define IT set<node>::iterator

宏定义没什么好说的,记住NOI系列赛事不能用autoauto一时爽,评测火葬场。

IT it = s.lower_bound(node(pos));

找到首个 $l$ 不小于pos的节点。

if (it != s.end() && it->l == pos)
    return it;

如果无需split,直接返回。

--it;

否则pos一定在前一个区间中。

int L = it->l, R = it->r;

$[L,R]$ 就是要被分割的区间。

LL V = it->v;

取出这个节点的值。

s.erase(it);

删除原节点。

s.insert(node(L, pos-1, V));

插入前半段。

return s.insert(node(pos, R, V)).first;

插入后半段,返回后半段的迭代器。这里利用了pair<iterator,bool> insert (const value_type& val)的返回值。

五、珂朵莉树的推平操作:assign

要是只有split还不得复杂度爆炸?我们需要assign操作迅速减小set的规模。

void assign(int l, int r, LL val=0)
{
    IT itl = split(l),itr = split(r+1);
    s.erase(itl, itr);
    s.insert(node(l, r, val));
}

一些萌新可能没有见过erase的这种用法,你们应该学习一个。C++98中void erase (iterator first, iterator last)可删除 $[first,last)$ 区间。这里就是把 $[l,r+1)$ 内的部分推成一段。

珂朵莉树的复杂度是由assign保证的。由于数据随机,有 $\frac{1}{4}$ 的操作为assignset的大小快速下降,最终趋于 $\log n$ ,使得这种看似暴力无比的数据结构复杂度接近 $m\log n$ 。

六、其他操作:一个比一个暴力

区间加:

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

分裂出来挨个加一下就行。

区间第k小:

LL rank(int l, int r, int k)
{
    vector<pair<LL, int> > vp;
    IT itl = split(l),itr = split(r+1);
    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 it=vp.begin();it!=vp.end();++it)
    {
        k -= it->second;
        if (k <= 0) return it->first;
    }
    return -1LL;
}

暴力取出排序就好了,反正也没有多少段。

LL sum(int l, int r, int ex, int mod)
{
    IT itl = split(l),itr = split(r+1);
    LL res = 0;
    for (; itl != itr; ++itl)
        res = (res + (LL)(itl->r - itl->l + 1) * pow(itl->v, LL(ex), LL(mod))) % mod;
    return res;
}

暴力遍历,快速幂,然后加起来。

那么,这道题就可做了。而且我们交了一发,发现这玩意跑得完全不像暴力,最慢的点是500多ms。

七、一些习题

UESTC的B站讲解里还有另两道题,一道是CF915E,另一道是BZOJ4293割草(权限题)。这两道题的主流做法都是线段树,珂朵莉树也可做。但珂朵莉树仍能体现出代码量较小、易查错的优势,适合作为珂朵莉树的练习题。

#include<cstdio>
#include<set>
#include<vector>
#include<utility>
#include<algorithm>
#define IT set<node>::iterator

using std::set;
using std::vector;
using std::pair;

typedef long long LL;
const int MOD7 = 1e9 + 7;
const int MOD9 = 1e9 + 9;
const int imax_n = 1e5 + 7;

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;
}

struct node
{
    int l,r;
    mutable LL v;
    node(int L, int R=-1, LL V=0):l(L), r(R), v(V) {}
    bool operator<(const node& o) const
    {
        return l < o.l;
    }
};

set<node> s;

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

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

void assign_val(int l, int r, LL val=0)
{
    IT itl = split(l),itr = split(r+1);
    s.erase(itl, itr);
    s.insert(node(l, r, val));
}

LL rank(int l, int r, int k)
{
    vector<pair<LL, int> > vp;
    IT itl = split(l),itr = split(r+1);
    vp.clear();
    for (; itl != itr; ++itl)
        vp.push_back(pair<LL,int>(itl->v, itl->r - itl->l + 1));
    std::sort(vp.begin(), vp.end());
    for (vector<pair<LL,int> >::iterator it=vp.begin();it!=vp.end();++it)
    {
        k -= it->second;
        if (k <= 0) return it->first;
    }
    return -1LL;
}

LL sum(int l, int r, int ex, int mod)
{
    IT itl = split(l),itr = split(r+1);
    LL res = 0;
    for (; itl != itr; ++itl)
        res = (res + (LL)(itl->r - itl->l + 1) * pow(itl->v, LL(ex), LL(mod))) % mod;
    return res;
}

int n, m;
LL seed, vmax;

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

LL a[imax_n];

int main()
{
    scanf("%d %d %lld %lld",&n,&m,&seed,&vmax);
    for (int i=1; i<=n; ++i)
    {
        a[i] = (rnd() % vmax) + 1;
        s.insert(node(i,i,a[i]));
    }
    s.insert(node(n+1, n+1, 0));
    int lines = 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)
            std::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)
            assign_val(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;
}