LGP8969 幻梦 Dream with Dynamic
\(\texttt{Luogu Link}\)
前言
唉，强校。
抛开别的不谈，这题意外地好懂……吗？
本学习笔记解析部分抄袭此文，代码抄袭此文。
题意简述
有一个长度为 \(n\) 的序列 \(A\)，有初值。需支持三种操作共 \(m\) 次：
A l r x：\(\forall i\in [l,r]\)，\(a_i\gets a_i+x\)。P l r：\(\forall i\in [l,r]\)，\(a_i\gets \text{ppc}(a_i)\)。J u：查询 \(a_u\) 的值。
\(n\le 3\times 10^5\)，\(q\le 10^6\)，\(a_i,x\le 10^9\)。
做法解析
看起来和有些势能线段树很像？然而这题的势能没什么良好性质。那咋办。
但是 \(\text{ppc}\) 有非常良好的性质。它的值域只有 \(\log V\)。怎么用呢？
首先我们查询只有单点的，这两种修改在线段树上成区间地作用是简单的。所以我们思考单点受到的操作就行了。
我们来把操作序列写出来：\(\texttt{apapppaaaapaapa}\)。
连串的加法是容易复合的，不妨把它们缩到一段，再按 \(\texttt{p}\) 割开操作序列：
\(\texttt{ap|ap|p|p|ap|ap|a}\)。这是若干个 \(\text{ppc}(x+b)\to x'\) 的复合，满足 \(x,x'\) 值域和定义域都在 \(\log V\) 范围（除了最开始的 \(x\)）。我们对于 \(w\in [0,\log V]\)，维护 \(F(w)=f_k(f_{k-1}(f_{k-2}(\dots f_3(f_2(f_1(w)))\dots)))\) 的值，其中 \(f_i(w)\) 为第一个 \(\text{ppc}\) 操作之后的第 \(i\) 个 \(\text{ppc}(x+b)\to x'\)。
另外特殊处理一下没有 \(\text{ppc}\) 的情况即可。
代码实现
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=3e5+5,MaxVb=51;
int N,M,A[MaxN],X,Y,Z;char Opt;
struct adat{int o;lolo d,b[MaxVb];};
adat addion(adat t,lolo x){if(t.o==0)t.d+=x;else for(int i=0;i<=50;i++)t.b[i]+=x;return t;
}
adat ppcion(adat t){if(t.o==0)for(int i=0;i<=50;i++)t.b[i]=i;else for(int i=0;i<=50;i++)t.b[i]=__builtin_popcountll(t.b[i]);t.o=1;return t;
}
adat merge(adat x,adat y){if(y.o==0)return addion(x,y.d);if(x.o==0){y.d+=x.d;return y;}for(int i=0;i<=50;i++)x.b[i]=y.b[__builtin_popcountll(x.b[i]+y.d)];return x;
}
struct SegTree{adat t[MaxN<<2];int cl[MaxN<<2],cr[MaxN<<2],cmid[MaxN<<2];int ls(int u){return u<<1;}int rs(int u){return (u<<1)|1;}void build(int u,int l,int r){cl[u]=l,cr[u]=r;if(l==r)return;int mid=(l+r)>>1;cmid[u]=mid;build(ls(u),l,mid),build(rs(u),mid+1,r);}void pushdown(int u){t[ls(u)]=merge(t[ls(u)],t[u]);t[rs(u)]=merge(t[rs(u)],t[u]);t[u].o=t[u].d=0;}void addupd(int u,int dl,int dr,int x){if(dl<=cl[u]&&cr[u]<=dr){t[u]=addion(t[u],x);return;}pushdown(u);if(dl<=cmid[u])addupd(ls(u),dl,dr,x);if(dr>cmid[u])addupd(rs(u),dl,dr,x);}void ppcupd(int u,int dl,int dr){if(dl<=cl[u]&&cr[u]<=dr){t[u]=ppcion(t[u]);return;}pushdown(u);if(dl<=cmid[u])ppcupd(ls(u),dl,dr);if(dr>cmid[u])ppcupd(rs(u),dl,dr);}adat query(int u,int dd){if(cl[u]==cr[u])return t[u];pushdown(u);return query(dd<=cmid[u]?ls(u):rs(u),dd);}
}SgT;
int main(){readis(N,M);SgT.build(1,1,N);for(int i=1;i<=N;i++)readi(A[i]);for(int i=1;i<=M;i++){scanf(" %c",&Opt);if(Opt=='A')readis(X,Y,Z),SgT.addupd(1,X,Y,Z);if(Opt=='P')readis(X,Y),SgT.ppcupd(1,X,Y);if(Opt=='J'){readi(X);adat res=SgT.query(1,X);if(res.o==0)writil(A[X]+res.d);else writil(res.b[__builtin_popcountll(A[X]+res.d)]);}}return 0;
}