题目大意

给你一个集合$S$，初始为空集，支持以下操作。

• 插入一个元素
• 给定 $x$，删除所有值为 $x$ 的元素
• 全局加
• 查询集合中有多少个元素满足其二进制的第 $k$ 位为 $1$，满足 $k\le 16$

$N\le 5\ast 10^5$

题解

先考虑对于一个 $k$ 时怎么做。

发现一个数 $x$ 二进制的第 $k$ 位为 $1$，等价于 $x\%2^{k+1}\ge 2^k$。我们考虑用一个数据结构来维护满足这个条件的元素数量，发现在支持加操作的情况下维护这个对于我这个菜逼来说是困难的。于是换个思路，我们不对数据结构进行修改，而是给他记录一个 $tag$，在查询的时候用 $tag$ 去修改对应查询的左右端点（$tag$ 为 $0$ 时 $l=2^k,r=2^{k+1}-1$）。在插入元素的时候也先用 $tag$ 对插入的元素进行修改。这个直接做就好。维护区间内元素数量可以使用权值线段树。代码很好写。

注意到 $k$ 范围很小，对每个 $k$ 单独开一个线段树也完全开得下。最终时间复杂度为 $O(16nlogV)$，实际比这小。

代码

#include<bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
using namespace std;

const int N=(1<<18)+5,K=18;
map<int,int> mp;

int n,laz;

struct segment_tree{
	int sum[N<<2],laz;
	
	void pushup(int p){
		sum[p]=sum[ls]+sum[rs];
	}
	
	void update(int p,int l,int r,int a,int b){
		if(l==r){
			sum[p]+=b;
			return;
		}
		int mid=l+r>>1;
		if(a<=mid) update(ls,l,mid,a,b);
		else update(rs,mid+1,r,a,b);
		pushup(p);
	}
	
	int query(int p,int l,int r,int a,int b){
		if(a<=l&&b>=r) return sum[p];
		int mid=l+r>>1,res=0;
		if(a<=mid) res+=query(ls,l,mid,a,b);
		if(b>mid) res+=query(rs,mid+1,r,a,b);
		return res;
	}
}t[K+5];

int main(){
	scanf("%d",&n);
	int heheda=0;
	for(int i=1,x;i<=n;i++){
		char opt[5];
		scanf("%s%d",opt,&x);
		if(opt[0]=='I'){
			for(int i=1,y,mod;i<=K;i++){
				mod=(1<<i);
				y=(x-t[i].laz+mod)%mod;
				t[i].update(1,1,mod,y+1,1);
			}
			mp[x-laz]++;
		}
		else if(opt[0]=='D'){
			int c=mp[x-laz];
			for(int i=1,y,mod;i<=K;i++){
				mod=(1<<i);
				y=(x-t[i].laz+mod)%mod;
				t[i].update(1,1,mod,y+1,-c);
			}
			mp[x-laz]=0;
		}
		else if(opt[0]=='A'){
			laz+=x;
			for(int i=1,mod;i<=K;i++){
				mod=(1<<i);
				t[i].laz=(t[i].laz+x%mod)%mod;
			}
		}
		else{
			int l=(1<<x),r=(1<<x+1)-1;
			int mod=(1<<x+1);
			l=(l-t[x+1].laz+mod)%mod;
			r=(r-t[x+1].laz+mod)%mod;
			if(l<=r) printf("%d\n",t[x+1].query(1,1,mod,l+1,r+1));
			else printf("%d\n",t[x+1].query(1,1,mod,1,r+1)+t[x+1].query(1,1,mod,l+1,mod));
		}
	}
	return 0;
}