题解：P8969 幻梦 | Dream with Dynamic

this54c · 2026-10-22 13:34:37 · 题解

来一发爆标做法。

快进到用线段树维护了一个函数 F(x)=T(\operatorname{popcount}(x+a))，其中 T 函数的定义域只有 \log V 个值可以暴力处理。

考虑多维护一层，我们维护 F(x)=T(\operatorname{popcount}(\operatorname{popcount}(x+a)+b))。

此时严谨分析一下，内层的 \operatorname{popcount} 最多有 \log V 个值，然后加了 b 又取了一次 \operatorname{popcount}。考虑 T 函数的定义域的低 \log \log V 位，这些位置上对 \operatorname{popcount} 的贡献在 [0,\log \log V]。而对于更高的位，从低位的进位要么 0 要么 1，于是更高位上对 \operatorname{popcount} 的贡献最多有两种。

因此，这个 T 的定义域至多 2\log \log V 种。

使用线段树维护所有标记就可以做到在线，非均摊的修改 O(\log n\log \log V)，查询 O(\log n) 做法。

#include <bits/stdc++.h>
#define N 300010
#define int long long
#define ls nw << 1
#define rs nw << 1 | 1
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
using namespace std;
char buf[100001], * p1 = buf, * p2 = buf;
inline int rd()
{
    static int x; static unsigned char c; x = 0;
a:  c = gc; if (c < '0' || c > '9') goto a;
b:  x = (x << 1) + (x << 3) + (c & 0xf), c = gc; if (c >= '0' && c <= '9') goto b;
    return x;
}
inline char gtop()
{
    static unsigned char c;
a:  c = gc; if (c == 'A' || c == 'P' || c == 'J') return c;
    goto a;
}
int n, q;
int a[N];
struct info
{
    int t;
    int a, b;
    int val[14];
    inline int calc2(int x) const { return t == 1 ? x : val[(x >> 6 != b >> 6) * 7 + __builtin_popcountll(x & 63)]; }
    inline int calc(int x) const
    {
        if (t == 0) return x + a;
        return calc2(__builtin_popcountll(x + a) + b);
    }
}seg[N << 2], f, g;
inline void merg(info& x, const info& y)
{
    int v;
    if (x.t == 0) v = x.a, x = y, x.a += v;
    else if (x.t == 1)
    {
        x.b += y.a, x.t = min(2ll, 1 + y.t);
        if (y.t) for (int i = 0; i < 7; i++) x.val[i] = y.calc2(i + y.b + __builtin_popcountll(x.b >> 6)), x.val[7 + i] = y.calc2(i + y.b + __builtin_popcountll((x.b >> 6) + 1));
    }
    else for (int i = 0; i < 14; i++) x.val[i] = y.calc(x.val[i]);
}
inline void pud(int nw) { merg(seg[ls], seg[nw]), merg(seg[rs], seg[nw]); seg[nw].t = seg[nw].a = seg[nw].b = 0; }
void modify(int nw, int l, int r, int pl, int pr, info& x)
{
    if (pl <= l && r <= pr) return merg(seg[nw], x);
    int mid = (l + r) >> 1; pud(nw);
    if (pl <= mid) modify(ls, l, mid, pl, pr, x);
    if (mid < pr) modify(rs, mid + 1, r, pl, pr, x);
}
int query(int nw, int l, int r, int p)
{
    if (l == r) return seg[nw].calc(a[p]);
    int mid = (l + r) >> 1, res;
    if (p <= mid) res = query(ls, l, mid, p);
    else res = query(rs, mid + 1, r, p);
    return seg[nw].calc(res);
}
signed main()
{
    n = rd(), q = rd(), g.t = 1;
    for (int i = 1; i <= n; i++) a[i] = rd();
    static unsigned char op;
    static int l, r, x;
    while (q--)
    {
        op = gtop();
        if (op == 'A') l = rd(), r = rd(), x = rd(), f.a = x, modify(1, 1, n, l, r, f);
        else if (op == 'P') l = rd(), r = rd(), modify(1, 1, n, l, r, g);
        else x = rd(), fprintf(stdout, "%lld\n", query(1, 1, n, x));
    }
    return 0;
}