P6412 [COCI2008-2009#3] BST题解

Naro_Ahgnay · 2021-12-04 17:43:27 · 题解

严格 \Theta(n) 算法

题目描述

现在有一个序列 a，将序列中的元素依次放进一个 BST 里，求 BST 中插入函数的执行次数。

注意：第一个数已经作为 BST 的根。

思路

对于每一个答案，分析后可以发现，每个数一定是在已经加入进去的数中小于它的最大值和大于它的最小值的两个数之间。举个例子：

对于数 x，在每次查找小于 x 的最大值和大于 x 的最小值时，可以用set、线段树等数据结构。而这些结构的时间复杂度为 \Theta(nlogn)。然而，还有一种叫做链表的数据结构，可以使时间复杂度降至严格 \Theta(n)。

步骤

step1

首先创造一个链表，链表有两个值，一个是 las,指向该位置的前一个位置，一个是 nxt,指向该位置的后一个位置。

step2

对于输入的 a_i,我们倒着向前遍历。对于每一个遍历到的数 a_i，此时我们将 a_i 在链表中的前一个数 list(a)_{las} 和后一个数 list(a)_{nxt} 存下来，然后删除 list(a)。下面图演示（假设现在删的数是3）：

step3

从1到n正序遍历，对于每一个遍历到的数 a_i, dep(a_i)=max {链表中的前一个数，链表中的后一个数}。用 sum 保存 dep(a_i) 的和，直接输出就行。

code

#include<bits/stdc++.h>
using namespace std;
struct List{
    int las,nxt;
}li[300011];
int n;
long long sum;
pair<int,int> b[300001];
int a[300001],dep[300001];
int main()
{
//  freopen("P6412.in","r",stdin);
//  freopen("P6412.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        li[i].nxt=i+1,li[i].las=i-1;
    }
    li[0].nxt=1,li[n+1].las=n;
    for(int i=n;i;i--)
    {
        b[a[i]].first=li[a[i]].las,b[a[i]].second=li[a[i]].nxt;
        li[li[a[i]].las].nxt=li[a[i]].nxt,li[li[a[i]].nxt].las=li[a[i]].las;
    }
    dep[a[1]]=0;puts("0");
    for(int i=2;i<=n;i++)
    {
        dep[a[i]]=max(dep[b[a[i]].first],dep[b[a[i]].second])+1;
        sum+=dep[a[i]];
        printf("%lld\n",sum);
    }
    return 0;
}