洛谷P8969 幻梦 | Dream with Dynamic 题解

题意：

有一个长度为 \(n\) 的序列，开始时第 \(i\) 位为 \(a_i\)。你需要完成 \(q\) 次操作：

A l r x，对于所有的 \(l\le i\le r\)，令 \(a_i\gets a_i+x\)。

P l r，对于所有的 \(l\le i\le r\)，令 \(a_i\gets\operatorname{popcount}(a_i)\)。

J p，查询 \(a_p\) 的值。

其中 \(\operatorname{popcount}(x)\) 为 \(x\) 的二进制表示中 \(1\) 的个数。

注意：本题时空限制为 10s 1.00GB。

输入格式：

第一行两个正整数 \(n,q\)。

第二行 \(n\) 个正整数 \(a_1, a_2, \ldots, a_n\)。

接下来 \(q\) 行，每行描述一个操作，形如以下三种中的一种：

A l r x

P l r

J p

输出格式：

对于每个 J 操作，输出一行，一个整数，表示答案。

数据范围：

保证 \(1\leq n\leq 3\times 10^5\)，\(1 \le q \le 10^6\)，\(1 \le l \le r \le n\)，\(1 \le p \le n\)，\(1\le a_i, x\le 10^9\)。

本题最大 I/O 量达到 30 MiB，请注意 I/O 效率。

区间 \(x \gets f(x)\) 并不是很好解决，但是注意到这次的是 \(\mathrm{popc}\) 函数，令值域为 \(V\) ，它的值域即 \(\mathcal{O}(\log V)\) 的

也就是说，如果一个区间已经进行过一次操作，那么它的值域仍不会大于 \(\mathcal{O}(\log V)\) 。

考虑用在线段树上维护一个长为 \(\mathcal{O}(\log V)\) 长的置换 \(f\) ，给予参数 \(A,B,p\) ，则当前的节点维护 \[ x^{\prime}= \begin{cases} x+B & p=0 \\[6pt] f(\operatorname{popc}(x+A))+B & p=1 \end{cases} \] 区间加直接修改 \(B\) ，区间 \(\mathrm{popc}\) 只需遍历置换 \(f\) 并求值即可。

这么做时间复杂度是 \(\mathcal{O}((n + q) \log n\log V)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
#define popc(x) __builtin_popcountll(x)
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e5 + 15))
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

int n,Q; ll a[N];
struct node
{
    bool flag; ll a,b; char p[64];
    ll ask(ll x) { return flag ? p[popc(x + a)] + b : x + b; }
    void clear() {
        flag = 0; a = b = 0;
        for(int i = 0; i < 64; i++) p[i] = 0;
    }
}tr[N << 2];

void merge(node &x, node y)
{
    if(!y.flag) { x.b += y.b; }
    else if(x.flag)
    {
        for(int i = 0; i < 64; i++)
            x.p[i] = y.p[popc(x.p[i] + x.b + y.a)];
        x.b = y.b;
    }else { y.a += x.b; x = y; }
}

void push_down(int at)
{
    merge(tr[ls(at)], tr[at]);
    merge(tr[rs(at)], tr[at]); tr[at].clear();
}

void update(int nl, int nr, node x, int l = 1, int r = n, int at = 1)
{
    if(nl <= l && r <= nr) return merge(tr[at], x), void(0);
    int mid = (l + r) >> 1; push_down(at);
    if(nl <= mid) update(nl, nr, x, l, mid, ls(at));
    if(nr > mid) update(nl, nr, x, mid + 1, r, rs(at));
}

ll query(int x, int l = 1, int r = n, int at = 1)
{
    if(l == r) return tr[at].ask(a[x]);
    int mid = (l + r) >> 1; push_down(at);
    if(x <= mid) return query(x, l, mid, ls(at));
    else return query(x, mid + 1, r, rs(at));
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> Q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int l,r,x; Q--; )
    {
        char ch; cin >> ch;
        if(ch == 'A')
        {
            cin >> l >> r >> x;
            node g; g.flag = 0; g.b = x; update(l,r,g);
        }
        else if(ch == 'P')
        {
            cin >> l >> r;
            node g; g.flag = 1; g.a = g.b = 0;
            for(int i = 0; i < 64; i++) g.p[i] = i;
            update(l,r,g);
        }
        else if(ch == 'J')
        {
            cin >> x;
            cout << query(x) << '\n';
        }
    }
    return 0;
}

结果一看，怎么跑了一共跑了17s，好慢！

原因部分在于，对于一些 \(\mathcal{O}(\log V)\) 级的区间，push_down 还不如暴力速度快。

考虑对线段树的一些节点打上标记，表示这个节点是一个“值域很小的连续段”。

每次找出若干个需要被合并的连续段，暴力对里面的每一个值计算 \(\mathrm{popc}\) ，

同样的，我们在每个点记录置换，并把所有需要合并的连续段线段树上的 LCA 打上标记

不妨记标记节点的个数为势能，考虑分析时间复杂度。

区间修改时，标记节点被 push_down 会标记两个新的节点，因此势能总量是 \(\mathcal{O}(q\log n)\) 级的。

而每次花费 \(\mathcal{O}(\log V)\) 的代价合并一个标记节点，所以两种修改均摊都是 \(\mathcal{O}(\log n\log V)\) 的。

有趣的是，因为我们用到了标记永久化，所以询问是 \(\mathcal{O}(\log n)\) 的，并且这种解法减少了 push_down 的问题

时间复杂度 \(\mathcal{O}(q\log n\log V)\) ，常数也小了不少。

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
#define popc(x) __builtin_popcountll(x)
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e5 + 15))
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

const int Lg = 64;
int n,Q,a[N]; ll tag[N << 2]; char p[N << 2][Lg], flag[N << 2];
void build(int at = 1, int l = 1, int r = n)
{
    for(int i = 0; i < Lg; i++) p[at][i] = i;
    if(l == r) { return flag[at] = true, tag[at] = a[l], void(0); }
    flag[at] = false; tag[at] = 0;
    int mid = (l + r) >> 1; build(ls(at), l, mid); build(rs(at), mid + 1, r); 
}
void proc(int at) {
    for(int i = 0; i < Lg; i++)
        p[at][i] = popc(p[at][i] + tag[at]);
    tag[at] = 0;
}
void push_down(int at)
{
    if(flag[at])
    {
        for(int i = 0; i < Lg; i++)
        {
            p[ls(at)][i] = p[at][(int)p[ls(at)][i]];
            p[rs(at)][i] = p[at][(int)p[rs(at)][i]];
        }
        for(int i = 0; i < Lg; i++) p[at][i] = i;
        flag[ls(at)] = flag[rs(at)] = 1; flag[at] = 0;
    }
    if(tag[at]) { tag[ls(at)] += tag[at]; tag[rs(at)] += tag[at]; tag[at] = 0; }
}
void upd(int at, int l, int r)
{
    if(flag[at]) return proc(at);
    push_down(at); int mid = (l + r) >> 1;
    upd(ls(at), l, mid); upd(rs(at), mid + 1, r);
}
void update(int nl, int nr, int at = 1, int l = 1, int r = n)
{
    if(nl <= l && r <= nr) { upd(at, l, r); flag[at] = 1; return; }
    push_down(at); int mid = (l + r) >> 1;
    if(nl <= mid) update(nl, nr, ls(at), l, mid);
    if(nr > mid) update(nl, nr, rs(at), mid + 1, r);
}
void modify(int nl, int nr, int x, int at = 1, int l = 1, int r = n)
{
    if(nl <= l && r <= nr) { return tag[at] += x, void(0); }
    push_down(at); int mid = (l + r) >> 1;
    if(nl <= mid) modify(nl, nr, x, ls(at), l, mid);
    if(nr > mid) modify(nl, nr, x, rs(at), mid + 1, r);
}
ll query(int x, int at = 1, int l = 1, int r = n)
{
    if(l == r) return p[at][0] + tag[at];
    int mid = (l + r) >> 1;
    if(flag[at]) {
        if(x <= mid) return p[at][query(x, ls(at), l, mid)] + tag[at];
        else return p[at][query(x, rs(at), mid + 1, r)] + tag[at];
    }else {
        if(x <= mid) return query(x, ls(at), l, mid) + tag[at];
        else return query(x, rs(at), mid + 1, r) + tag[at];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> Q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build();
    for(int l,r,x; Q--; )
    {
        char ch; cin >> ch;
        if(ch == 'A') { cin >> l >> r >> x; modify(l,r,x); }
        else if(ch == 'P') { cin >> l >> r; update(l,r); }
        else if(ch == 'J') { cin >> x; cout << query(x) << '\n'; }
    }
    return 0;
}

参考文献：

[1] https://yyyyxh329.blog.luogu.org/solution-p8969

[2] https://www.luogu.com.cn/blog/dreamerkk/solution-p8969

[3] https://www.luogu.com.cn/blog/writeSTL/solution-p8969

虽说我觉得有时候我的题解疑似有缝合的性质，但是我一直尽力在理解学习这些题目的思路了。

题外话：

题目背景：（挺有意思）

“那以后见到她，会不会笑出来啊？”

“哈，一时半会见不到她的。”

小时候说要一起去看尘寰间的人间烟火，有人欣然接受，长大了说遗忘过去，那人也没有反驳。

其实吧，她们彼此明白，小时候在意的不是什么人间烟火，而是一起。

黑夜里，没有早晨的绯红，也褪去了天边的白光，留下的是她心头的散不去的灰暗。没有星光璀璨，没有满天繁星，她不在乎。她在乎的是那个人心中闪烁的星辰大海。

察觉所谓规则秘密，不过取悦于创世神明，早已知晓光明同黑暗般腥风血雨。

我想说，若存在仅仅是为了取悦神明，那么找寻意义的过程已经赋予了我们新的生命。

q779

https://q779.cn/2023/12/31/luo-gu-p8969-huan-meng-dream-with-dynamic-ti-jie/