提供一种需要卡常的分块写法。

首先看到 \(\operatorname{popcount}\) 操作，便可以自然而然的想到在值域上做文章。

首先因为 \(\operatorname{popcount} \leq \log x\)。

所以可以想到对于一个序列来说，进行一次 \(\operatorname{popcount}\) 操作后至多有 \(\log V\) 个不同的数字。

并且在对这个区间进行全局操作时不同数的数量不增。

因此考虑分块。

块内最开始用 \(tag\) 记录加法操作。

对于块内如果有整块 \(\operatorname{popcount}\) 操作则转换成记录每个值都变成了什么。

由于所有值不大于 \(\log V\)，所以量级是 \(\log V\) 的。

类似于阈值分治的思想，不同类型的数据不同处理。

这样做复杂度是 \(O(q \sqrt n \log V)\)。

会超时。

不过还能改进。

这样做在保持分块的情况下不会写线段树的标记只能改进 \(\operatorname{popcount}\)。

但是我们可以用自带的函数。

这样写：

inline int popcount(int n){
    return __builtin_popcountll(n);
}

然后考虑一些优化：

1. 记录块内最大值，若为 \(1\) 则跳过 \(\operatorname{popcount}\) 操作。

2. 每次 \(\operatorname{popcount}\) 操作后去重降低后续操作复杂度。

3. 加法操作全部堆到 \(tag\) 里，使得加法操作复杂度稳定在 \(O(\sqrt n)\)。

如此再加上一定卡常就可以过了。

不过这样为什么可以过呢？

因为这个函数内部用自带的表以及二分实现，虽然都是 \(\log\) 量级，但是二分理论上很难跑满。

所以复杂度还是 \(O(q \sqrt n \log V)\)，但是常数极小。

以下是比较丑的代码，各位大佬轻喷。

#include<bits/stdc++.h>
#define int long long
#define max(x,y) (x>y?x:y)
using namespace std;
const int maxn = 3e5+1000;
const int maxw = 1000;
int B;
int a[maxn];
int sum;//块的数量
inline int popcount(int n){
    return __builtin_popcountll(n);
}
class block{
    public:
    int l,r;//块的起止位置
    int flag;//是否已经被 popcount 过
    pair<int,int> chifan[maxw];
    int tot;
    //popcount 后块内不同元素数量至多 50 个，所以暴力记录查询
    int tag;//加法标记
    void init();//初始化
    void maintain();//散块重构
    void change();//popcount 后转换记录方式
    void add(int x);
    void Pop();
}b[maxw];
inline void block::init(){
    flag=0;
    tot=0;
    tag=0;
}
void block::maintain(){
    if(flag==0){
        for(int i=l;i<=r;++i) a[i]=a[i]+tag;
        tag=0;
    }
    else{
        map<int,int> lwx;
        for(int i=1;i<=tot;i++) lwx[chifan[i].first]=chifan[i].second+tag;
        for(int i=l;i<=r;++i)
        {
            a[i]=lwx[a[i]];
        }
    }
    for(int i=1;i<=tot;++i) chifan[i].first=chifan[i].second=0;
    flag=tot=tag=0;
}
void block::change(){
    for(int i=l;i<=r;++i) a[i]=popcount(a[i]+tag);
    tag=0;
    flag=1;
    map<int,int> use;
    for(int i=l;i<=r;++i){
        int op=0;
        if(use[a[i]]==0)
            chifan[++tot]=make_pair(a[i],a[i]),use[a[i]]=1;
    }
}
inline void block::add(int x){
    tag+=x;
}
void block::Pop(){
    if(flag==0) change();
    else{
        int Maxval=0;
        for(int i=1;i<=tot;i++) Maxval=max(Maxval,chifan[i].second+tag);
        if(Maxval==1) return ;
        for(int i=1;i<=tot;++i)
            chifan[i].second=popcount(chifan[i].second+tag);
        int f=0;
        for(int i=2;i<=tot;i++)
            if(chifan[i].first!=chifan[i-1].first) f=1;
        if(f==0)
        {
            for(int i=2;i<=tot;i++) chifan[i].first=chifan[i].second=0;
            tot=1;
        }
    }
    tag=0;
}
void changeA(int l,int r,int x){
    int bl=l/B+1;
    if(l-l/B*B==0) bl--;
    int br=r/B+1;
    if(r-r/B*B==0) br--;
    for(int i=bl+1;i<br;++i)
        b[i].add(x);

    if(bl!=br){
        b[bl].maintain();
        b[br].maintain();
        for(int i=l;i<=b[bl].r;++i) a[i]+=x;
        for(int i=b[br].l;i<=r;++i) a[i]+=x;
    }
    else{
        b[bl].maintain();
        for(int i=l;i<=r;i++) a[i]+=x;
    }
}
void changeB(int l,int r){
    int bl=l/B+1;
    if(l-l/B*B==0) bl--;
    int br=r/B+1;
    if(r-r/B*B==0) br--;
    for(int i=bl+1;i<br;++i)
        b[i].Pop();
    
    if(bl!=br){
        b[bl].maintain();
        b[br].maintain();
        for(int i=l;i<=b[bl].r;++i) a[i]=popcount(a[i]);
        for(int i=b[br].l;i<=r;++i) a[i]=popcount(a[i]);
    }
    else{
        b[bl].maintain();
        for(int i=l;i<=r;++i) a[i]=popcount(a[i]);
    }
}
int question(int x){
    int pos=x/B+1;
    if(x-x/B*B==0) pos--;
    if(b[pos].flag==0) return a[x]+b[pos].tag;
    else{
        for(int j=1;j<=b[pos].tot;++j)
            if(a[x]==b[pos].chifan[j].first) return b[pos].chifan[j].second+b[pos].tag;
    }
}
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}

int n,q;
signed main(){
    n=read();
    q=read();
    B=sqrt(n);
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=1;i<=n;i=i+B){
        b[++sum].l=i;
        b[sum].r=min(n,i+B-1);
        b[sum].init();
    }
    for(int i=1;i<=q;i++){
        char op;
        op=getchar();
        while(op<'A'||op>'Z')
        op=getchar();
        if(op=='A'){
            int l,r,x;
           l=read();
           r=read();
           x=read();
            changeA(l,r,x);
        }
        else if(op=='P'){
            int l,r;
            l=read();
            r=read();
            changeB(l,r);
        }
        else{
            int x;
            x=read();
            write(question(x));
            putchar('\n');
        }
    }
    return 0;
}