【题解】Willem, Chtholly and Seniorious 珂朵莉树/链 CF896C

于由XZYQvQ发布

1. 题目

传送门=￣ω￣=

题意翻译

请你写一种奇怪的数据结构，支持：
– $1$ $l$ $r$ $x$：将 $[l,r]$区间所有数加上 $x$
– $2$ $l$ $r$ $x$：将 $[l,r]$区间所有数改成 $x$
– $3$ $l$ $r$ $x$：输出将 $[l,r]$区间从小到大排序后的第 $x$个数是的多少 (即区间第 $x$小，数字大小相同算多次，保证 $1\leq$ $x$ $\leq$ $r-l+1$ )
– $4$ $l$ $r$ $x$ $y$：输出 $[l,r]$区间每个数字的 $x$次方的和模 $y$的值 (即 ($\sum^r_{i=l}a_i^x$) $\mod y$)

题解

奥妙重重的暴力。。。

另外这个原本叫 Old Driver Tree(ODT)，老司机树。。。

具体什么意思呢，其实非常简单。

根据 NOIP 初赛知识我们可以知道，在线段上随机取俩点它们的距离期望是 $\frac 1 3$

也就是在随机数据下你进行一次操作 $4$期望会把连续的长度为 $\frac n 3$的序列的值全部修改为同一个值。

那么我们就可以把这 $\frac n 3$个节点合并成一个 “区间” 节点。

随机数据下这个节点个数是很少的。

因为在这题中：

  • 有 $\frac 1 4$的概率会期望让序列变为原来的 $\frac 2 3$倍
  • 有 $\frac 3 4$的概率让序列多增加两个元素（$+2$）

因此经过非常多次的修改后最终期望的节点个数是 $18$个（Calculated by boshi）

所以复杂度大概就是个 $n \log n$级别的

具体操作很简单，就是每次提取出需要操作的区间，然后暴力一个点一个点地加，因为点数少所以快。

如果当前需要提取的区间边界在某个节点所代表的区间内部就分裂这个节点（也就是前面所说的 $\frac 3 4$的概率增加两个元素）

其余的和数组暴力没区别。

然后网上似乎都写的是 set 实现的，甚至说别的数据结构实现的都是异端。。。

然而我觉得 set 不够优美，它常数太大了。

因为本身这个复杂度是基于块的个数的，和块的检索速度并没有多大关系，因此我用 list 链表代替了 set，确实快上不少（5 秒变 3.5 秒）

而且 list 个人感觉好打且好想一些，list 迭代器不会失效（虽然说 set 迭代器似乎也不会失效。。。）

还是上代码吧，如果有不懂得代码应该还算清楚。

代码中的 Divide(l, r)表示提取区间 $[l, r]$（并且会返回一对左闭右开的迭代器）

先上 list 实现的代码：

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

typedef long long LL;

typedef pair<LL, int> PLI;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

LL qpow(LL a, LL b, LL mod)
{
    LL res = 1; a %= mod;
    while (b)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return res % mod;
}

struct N
{
    int l, r; LL d;
    N(int a, int b, LL c) {l = a, r = b, d = c;}
};

list<N> t;

typedef list<N>::iterator itr;

void Divide(int l, int r, itr& L, itr& R)
{
    L = t.begin();
    while (L->r < l) L++;
    if (L->l < l) t.insert(L, N(L->l, l - 1, L->d)), L->l = l;
    R = L;
    while (R->r < r) R++;
    if (R->r > r)
    {
        itr tmp = R; tmp++;
        t.insert(tmp, N(r + 1, R->r, R->d)), R->r = r;
    }
    R++;
}

void Add(int l, int r, LL x)
{
    itr L, R; Divide(l, r, L, R);
    while (L != R) L->d += x, L++;
}

void Modify(int l, int r, LL x)
{
    itr L, R; Divide(l, r, L, R);
    L->r = r, L->d = x, L++, t.erase(L, R);
}

LL Kth(int l, int r, int x)
{
    static vector<PLI> srt; srt.clear();
    itr L, R; Divide(l, r, L, R);
    while (L != R) srt.push_back(PLI(L->d, L->r - L->l + 1)), L++;
    sort(srt.begin(), srt.end());
    LL res = -1; int i = 0;
    while (x > 0) res = srt[i].first, x -= srt[i].second, i++;
    return res;
}

LL PowSum(int l, int r, LL x, LL y)
{
    itr L, R; Divide(l, r, L, R);
    LL res = 0;
    while (L != R)
        res = (res + qpow(L->d, x, y) * ((L->r - L->l + 1) % y) % y) % y, L++;
    return res;
}

int n, m;

LL seed, vmx;

LL rnd()
{
    LL res = seed;
    seed = (seed * 7 + 13) % 1000000007;
    return res;
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(seed), IN(vmx);
    for (LL i = 1; i <= n; i += 1) t.push_back(N(i, i, rnd() % vmx + 1));
    for (LL i = 1, op, l, r, x; i <= m; i += 1)
    {
        op = rnd() % 4 + 1, l = rnd() % n + 1, r = rnd() % n + 1;
        if (l > r) swap(l, r);
        if (op == 3) x = rnd() % (r - l + 1) + 1;
        else x = rnd() % vmx + 1;
        if (op == 1) Add(l, r, x);
        else if (op == 2) Modify(l, r, x);
        else if (op == 3) printf("%lld\n", Kth(l, r, x));
        else if (op == 4)
            printf("%lld\n", PowSum(l, r, x, rnd() % vmx + 1));
    }
    return 0;
}

再上 set 实现的代码（set 是最开始写的好像比较丑 QAQ）：

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

typedef long long LL;

typedef pair<LL, int> PLI;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

LL qpow(LL a, LL b, LL mod)
{
    LL res = 1; a %= mod;
    while (b)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return res % mod;
}

struct N
{
    LL l, r; mutable LL d;
    N(LL a, LL b = -1, LL c = -1) {l = a, r = b, d = c;}
    bool operator < (const N oth) const {return l < oth.l;}
};

set<N> t;

typedef set<N>::iterator itr;

void Split(LL x)
{
    itr p = t.lower_bound(N(x));
    if (p == t.end() || p->l > x) p--;
    if (p->r < x) return;
    if (p->l < x)
    {
        LL tl = p->l, tr = p->r, td = p->d;
        t.erase(p), t.insert(N(tl, x - 1, td)), t.insert(N(x, tr, td));
    }
}

void Divide(LL l, LL r, itr& L, itr& R)
{
    Split(l), Split(r + 1);
    L = t.lower_bound(N(l)), R = t.lower_bound(N(r + 1));
}

void Add(LL l, LL r, LL d)
{
    itr L, R;
    Divide(l, r, L, R);
    while (L != R) L->d += d, L++;
}

void Modify(LL l, LL r, LL d)
{
    itr L, R;
    Divide(l, r, L, R), t.erase(L, R);
    t.insert(N(l, r, d));
}

vector<PLI> srt;

LL Kth(LL l, LL r, LL k)
{
    itr L, R; srt.clear();
    Divide(l, r, L, R);
    while (L != R) srt.push_back(PLI(L->d, L->r - L->l + 1)), L++;
    sort(srt.begin(), srt.end());
    LL res = -1;
    for (LL i = 0; i < srt.size() && k > 0; i += 1)
        res = srt[i].first, k -= srt[i].second;
    return res;
}

LL PowSum(LL l, LL r, LL x, LL y)
{
    itr L, R;
    Divide(l, r, L, R);
    LL res = 0;
    while (L != R)
        res = (res + qpow(L->d, x, y) * ((L->r - L->l + 1) % y) % y) % y, L++;
    return res;
}

LL n, m, seed, vmx;

LL rnd()
{
    LL res = seed;
    seed = (1ll * seed * 7 + 13) % 1000000007;
    return res;
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(seed), IN(vmx);
    for (LL i = 1; i <= n; i += 1) t.insert(N(i, i, rnd() % vmx + 1));
    for (LL i = 1, op, l, r, x; i <= m; i += 1)
    {
        op = rnd() % 4 + 1, l = rnd() % n + 1, r = rnd() % n + 1;
        if (l > r) swap(l, r);
        if (op == 3) x = rnd() % (r - l + 1) + 1;
        else x = rnd() % vmx + 1;
        if (op == 1) Add(l, r, x);
        else if (op == 2) Modify(l, r, x);
        else if (op == 3) printf("%lld\n", Kth(l, r, x));
        else if (op == 4)
            printf("%lld\n", PowSum(l, r, x, rnd() % vmx + 1));
    }
    return 0;
}
分类： 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

2 条评论

智子 · 2019年9月6日 12:44 下午

%%%% Orz

回复

B_Z_B_Y · 2018年10月19日 5:57 下午

%%%% Orz

回复

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注