提供一种需要卡常的分块写法。
首先看到 \(\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\) 则跳过 \(\operatorname{popcount}\) 操作。
-
每次 \(\operatorname{popcount}\) 操作后去重降低后续操作复杂度。
-
加法操作全部堆到 \(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;
}