浪潮集团的“超级大树” 2019 计蒜之道初赛第五场

有助于了解树的结构

Pro：
https://nanti.jisuanke.com/t/39451

Sol：
点的总数太大，无法存储

实际上使用过的点不多

1.对于未使用过的点，不进行创建
树上的遍历，求出被删除的点的总数

类似思想：线段树动态开点

对于每个点，从根节点到该点之间的所有的点被创建，当前树上的所有被创建的点的总数为D
D<=kQ
每次查询，添加或删除 logD
树上的遍历 D

map/unordered_map
红黑树
查找，添加或删除元素 log(D)

vector
元素从小到大排序
找到添加或删除的位置二分 lower_bound log(D)
然后添加或删除元素 log(D)
查找元素 log(D)

数组
添加或删除元素 D 最差情况是每次处理的都是编号最小(编号从小到大排序)的点，这里D较小，可以接受
查找元素 log(D)

2.对于使用过的点，放在vector/set(这里所有删除的点的编号都不同)/map等stl容器中，数组也行
对于每个删除的点，寻找祖先节点，看是否存在祖先节点被删去，如果是，这个删除的点不起作用(这个点的子树包含在祖先节点的子树内)

对于所有点，访问的点为从该点向上，直到第一个存在的点或根节点
重复的路径中的点没有被访问多次

每次查询，添加或删除 logD
寻找操作 D

对于M叉树的M为1，k<=1e18
不能使用上述方法
当M=1，树为链式结构，
只需记录被删除的点中编号最大的点即可
对于M>=1,k<=log(x+eps)/log(2) <64

way1

tree not building not existing point

vector

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10 #include <vector>
11 
12 const double eps=1e-8;
13 const ll inf=1e9;
14 const ll mod=1e9+7;
15 const int maxn=(5e2+10)*64;///
16 
17 struct node
18 {
19     ll nex[2],cond;
20 }tr[maxn];
21 
22 vector<ll> vec;
23 
24 ll cnt[100],m,maxdep,ind,pos;
25 
26 ll dfs(ll d,ll dep)
27 {
28     ll i;
29     if (tr[d].cond==1)
30         return cnt[maxdep-dep];
31     ll sum=0;
32     for (i=0;i<2;i++)
33         if (tr[d].nex[i])
34             sum+=dfs(tr[d].nex[i],dep+1);
35     return sum;
36 }
37 
38 void build(ll x)
39 {
40     if (x!=0)
41     {
42         build((x-1)/m);
43         if (!tr[pos].nex[(x-1)%m])
44             tr[pos].nex[(x-1)%m]=++ind;
45         pos=tr[pos].nex[(x-1)%m];
46     }
47 }
48 
49 int main()
50 {
51     ll q,opt,i,x;
52     scanf("%lld%lld%lld",&m,&maxdep,&q);
53     if (m!=1)
54     {
55         x=1;
56         for (i=1;i<=maxdep;i++)
57         {
58             cnt[i]=cnt[i-1]+x;
59             x*=m;
60         }
61     }
62 
63     while (q--)
64     {
65         scanf("%lld%lld",&opt,&x);
66         ///remove
67         if (opt==1)
68         {
69             if (m==1)
70                 vec.insert(lower_bound(vec.begin(),vec.end(),x) , x);
71             else
72             {
73                 pos=0;
74                 build(x);
75                 tr[pos].cond=1;
76             }
77         }
78         ///add
79         else
80         {
81             if (m==1)
82                 vec.erase(lower_bound(vec.begin(),vec.end(),x));
83             else
84             {
85                 pos=0;
86                 build(x);
87                 tr[pos].cond=0;
88             }
89         }
90         if (m==1)
91             printf("%lld
",vec.empty()?maxdep:vec[0]);
92         else
93             printf("%lld
",cnt[maxdep]-dfs(0,0));
94     }
95     return 0;
96 }

way2

visit ancestor

set

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10 #include <set>
11 
12 const double eps=1e-8;
13 const ll inf=1e18;
14 const ll mod=1e9+7;
15 const int sexn=(5e2+10)*64;///
16 
17 set<ll> se;
18 
19 ll cnt[100],m,maxdep;
20 
21 int main()
22 {
23     ll q,opt,i,x,xx,sum;
24     bool vis;
25     set<ll>::iterator j;
26     scanf("%lld%lld%lld",&m,&maxdep,&q);
27     if (m!=1)
28     {
29         x=1;
30         for (i=1;i<=maxdep;i++)
31         {
32             cnt[i]=cnt[i-1]+x;
33             x*=m;
34         }
35     }
36 
37     while (q--)
38     {
39         scanf("%lld%lld",&opt,&x);
40         ///remove
41         if (opt==1)
42             se.insert(x);
43         ///add
44         else
45             ///must has this element, not need to judge if xxx!=yyy.end()
46             ///oterwise if no this element, wrong!
47             se.erase(se.find(x));
48 
49         if (m==1)
50         {
51             if (se.empty())
52                 printf("%lld
",maxdep);
53             else
54             {
55                 x=inf;
56                 for (j=se.begin();j!=se.end();j++)
57                     x=min(x,*j);
58                 printf("%lld
",x);
59             }
60         }
61         else
62         {
63             sum=cnt[maxdep];
64             for (j=se.begin();j!=se.end();j++)
65             {
66                 x=*j;
67                 xx=x;
68                 vis=1;
69                 while (x)
70                 {
71                     x=(x-1)/m;
72                     if (se.find(x)!=se.end())
73                     {
74                         vis=0;
75                         break;
76                     }
77                 }
78                 if (vis)
79                     sum-=cnt[maxdep+1-(lower_bound(cnt,cnt+maxdep+1,xx+1)-cnt)];
80 
81             }
82             printf("%lld
",sum);
83         }
84     }
85     return 0;
86 }

map

这里用map，第二维就是没必要的。

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10 #include <map>
11 
12 const double eps=1e-8;
13 const ll inf=1e18;
14 const ll mod=1e9+7;
15 const int maxn=(5e2+10)*64;///
16 
17 map<ll,ll> ma;
18 
19 ll cnt[100],m,maxdep;
20 
21 int main()
22 {
23     ll q,opt,i,x,xx,sum;
24     bool vis;
25     map<ll,ll>::iterator j;
26     scanf("%lld%lld%lld",&m,&maxdep,&q);
27     if (m!=1)
28     {
29         x=1;
30         for (i=1;i<=maxdep;i++)
31         {
32             cnt[i]=cnt[i-1]+x;
33             x*=m;
34         }
35     }
36 
37     while (q--)
38     {
39         scanf("%lld%lld",&opt,&x);
40         ///remove
41         if (opt==1)
42             ma[x]=1;
43         ///add
44         else
45             ///must has this element, not need to judge if xxx!=yyy.end()
46             ///oterwise if no this element, wrong!
47             ma.erase(ma.find(x));
48         if (m==1)
49         {
50             if (ma.empty())
51                 printf("%lld
",maxdep);
52             else
53             {
54                 x=inf;
55                 for (j=ma.begin();j!=ma.end();j++)
56                     x=min(x,j->first);
57                 printf("%lld
",x);
58             }
59         }
60         else
61         {
62             sum=cnt[maxdep];
63             for (j=ma.begin();j!=ma.end();j++)
64             {
65                 x=j->first;
66                 xx=x;
67                 vis=1;
68                 while (x)
69                 {
70                     x=(x-1)/m;
71                     if (ma.find(x)!=ma.end())
72                     {
73                         vis=0;
74                         break;
75                     }
76                 }
77                 if (vis)
78                     sum-=cnt[maxdep+1-(lower_bound(cnt,cnt+maxdep+1,xx+1)-cnt)];
79 
80             }
81             printf("%lld
",sum);
82         }
83     }
84     return 0;
85 }

数组

还是用vector吧。。。

浪潮集团的“超级大树” 2019 计蒜之道 初赛 第五场

浪潮集团的“超级大树” 2019 计蒜之道初赛第五场