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

113 阅读 0 评论 75 点赞

我是靠谱客的博主妩媚钢笔，这篇文章主要介绍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 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 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 }