P8968 觅光
称包含目标点 \(u\) 的那颗子树为目标子树，结论就是只要非目标子树容量充足，后手可以至少将一半的球扔到非目标子树里去。而且只要先手只扔正电球就可以达到这个下界。
现在我们考虑数据结构的部分，维护子树内所有点的答案，那么相当于对于一部分值 \(\times 2\)，一部分值 \(+a\)。树套树/树上启发式合并都可以 \(O(n\log^2n)\) 维护，但比较难写。
注意到对于一个点 \(\times 2\) 操作最多有 \(O(\log \sum c_i)\) 次，相当于我们每次可以暴力枚举子树中答案最小的若干个数 \(\times 2\)，剩下的东西打加法 tag。
考虑一种更清新的数据结构可并堆。每次 pop 出所有 \(\leq a\) 的数，给剩下的数打加法 tag，然后把 pop 出来的数 \(\times 2\) 塞回去。复杂度依然两个 \(\log\)。
注意到 \(f(x)=x+\min(x,a)\) 关于 \(x\) 是单调的，我们对可并堆中所有值进行 \(x\leftarrow f(x)\) 不会改变相对大小关系也就不会改变堆的结构。于是我们只需要在堆结构中 dfs 出所有 \(\leq x\) 的元素，再给堆删去这些元素形成的森林的所有的根打 tag。复杂度 \(O(n\log \sum c_i)\)，足以通过此题。
//read()
const int N=1000003;
typedef long long ll;
int n,rk;
int a[N],ft[N];
bool cnt[N];
ll seq[N],c[N],f[N],tg[N];
int lc[N],rc[N],rt[N];
int ch[N][2],d[N];
void proc(int p,ll v){tg[p]+=v;f[p]+=v;}
void pushdown(int p){
if(tg[p]){
if(lc[p]) proc(lc[p],tg[p]);
if(rc[p]) proc(rc[p],tg[p]);
tg[p]=0;
}
}
int merge(int x,int y){
if(!x||!y) return x|y;
if(f[x]>f[y]) swap(x,y);
pushdown(x);
rc[x]=merge(rc[x],y);
if(d[lc[x]]<d[rc[x]]) swap(lc[x],rc[x]);
d[x]=d[rc[x]]+1;
return x;
}
void upd(int p,ll v){
if(f[p]<v) f[p]<<=1;
else return proc(p,v);
pushdown(p);
if(lc[p]) upd(lc[p],v);
if(rc[p]) upd(rc[p],v);
}
void dfs(int u){
if(ch[u][0]) dfs(ch[u][0]);
if(ch[u][1]) dfs(ch[u][1]);
f[u]=(c[u]+=c[ch[u][0]]+c[ch[u][1]]);rt[u]=u;
if(ch[u][0]){
upd(rt[ch[u][0]],c[ch[u][1]]);
rt[u]=merge(rt[u],rt[ch[u][0]]);
}
if(ch[u][1]){
upd(rt[ch[u][1]],c[ch[u][0]]);
rt[u]=merge(rt[u],rt[ch[u][1]]);
}
}
void push(int p){
pushdown(p);
if(lc[p]) push(lc[p]);
if(rc[p]) push(rc[p]);
}
int main(){
n=read();
for(int i=2;i<=n;++i){
int p=read();
if(ch[p][0]) ch[p][1]=i;
else ch[p][0]=i;
}
for(int i=1;i<=n;++i) c[i]=read<ll>();
dfs(1);push(rt[1]);
for(int i=1;i<=n;++i) printf("%lld ",f[i]);
putchar('\n');
return 0;
}
P8969 幻梦
数据结构好题呢。
区间 \(x\leftarrow f(x)\) 很不好做，然而这道题的突破口在于 \(f(x)=\text{popcount}(x)\) 它值域仅有 \(O(\log V)\)。
当只有 P 操作时，我们可以维护一系列的值域很小的连续段，类似 ODT 一样合并连续段，把连续段个数当成势能，每次操作最多增加两个连续段，每次花费 \(O(\log V)\) 的代价势能就会 \(-1\)，总复杂度 \(O((n+q)\log V\alpha(n))\)。
具体怎么合并连续段呢？发现在做过一次 \(\text{popcount}\) 后再做 \(\text{popcount}\) 相当于值域复合上一个长度为 \(O(\log V)\) 的置换，并查集维护。
当拥有 A 操作时事情变得复杂起来，因为你每次要对一个连续段的区间打 tag，不知道可不可以用一颗平衡树去维护连续段，感觉这样太复杂就没顺着这个思路想下去。
既然常规做法做不了就去想块块，依然考虑给值域很小的块块打上标记维护置换，这次我们发现如果给块块打加法标记变得很快了，代价是维护置换的部分多了一个根号，平衡下复杂度大概可以做到 \(O(q\sqrt{n\log V})\)，显然跑不过所以没去实现。
发现我们上述做法并没有怎么依赖分块的性质，而主要是在“打加法标记”和“维护值域小的连续段”之间进行平衡，也就是说我们可以换用线段树。本质是我们原来维护极大的“值域很小的段”，现在强行把它劈成线段树/分块的形态方便我们打加法标记。
具体地来说，我们这次给线段树的一些节点打上“终止标记”，代表这个节点是一个“值域很小的连续段”。每次找出若干个需要被合并的连续段，暴力对里面的每一个值计算 \(\text{popcount}\)，运用标记永久化的思想把计算出来的长为 \(O(\log V)\) 的置换记在这个点，然后把所有需要合并的连续段线段树上的 LCA 标记为新的终止节点。
记终止节点的个数是势能。区间修改时，终止节点被 pushdown 会标记两个新的终止节点，所以势能总量是 \(O(q\log n)\) 级别的。每次花费 \(O(\log V)\) 的代价合并一个终止节点，所以两种修改均摊都是 \(O(\log n\log V)\) 的。单点查询标记永久化了所以是 \(O(\log n)\) 的。
#include <cstdio>
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
//read()
typedef long long ll;
const int N=300003,Lg=50;
int n,q;
int a[N];
int per[N<<2][Lg];
ll tg[N<<2];
bool ex[N<<2];
void build(int p=1,int l=1,int r=n){
for(int i=0;i<Lg;++i) per[p][i]=i;
if(l==r){ex[p]=1;tg[p]=a[l];return;}
ex[p]=0;tg[p]=0;
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
void proc(int p){
for(int i=0;i<Lg;++i)
per[p][i]=__builtin_popcountll(per[p][i]+tg[p]);
tg[p]=0;
}
void pushdown(int p){
if(ex[p]){
for(int i=0;i<Lg;++i){
per[lc][i]=per[p][per[lc][i]];
per[rc][i]=per[p][per[rc][i]];
}
for(int i=0;i<Lg;++i) per[p][i]=i;
ex[lc]=ex[rc]=1;ex[p]=0;
}
if(tg[p]){tg[lc]+=tg[p];tg[rc]+=tg[p];tg[p]=0;}
}
void upd(int p,int l,int r){
if(ex[p]) return proc(p);
pushdown(p);
int mid=(l+r)>>1;
upd(lc,l,mid);upd(rc,mid+1,r);
}
void update(int ll,int rr,int p=1,int l=1,int r=n){
if(ll<=l&&r<=rr){upd(p,l,r);ex[p]=1;return;}
pushdown(p);
int mid=(l+r)>>1;
if(ll<=mid) update(ll,rr,lc,l,mid);
if(rr>mid) update(ll,rr,rc,mid+1,r);
}
void modify(int ll,int rr,int v,int p=1,int l=1,int r=n){
if(ll<=l&&r<=rr){tg[p]+=v;return;}
pushdown(p);
int mid=(l+r)>>1;
if(ll<=mid) modify(ll,rr,v,lc,l,mid);
if(rr>mid) modify(ll,rr,v,rc,mid+1,r);
}
ll query(int x,int p=1,int l=1,int r=n){
if(l==r) return per[p][0]+tg[p];
int mid=(l+r)>>1;
if(ex[p]){
if(x<=mid) return per[p][query(x,lc,l,mid)]+tg[p];
else return per[p][query(x,rc,mid+1,r)]+tg[p];
}
else{
if(x<=mid) return query(x,lc,l,mid)+tg[p];
else return query(x,rc,mid+1,r)+tg[p];
}
}
int main(){
n=read();q=read();
for(int i=1;i<=n;++i) a[i]=read();
build();
for(int i=1;i<=q;++i){
char cc;
do cc=getchar();while(cc<'A'||cc>'Z');
if(cc=='A'){
int l=read(),r=read(),v=read();
modify(l,r,v);
}
if(cc=='P'){
int l=read(),r=read();
update(l,r);
}
if(cc=='J') printf("%lld\n",query(read()));
}
return 0;
}