[Codeforces896C] Willem, Chtholly and Seniorious (ODT-珂朵莉树)

无聊学了一下珂朵莉树

珂朵莉树好哇，是可以维护区间x次方和查询的高效数据结构。

思想大致就是一个暴力（相对而言）的树形数据结构

lxl毒瘤太强了，发明了ODT算法（Old Driver Tree老司机算法）

这里有一个大佬ACDreamer的题解

附上链接https://www.luogu.org/blog/ACdreamer/solution-cf896c

还有一个B站的讲解视频

附上链接https://www.bilibili.com/video/av21651173

我不会用珂朵莉树，但是就是大致了解了一下吧

毕竟普及蒟蒻听不懂省选算法。

这里附上大佬的程序

#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 + ;

const int MOD9 = 1e9 + ;

const int imax_n = 1e5 + ;

LL pow(LL a, LL b, LL mod)

{

    LL res = ;

    LL ans = a % mod;

    while (b)

    {

        if (b&) res = res * ans % mod;

        ans = ans * ans % mod;

        b>>=;

    }

    return res;

}

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& 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-, V));

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

}

void add(int l, int r, LL val=)

{

    IT itl = split(l),itr = split(r+);

    for (; itl != itr; ++itl) itl->v += val;

}

void assign_val(int l, int r, LL val=)

{

    IT itl = split(l),itr = split(r+);

    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+);

    vp.clear();

    for (; itl != itr; ++itl)

        vp.push_back(pair<LL,int>(itl->v, itl->r - itl->l + ));

    std::sort(vp.begin(), vp.end());

    for (vector<pair<LL,int> >::iterator it=vp.begin();it!=vp.end();++it)

    {

        k -= it->second;

        if (k <= ) return it->first;

    }

    return -1LL;

}

LL sum(int l, int r, int ex, int mod)

{

    IT itl = split(l),itr = split(r+);

    LL res = ;

    for (; itl != itr; ++itl)

        res = (res + (LL)(itl->r - itl->l + ) * pow(itl->v, LL(ex), LL(mod))) % mod;

    return res;

}

int n, m;

LL seed, vmax;

LL rnd()

{

    LL ret = seed;

    seed = (seed *  + ) % MOD7;

    return ret;

}

LL a[imax_n];

int main()

{

    scanf("%d %d %lld %lld",&n,&m,&seed,&vmax);

    for (int i=; i<=n; ++i)

    {

        a[i] = (rnd() % vmax) + ;

        s.insert(node(i,i,a[i]));

    }

    s.insert(node(n+, n+, ));

    int lines = ;

    for (int i =; i <= m; ++i)

    {

        int op = int(rnd() % ) + ;

        int l = int(rnd() % n) + ;

        int r = int(rnd() % n) + ;

        if (l > r)

            std::swap(l,r);

        int x, y;

        if (op == )

            x = int(rnd() % (r-l+)) + ;

        else

            x = int(rnd() % vmax) +;

        if (op == )

            y = int(rnd() % vmax) + ;

        if (op == )

            add(l, r, LL(x));

        else if (op == )

            assign_val(l, r, LL(x));

        else if (op == )

            printf("%lld\n",rank(l, r, x));

        else

            printf("%lld\n",sum(l, r, x, y));

    }

    return ;

}