问题描述:

我们定义某天的最小波动值为$min \lbrace |$该天以前某一天的营业额$-$该天营业额$| \rbrace $

第一天的最小波动值为第一天的营业额

你的任务是编写一个程序帮助Tiger来计算这一个值:每一天的最小波动值之和。

输入:

第一行为正整数$n(n<=32767)$,表示该公司从成立一直到现在的天数,接下来的$n$行每行有一个整数$ai(|ai|<=1000000)$,表示第$i$天公司的营业额,可能存在负数

输出:

仅一个整数,即每一天的的最小波动值之和(结果小于$2^{31}$)

思路:

我们就是要实现 动态插点,找前驱和后继 这三种操作。首先平衡树肯定是能够做到的,于是就码了一发Splay。

然后其实权值线段树也可以做到。我们先将这些值离散化,每个值对应一个叶子节点。于是我们对于每一个节点维护区间内最左边和最右边的位置就好了。

代码:

Splay代码:

#include <bits/stdc++.h>
#define MAXN 100005
#define INF 1e9
using namespace std;

int n, m, x, root, tot, ans;

struct Node
{
    int son[2], fa, val, size, tag;
    void init(int x, int y)
    {
        son[0]=son[1]=0;
        size=1; val=x; fa=y;
    }
} t[MAXN];

void up(int x)
{
    t[x].size=t[t[x].son[0]].size+t[t[x].son[1]].size+1;
}

void rotate(int x)
{
    int y=t[x].fa, z=t[y].fa;
    int k1=t[y].son[1]==x, k2=t[z].son[1]==y;
    t[z].son[k2]=x; t[x].fa=z;
    t[y].son[k1]=t[x].son[k1^1]; t[t[x].son[k1^1]].fa=y;
    t[x].son[k1^1]=y; t[y].fa=x;
    up(y); up(x);
}

void splay(int x, int k)
{
    while(t[x].fa!=k)
    {
        int y=t[x].fa, z=t[y].fa;
        if(z!=k)
        {
            if((t[z].son[1]==y)^(t[y].son[1]==x)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if(k==0) root=x;
}

int findnext(int k, int op)
{
    int x=root;
    x=t[x].son[op];
    while(t[x].son[op^1]) x=t[x].son[op^1];
    return x;
}

void insert(int k)
{
    int fa=0, x=root;
    while(x) fa=x, x=t[x].son[k>t[x].val];
    x=++tot;
    if(fa) t[fa].son[k>t[fa].val]=x;
    t[x].init(k, fa);
    splay(x, 0);
}

int main()
{
    insert(-INF);
    insert(INF);
    scanf("%d%d", &n, &x);
    insert(x);
    ans+=x;
    for(int i=2; i<=n; i++)
    {
        scanf("%d", &x);
        insert(x);
        int y=t[findnext(x, 0)].val;
        int z=t[findnext(x, 1)].val;
        ans+=min(x-y, z-x);
    }
    printf("%d\n", ans);
}

权值线段树代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 33000
#define mid (l+r>>1)
#define ls root<<1
#define rs root<<1|1
#define INF 1e9
using namespace std;

int n, ans, a[MAXN], b[MAXN], vis[MAXN], maxpos[MAXN*4], minpos[MAXN*4];

void up(int root)
{
    maxpos[root]=max(maxpos[ls], maxpos[rs]);
    minpos[root]=min(minpos[ls], minpos[rs]);
}

void update(int root, int l, int r, int x)
{
    if(l>x || r<x) return ;
    if(l==r) {maxpos[root]=minpos[root]=l; return;}
    update(ls, l, mid, x);
    update(rs, mid+1, r, x);
    up(root);
}

int queryl(int root, int l, int r, int x, int y)
{
    if(l>y || r<x) return 0;
    if(l>=x && r<=y) return maxpos[root];
    return max(queryl(ls, l, mid, x, y), queryl(rs, mid+1, r, x, y));
}

int queryr(int root, int l, int r, int x, int y)
{
    if(l>y || r<x) return n+1;
    if(l>=x && r<=y) return minpos[root];
    return min(queryr(ls, l, mid, x, y), queryr(rs, mid+1, r, x, y));
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        b[i]=a[i];
    }
    b[0]=-INF; b[n+1]=INF;
    for(int i=0; i<MAXN*4; i++) minpos[i]=n+1;

    sort(b+1, b+n+1);
    unique(b+1, b+n+1);
    for(int i=1; i<=n; i++)
    {
        int pos=lower_bound(b+1, b+n+1, a[i])-b;
        if(vis[pos]) continue;
        vis[pos]=1;
        update(1, 1, n, pos);

        if(i==1) ans+=a[i];
        else
        {
            int x=queryl(1, 1, n, 1, pos-1);
            int y=queryr(1, 1, n, pos+1, n);
            ans+=min(a[i]-b[x], b[y]-a[i]);
        }
    }
    printf("%d\n", ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注