微信网站开发js框架,学校网站建设申请报告,wordpress 分类目录 seo,看片狂人看到集合和异或#xff0c;可以想到01tire(但是我没有想到)。 让后就可以对于每次插入和删除一个数#xff0c;都在01tire树上操作即可。让后记录一下到当前位(当然是从高位到低位啦)有相同前缀的数的个数。例如样例建图出来大概是这样的#xff1a; 可以看到从编号为2的点开… 看到集合和异或可以想到01tire(但是我没有想到)。 让后就可以对于每次插入和删除一个数都在01tire树上操作即可。让后记录一下到当前位(当然是从高位到低位啦)有相同前缀的数的个数。例如样例建图出来大概是这样的 可以看到从编号为2的点开始有分歧这个时候当前p的位为1l的位为0显然我们需要走右边才可能能使其答案小于l否则答案直接大于l了。让后到6的位置这个时候当前p的位为1l的位为1显然我们可以右儿子加上值为1的数的数量让后往左走因为左边虽然当前前缀于p异或之后和l相等但是可能也有小于l的数。也就是我们每次都要往与l当前位在p与当前值异或之后相等的位置走这样就可以解决问题啦。不过要注意如果当前位l为0的时候p与当前值异或之后一定要为0。
注这个地方为了方便根的编号要设置为1不能设置为0相应的idx初始值也要为1。因为在solve函数里搜索查询的数的时候我们不能保证每个访问到的结点都已经申请了空间当然也可以每个都申请但是麻烦还废空间。所以当访问的空间不存在的时候son [ p ] [ u ] 值为0如果你设置的根编号为0那么这个时候不就正好是根了嘛所以这里根不能设置为0。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N6000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int q;
int son[N][2],cnt[N],idx1;void insert(int x)
{int p1;for(int i30;i0;i--){cnt[p];int uxi1;if(!son[p][u]) son[p][u]idx;pson[p][u];}cnt[p];
}void delet(int x)
{int p1;for(int i30;i0;i--){cnt[p]--;int uxi1;if(!son[p][u]) son[p][u]idx;pson[p][u];}cnt[p]--;
}int solve(int x,int t)
{int p1,ans0;for(int i30;i0;i--){int uxi1;int sti1;if(us) anscnt[son[p][0]];if(us) anscnt[son[p][1]];if(!s) pson[p][u];else pson[p][u^1];}return ans;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d,q);while(q--){int op,p,l; scanf(%d%d,op,p);if(op1) insert(p);else if(op2) delet(p);else{scanf(%d,l);printf(%d\n,solve(p,l));}}return 0;
}
/**/
