洛谷P8969 幻梦 | Dream with Dynamic 题解
题目链接: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$ ,则当前的节点维护
区间加直接修改 $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
虽说我觉得有时候我的题解疑似有缝合的性质,但是我一直尽力在理解学习这些题目的思路了。
题外话:
题目背景:(挺有意思)
“那以后见到她,会不会笑出来啊?”
“哈,一时半会见不到她的。”
小时候说要一起去看尘寰间的人间烟火,有人欣然接受,长大了说遗忘过去,那人也没有反驳。
其实吧,她们彼此明白,小时候在意的不是什么人间烟火,而是一起。
黑夜里,没有早晨的绯红,也褪去了天边的白光,留下的是她心头的散不去的灰暗。没有星光璀璨,没有满天繁星,她不在乎。她在乎的是那个人心中闪烁的星辰大海。
察觉所谓规则秘密,不过取悦于创世神明,早已知晓光明同黑暗般腥风血雨。
我想说,若存在仅仅是为了取悦神明,那么找寻意义的过程已经赋予了我们新的生命。