【日常小测】subset

题目传送门:http://oi.cyo.ng/wp-content/uploads/2016/11/20161104.pdf

这题如果是亦或之类的,大家应该都会做吧!
但这题是&的话,有些时候就需要同时进入左右子树了QAQ
这个我们不难想到:http://uoj.ac/problem/176
简直一毛一样有木有?

然而这么做有一个问题:这货只能用Fat Node的持久化形式
这样的话,在最后复制左右子树的时候,复杂度还是不对啊QAQ
所以这样似乎没法做了QAQ
如果可以的话,可不可以给我讲一讲? _(:з」∠)_

还是来说一说std吧:
将二进制下前八位作为数组的一维下标
将二进制的后八位作为数组的二维下标
然后在查询时暴力第二维,修改时暴力第一维
时间复杂度O(n*2^8)

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300;
const int MX = 256;

int f[N][N],n;
char pat[10];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void modify(int w, int delta) {
	for (int i=0;i<MX;i++) {
		if ((i&w)==(w&255)) {
			f[i][w>>8] += delta;
		}
	}
}
 
inline int query(int w) {
	int ret = 0;
	for (int i=0,sta=w>>8;i<MX;i++) {
		if ((i&sta)==i) {
			ret += f[w&255][i];
		}
	}
	return ret;
} 
 
int main(){
	freopen("subset.in","r",stdin);
	freopen("subset.out","w",stdout);
	n = read();
	for (int i=1;i<=n;i++) {
		scanf("%s",pat+1);
		if (pat[1] == 'a') modify(read(),1);
		else if (pat[1]=='d') modify(read(),-1);
		else printf("%d\n",query(read()));	
	}
	return 0;
}