Liveddd's Blog

愛にできることはまだあるかい

P3571 [POI2014]SUP-Supercomputer

可以用堆做到 O(nlogn) ,也可以用更加优秀的斜率优化实现 O(n)

题目链接

考虑按照 dep 分层。记 cntdep 表示深度为 dep 的点数。考虑从大到小枚举 k,将对于每个 k 的最优解都求出来。

k 足够大时,显然一次能且仅能选择同一层的点,即 ansk=maxdepi。当某一时刻,cnti>k,那么我们无法在一次内选择完第 i 层的点,需要将其中 cntik 个点挪到下一层选取。

题目中限制了拥有父子关系的两个点无法同时选择,我们需要证明只需要将剩下的点向下挪动一层就能够得到合法解。

假设此时 cnti1k

我们需要在第 i 次和第 i+1 共选取 2k 个点其中第 i 层选取 cnti 个,第 i+1 层选取 2kcnti 个点。

1. cnti+1<2kcnti:第 i+1 天未取满 k 个点,并不影响结果。

2. cnti+1>2kcnti:将第 i+1 层多余的点挪向第 i+2 层,这显然是一个相同的子问题。

3. cnti>2k:将第 i 层多余的点和第 i+1 层所有点挪向第 i+2 层,这显然又是一个相同的子问题。

而这 2k 个点拥有父子关系的点对数 <k,故一定能找到合法方案。

也可以感性理解,既然当 k>k 时,被选中的点可以在当层选择,那么挪到下一层就更容易有合法方案了。

由上面的结论我们可以得到,我们始终可以把操作一次多余的点挪向下一层,保证每层的点数 k,最多有 n 层。

这个时候暴力维护是不行的,因为我们并不关心多出来的点来自哪一层,我们尝试将多层放在一起合并后维护。

我们于是就维护的就是一段区间 [l,r],表示连续 rl+1 天仅选取第 [l,r] 层的点,且一定取完,即 i=lrcnti(rl+1)×k

故我们只需要用维护区间,每次将堆顶不合法区间取出,向下合并即可。

时间复杂度 O(nlogn) ,比隔壁斜率优化 O(n) 要慢,但也算提供新的思路吧。

Code
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
#include<iostream>
#include<cstdio>
#include<queue>
#include<bitset>
#define ll long long
using namespace std;
const int N=1e6+10;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1&...x1)
{
read(x),read(x1...);
}
struct Node
{
int l,r,cnt;
inline bool operator<(const Node &rhs)const {
return (ll)cnt*(rhs.r-rhs.l+1)<(ll)rhs.cnt*(r-l+1);
}
inline bool check(int k)const {
return (ll)(r-l+1)*k<cnt;
}
};
int n,m;
int query[N],ans[N];
int cnt[N],dep[N];
int ed[N];
bool vis[N];
priority_queue<Node>q;
int main()
{
read(n,m);
for(int i=1;i<=m;i++)
read(query[i]);
++cnt[dep[1]=1];
int res=1;
for(int i=2;i<=n;i++)
{
int fa;
read(fa);
++cnt[dep[i]=dep[fa]+1];
res=max(res,dep[i]);
}
for(int i=1;i<=n;i++)
{
ed[i]=i;
q.push((Node){i,i,cnt[i]});
}
for(int k=1e6;k>=1;k--)
{
while(q.top().check(k))
{
Node x=q.top();
q.pop();
if(vis[x.l])
continue;
vis[x.r+1]=1;
res=max(res,ed[x.l]=ed[x.r+1]);
cnt[x.l]+=cnt[x.r+1];
q.push((Node){x.l,ed[x.l],cnt[x.l]});
}
ans[k]=res;
}
for(int i=1;i<=m;i++)
printf("%d ",ans[query[i]]);
return 0;
}

Gitalk 加载中 ...