Educational Codeforces Round 23 E. Choosing The Commander 字典树

103 阅读 0 评论 68 点赞

我是靠谱客的博主妩媚钢笔，这篇文章主要介绍Educational Codeforces Round 23 E. Choosing The Commander 字典树，现在分享给大家，希望可以做个参考。

题目连接：E. Choosing The Commander

题意：士兵有个值，指挥官有两个p,l三种操作，第一种添加一个值为p的士兵，第二种删除一个值为p的士兵，（士兵pi只会尊敬pi^p<l的指挥官）第三种询问现有的士兵中有多少个尊敬这个指挥官。

题解：我们把士兵建一棵0，1字典树，然后在询问的时候，根据p,l,dfs整棵字典树，在加上满足条件的值，复杂度0（nlogp）

 1 #include<bits/stdc++.h>
 2 #include<set>
 3 #include<cstdio>
 4 #include<iomanip>
 5 #include<iostream>
 6 #include<string>
 7 #include<cstring>
 8 #include<algorithm>
 9 #define pb push_back
10 #define ll long long
11 #define fi first
12 #define se second
13 #define PI 3.14159265
14 #define ls l,m,rt<<1
15 #define rs m+1,r,rt<<1|1
16 #define eps 1e-7
17 #define pii pair<int,int>
18 typedef unsigned long long ull;
19 const int mod=1e3+5;
20 const ll inf=0x3f3f3f3f3f3f3f;
21 const int maxn=1e5+5;
22 using namespace std;
23 int n,s;
24 struct tire//字典树
25 {
26
int sz,rt,now;
27
struct node
28 
{
29
int nxt[2],cnt;
30
}st[maxn*32];
31
int node()//构建新节点
32 
{
33
st[sz].nxt[0]=st[sz].nxt[1]=-1;st[sz].cnt=0;
34
sz++;return sz-1;
35 
}
36
void init()
37 
{
38
sz=0;
39
rt=node();
40 
}
41
void ins(int x)//插入
42 
{
43
now=rt;st[now].cnt++;
44
for( int i=31;i>=0;i--)
45 
{
46
int id=(x>>i)&1;
47
if(st[now].nxt[id]==-1)st[now].nxt[id]=node();
48
now=st[now].nxt[id];st[now].cnt++;
49 
}
50 
}
51
void erase(int x)
52 
{
53
now=rt; st[now].cnt--;
54
for(int i=31;i>=0;i--)
55 
{
56
int id=(x>>i)&1;
57
now=st[now].nxt[id];st[now].cnt--;
58 
}
59 
}
60
int ask(int x,int l,int v,int len=31)
61 
{
62
if(v==-1||len<0)return 0;
63
int pp=(x&(1<<len))>0;
64
if(l&(1<<len)){
65
return (st[v].nxt[pp]==-1?0:st[st[v].nxt[pp]].cnt)+ask(x,l,st[v].nxt[pp^1],len-1);
66 
}
67
else return ask(x,l,st[v].nxt[pp],len-1);
68 
}
69 }ac;
70 int main()
71 {
72
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
73 
ac.init();
74
cin>>n;
75
while(n--)
76 
{
77
int op,p,l;
78
cin>>op>>p;
79
if(op==1)ac.ins(p);
80
else if(op==2)ac.erase(p);
81
else cin>>l,cout<<ac.ask(p,l,ac.rt)<<endl;
82 
}
83
return 0;
84 }