P8969 题解

dAniel_lele · 2024-04-25 23:09:52 · 题解

注意到一个区间要么没有 P 操作，要么只会有至多 \log V 种数。

考虑线段树，对于每个节点维护 add 表示增加量的懒标记，tp 表示是否有过 P 操作，b_{i=0\sim \log V} 表示 \operatorname{popcount}(x+add)=i 时，这个节点的第一个 P 以后的懒标记会将 x 变为哪个数。

懒标记下传时需要优先判断两边的 tp 是 0 还是 1。具体细节留给读者自行推倒可以见代码。

总复杂度 O(n\log n\log V)。

#include <bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
using namespace std;
int a[1000005];
struct node{
    int tp,add,b[51];
};
node addx(node t,int x){//A 操作，将一个区间加上 x
    if(t.tp==0){
        t.add+=x;
        return t;
    }
    for(int i=0;i<=50;i++) t.b[i]+=x;
    return t;
}
node addy(node t){//P 操作，将一个区间变为 popcount
    if(t.tp==0){
        t.tp=1;
        for(int i=0;i<=50;i++) t.b[i]=i;
        return t;
    }
    for(int i=0;i<=50;i++) t.b[i]=__builtin_popcountll(t.b[i]);
    return t;
}
node merge(node x,node y){//pushdown 时将两个 node 合并
    if(y.tp==0){
        return addx(x,y.add);
    }
    if(x.tp==0){
        y.add+=x.add;
        return y;
    }
    for(int i=0;i<=50;i++) x.b[i]=y.b[__builtin_popcountll(x.b[i]+y.add)];
    return x;
}
struct sgt{
    node f[1200005];
    void pushdown(int i){
        f[i*2]=merge(f[i*2],f[i]);
        f[i*2+1]=merge(f[i*2+1],f[i]);
        f[i].add=f[i].tp=0;
    }
    void change1(int i,int l,int r,int ql,int qr,int cg){
        if(ql<=l&&r<=qr){
            f[i]=addx(f[i],cg);
            return ;
        }
        pushdown(i);
        if(ql<=mid) change1(i*2,l,mid,ql,qr,cg);
        if(qr>mid) change1(i*2+1,mid+1,r,ql,qr,cg);
    }
    void change2(int i,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr){
            f[i]=addy(f[i]);
            return ;
        }
        pushdown(i);
        if(ql<=mid) change2(i*2,l,mid,ql,qr);
        if(qr>mid) change2(i*2+1,mid+1,r,ql,qr);
    }
    node qry(int i,int l,int r,int pos){
        if(l==r) return f[i];
        pushdown(i);
        if(pos<=mid) return qry(i*2,l,mid,pos);
        return qry(i*2+1,mid+1,r,pos);
    }
}tree;
signed main(){
    int n,q; cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(q--){
        char c; cin>>c;
        if(c=='J'){
            int p; cin>>p;
            node tmp=tree.qry(1,1,n,p);
            if(tmp.tp==0) cout<<a[p]+tmp.add<<"\n";
            else cout<<tmp.b[__builtin_popcountll(a[p]+tmp.add)]<<"\n";
        }
        else if(c=='A'){
            int l,r,x; cin>>l>>r>>x;
            tree.change1(1,1,n,l,r,x);
        }
        else{
            int l,r; cin>>l>>r;
            tree.change2(1,1,n,l,r);
        }
    }
    return 0;
}