题目传送门: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; }