思路如下：

用线段树维护区间的值，并建立一个标记用于标记区间的所有值是否相同，在区间 popcount 时如果发现标记成立则只需要对区间进行区间修改即可。

因为在 popcount 之后区间最多有 $\log V$ 个值，在随机数据下应该过得去，但实际情况是 (请忽略背景

蒟蒻不知道为什么会 WA

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=333333;
typedef long long ll;

char op[2];
int in1,in2,in3,inp[N];
int n,q;

int popcount(ll n){
    int cnt=0;
    while(n>INT_MAX){if(n&1) cnt++;n>>=1;}
    return cnt+__builtin_popcount(n);
}

int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||'9'<ch){ch=getchar();}
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x;
}

void write(ll x){
    ll k=x/10;
    if(k) write(k);
    putchar(x-(k<<1)-(k<<3)+'0');
    return ;
}

struct STn{int l,r;ll t,num,t3;int is,t2;};
struct ST{
    STn a[N<<2];
    void push_up(int p){
        if(a[p<<1].is&&a[p<<1|1].is&&(a[p<<1].num==a[p<<1|1].num)){
            a[p].is=1;a[p].num=a[p<<1].num;
        }
        return ;
    }
    void add_t(int p,ll k){
        a[p].t+=k;a[p].num+=k;return ;
    }
    void change_t(int p,ll k){
        a[p].t=0;a[p].t2=1;a[p].t3=k;
        a[p].num=k;return ;
    }
    void push_down(int p){
        if(a[p].t2){
            change_t(p<<1,a[p].t3);
            change_t(p<<1|1,a[p].t3);
            a[p].t2=a[p].t3=0;
        }
        if(a[p].t){
            add_t(p<<1,a[p].t);
            add_t(p<<1|1,a[p].t);
            a[p].t=0;
        }
    }
    void build(int p,int l,int r){
        a[p].l=l;a[p].r=r;a[p].t=a[p].t2=a[p].t3=0;
        if(a[p].l==a[p].r){a[p].num=inp[a[p].l];a[p].is=1;return ;}
        int mid=(a[p].l+a[p].r)>>1;
        build(p<<1,l,mid);build(p<<1|1,mid+1,r);
        push_up(p);return ;
    }
    ll ask(int p,int x){
        if(a[p].l==a[p].r) return a[p].num;
        push_down(p);int mid=(a[p].l+a[p].r)>>1;
        return (x<=mid)?ask(p<<1,x):ask(p<<1|1,x);
    }
    void add(int p,int l,int r,int k){
        if(l<=a[p].l&&a[p].r<=r){add_t(p,k);return ;}
        int mid=(a[p].l+a[p].r)>>1;push_down(p);
        if(l<=mid) add(p<<1,l,r,k);
        if(r>mid) add(p<<1|1,l,r,k);
        push_up(p);return ;
    }
    void pop(int p,int l,int r){
        if(a[p].l==a[p].r){
            a[p].num=popcount(a[p].num);
            return ;
        }
        if(l<=a[p].l&&a[p].r<=r&&a[p].is){
            change_t(p,popcount(a[p].num));
            return ;
        }
        push_down(p);
        int mid=(a[p].l+a[p].r)>>1;
        if(l<=mid) pop(p<<1,l,r);
        if(r>mid) pop(p<<1|1,l,r);
        push_up(p);return ;
    }
}tree;

int main(){
    freopen("the.in","r",stdin);
    freopen("the.out","w",stdout);
    n=read();q=read();
    for(int i=1;i<=n;i++) inp[i]=read();
    tree.build(1,1,n);
    while(q--){
        scanf("%s",op+1);
        if(op[1]=='A'){
            in1=read();in2=read();in3=read();
            tree.add(1,in1,in2,in3);
        }
        if(op[1]=='P'){
            in1=read();in2=read();
            tree.pop(1,in1,in2);
        }
        if(op[1]=='J'){
            in1=read();
            write(tree.ask(1,in1));putchar('\n');
        }
    }
    return 0;
}

还有一个想法，在合并时如果发现左右两子区间都有标记，并且左右两区间的值的 popcount 相同，那么这个区间的标记也成立，因为在一次 popcount 后就相同了，这样的做法正确性应该没错，应该不会慢太多（复杂度至多乘个 $\log n$，但因为 popcount 时不需要继续递归，所以比这要少），但实测中所有点全 T。

就是把 pushup 函数换成下面的：

void push_up(int p){
        if(a[p<<1].is&&a[p<<1|1].is&&(a[p<<1].num==a[p<<1|1].num||popcount(a[p<<1].num)==popcount(a[p<<1|1].num))){
            a[p].is=1;a[p].num=a[p<<1].num;
        }
        return ;
    }

这又是为什么呢？