头部背景图片
Decaku 's Blog |
Decaku 's Blog |

主席树题集(不定时更新)

描述:

$ hduoj 5678 $
传送门


思路:

$要求子树的中位数,直接根据dfs序建出主席树,然后求区间 \\
第K大,观察到询问比答案种数多很多,所以先做预处理,double \\
的取模用fmod函数。 $


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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int M=40*maxn;
const int mod=1e9+7;

int T,n,m;
int Time,w[maxn],cnt,head[maxn],in[maxn],out[maxn];
int a[maxn],t[maxn],rt[maxn],lson[M],rson[M],c[M],tot,len;
double ans[maxn];

void ini_hash()
{
for(int i=1; i<=n; i++)
t[i]=a[i];
sort(t+1,t+n+1);
len=unique(t+1,t+n+1)-t-1;
}

int build(int l,int r)
{
int root=tot++;
c[root]=0;
if(l!=r)
{
int mid=(l+r)>>1;
lson[root]=build(l,mid);
rson[root]=build(mid+1,r);
}
return root;
}

int Hash(int x)
{
return lower_bound(t+1,t+len+1,x)-t;
}

int update(int root,int pos,int val)
{
int newroot=tot++,tmp=newroot;
c[newroot]=c[root]+val;
int l=1,r=len;
while(l<r)
{
int mid=l+r>>1;
if(pos<=mid)
{
lson[newroot]=tot++;
rson[newroot]=rson[root];
newroot=lson[newroot];
root=lson[root];
r=mid;
}
else
{
rson[newroot]=tot++;
lson[newroot]=lson[root];
newroot=rson[newroot];
root=rson[root];
l=mid+1;
}
c[newroot]=c[root]+val;
}
return tmp;
}

int query(int u,int v,int k)
{
int l=1,r=len;
while(l<r)
{
int mid=l+r>>1;
if(c[lson[u]]-c[lson[v]]>=k)
{
r=mid;
u=lson[u];
v=lson[v];
}
else
{
l=mid+1;
k-=c[lson[u]]-c[lson[v]];
u=rson[u];
v=rson[v];
}
}
return l;
}
struct Edge
{
int to,nex;
} e[maxn<<1];

void add_edge(int u,int v)
{
e[++cnt].nex=head[u];
e[cnt].to=v;
head[u]=cnt;

e[++cnt].nex=head[v];
e[cnt].to=u;
head[v]=cnt;
}

void ini()
{
cnt=-1;
tot=Time=0;
memset(head,-1,sizeof(head));
}

void dfs(int u,int f)
{
in[u]=++Time;
for(int i=head[u]; ~i; i=e[i].nex)
{
int v=e[i].to;
if(v==f)
continue;
dfs(v,u);
}
out[u]=Time;
}

int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&m);
ini();
for(int i=1; i<=n; i++)
scanf("%d",&w[i]);
for(int i=1; i<n; i++)
{
int u,v;
scanf("%d %d",&u,&v);
add_edge(u,v);
}
dfs(1,0);
for(int i=1; i<=n; i++)
a[in[i]]=w[i];

ini_hash();
rt[n+1]=build(1,len);
for(int i=n;i;i--)
{
int pos=Hash(a[i]);
rt[i]=update(rt[i+1],pos,1);
}

for(int i=1; i<=n; i++)
{
int K=out[i]-in[i]+1;
if(K&1)
ans[i]=1.0*t[query(rt[in[i]],rt[out[i]+1],K/2+1)];
else
ans[i]=(1.0*t[query(rt[in[i]],rt[out[i]+1],K/2)]+1.0*t[query(rt[in[i]],rt[out[i]+1],K/2+1)])/2;
}
double sum=0;

while(m--)
{
int q;
scanf("%d",&q);
sum=fmod(sum*10+ans[q],1.0*mod);
}
printf("%.1f\n",sum);
}
}

描述:

$ hduoj 6504 $
传送门


思路:

$根据dfs序建出主席树,然后枚举删的边,统计子树里元素种 \\
类数,统计树另一边里元素种类数把序列倍增一份即可。 $


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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int M=80*maxn;
int n,head[maxn],cnt,w[maxn];
int Time,in[maxn],out[maxn];
int a[maxn<<1],T[maxn<<1],lson[M],rson[M],c[M],tot;
int build(int l,int r)
{
int root=tot++;
c[root]=0;
if(l!=r)
{
int mid=l+r>>1;
lson[root]=build(l,mid);
rson[root]=build(mid+1,r);
}
return root;
}

int update(int root,int pos,int val)
{
int newroot=tot++,tmp=newroot;
c[newroot]=c[root]+val;
int l=1,r=2*n;
while(l<r)
{
int mid=l+r>>1;
if(pos<=mid)
{
lson[newroot]=tot++;
rson[newroot]=rson[root];
newroot=lson[newroot];
root=lson[root];
r=mid;
}
else
{
rson[newroot]=tot++;
lson[newroot]=lson[root];
newroot=rson[newroot];
root=rson[root];
l=mid+1;
}
c[newroot]=c[root]+val;
}
return tmp;
}
int query(int root,int pos)
{
int ret=0;
int l=1,r=2*n;
while(pos<r)
{
int mid=l+r>>1;
if(pos<=mid)
{
r=mid;
root=lson[root];
}
else
{
ret+=c[lson[root]];
root=rson[root];
l=mid+1;
}
}
return ret+c[root];
}


struct Edge
{
int to,nex;
} e[maxn<<1];

void add_edge(int u,int v)
{
e[++cnt].nex=head[u];
e[cnt].to=v;
head[u]=cnt;

e[++cnt].nex=head[v];
e[cnt].to=u;
head[v]=cnt;
}
void ini()
{
cnt=-1;
Time=0;
tot=0;
memset(head,-1,sizeof(head));
}

void dfs(int u,int f)
{
in[u]=++Time;
for(int i=head[u]; ~i; i=e[i].nex)
{
int v=e[i].to;
if(v==f)
continue;
dfs(v,u);
}
out[u]=Time;
}


int main()
{
while(~scanf("%d",&n))
{
ini();

for(int i=2; i<=n; i++)
{
int p;
scanf("%d",&p);
add_edge(i,p);
}
for(int i=1; i<=n; i++)
scanf("%d",&w[i]);
dfs(1,0);
for(int i=1; i<=n; i++)
a[in[i]]=w[i],a[in[i]+n]=w[i];

T[2*n+1]=build(1,n*2);
map<int,int>mp;
for(int i=2*n; i>=1; i--)
{
if(mp.find(a[i])==mp.end())
{
T[i]=update(T[i+1],i,1);
}
else
{
int tmp=update(T[i+1],mp[a[i]],-1);
T[i]=update(tmp,i,1);
}
mp[a[i]]=i;
}


int ans=-1;
for(int i=2; i<=n; i++)
{
int l=in[i],r=out[i];
int tem=query(T[l],r)+query(T[r+1],n+l-1);
ans=max(ans,tem);
}
printf("%d\n",ans);
}
}
avatar Decaku 很菜但也很想carry