icontofig | 发布于 2020-02-24 15:52:01 | 阅读量 423 | 线段树
发布于 2020-02-24 15:52:01 | 线段树

 题目大意

给定一个序列a,要求你每个元素都选出不超过ai的值,使得选出的元素序列满足不严格上凸(上凸、非严格单调皆可),且总和最大,求问每个位置上选出的元素是多少。

题解

此题有一个暴力的easy version版本,只需要枚举每个位置为最大值点位置pos(也就是该点处选择的元素大小为apos)暴力计算即可。

但是当数据量变大到5*105数量级时,我们没有办法枚举位置暴力计算。

但是可以注意到,枚举每个位置为最大值点位置pos这一步仍然是不可避免地,这是解题的核心,于是很容易想到,我们需要在较短时间内算出当每个位置为最大值点位置时,所选出的最优序列的元素大小总和。我们不能用暴力的版本每一次枚举都用O(n)的时间复杂度来算。

我们考虑用一种类似于前缀和和后缀和的形式来计算上述提到的我们需要计算的。前缀和和后缀和相加减去此位置本身所得的值,即在当前位置为最大值点位置时,所选出的最优序列的元素总和的大小。最优前缀和与最优后缀和的计算模式大致相同,直接来看最优前缀和pre的计算方法吧。

假设当前枚举到的位置为pos(pos>1),考虑两种情况:

1.apos>=apos-1,这时选取当前位置为最大值点时,不会对pos-1为最大值点时的最优前缀和的值产生影响,直接转移:pre[pos] = pre[pos-1];

2.apos<apos-1,这时选取当前位置为最大值点时,就不能用pos-1为最大值点时的最优前缀和的值来进行转移,因为这时pos-1位置不能选取其最大值了。这时候需要考虑我们不会对哪个位置之前的选值有影响,很明显是pos位置前第一个小于等于apos的元素所在的位置。

最优后缀和也类似考虑。

在第一种情况下,我们无需考虑什么东西,可以直接转移。重点在第二种情况,如何寻找pos之前第一个小于等于apos的元素所在的位置,这个操作的复杂度会影响到我们整体的算法复杂度。

据说有可以把这个操作整体复杂度做到O(1)的做法,但是这里并没有想到,于是选择nlogn的线段树做法。

首先对数组离散化,对离散化后的权值建一棵线段树,线段树节点上的值为其子树中元素的最大值,元素表示的是当前节点代表的区间的各个离散化后的值中出现的最晚的位置(最大)是哪个位置。

从开始向后逐个计算。

如果在第一种情况,直接转移,并将当前的位置pos更新到到线段树对应着当前位置元素的离散化后的值的权值叶节点。

如果在第二种情况,假设当前位置pos离散化后的值为val,我们在线段树上求区间[1,val]中的最大值prepos,转移为pre[pos] = pre[prepos] + ai * (pos-prepos).

最优后缀和从后向前类似计算。

最终用O(n)的时间计算得到最优的最大值位置finalpos,然后O(n)模拟生成题目要求的序列即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5+5;
int m[maxn];
int n;
int ans[maxn];
ll cnt1[maxn],cnt2[maxn];
int a[maxn],p[maxn];
ll mx,now;
typedef pair<int,int>PI;
set<int>s;
PI tmp;
set<int>::iterator it;
int index;
map<int,int>mp;
struct tree{
    int l,r,pos;
}tr[maxn<<2];
void push_up(int now){
    tr[now].pos = max(tr[now<<1].pos,tr[now<<1|1].pos);
    return;
}
void build(int now,int l,int r){
    tr[now].l = l;
    tr[now].r = r;
    tr[now].pos = 0;
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
    return;
}
void update(int now,int pos,int x){
    if(tr[now].l == tr[now].r){
        tr[now].pos = pos;
        return;
    }
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(x <= mid)
        update(now<<1,pos,x);
    else update(now<<1|1,pos,x);
    push_up(now);
    return;
}
int query(int now,int l,int r){
    if(l > r)return 0;
    if(tr[now].l >= l && tr[now].r <= r){
        return tr[now].pos;
    }
    int ret = 0;
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(l <= mid)
        ret = max(ret,query(now<<1,l,r));
    if(r > mid)
        ret = max(ret,query(now<<1|1,l,r));
    return ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    mx = 0;
    for(int i = 1;i <= n;++i){
        cin >> m[i];
        s.insert(m[i]);
        cnt1[i] = cnt2[i] = 0;
    }
    for(it = s.begin();it != s.end();it++){
        mp[*it] = ++index;
    }
    build(1,1,index);
    cnt1[1] = m[1];
    update(1,1,mp[m[1]]);
    for(int i = 2;i <= n;++i){
        if(m[i] >= m[i-1]){
            cnt1[i] = cnt1[i-1] + m[i];
        }
        else{
            int pos = query(1,1,mp[m[i]]);
            cnt1[i] = cnt1[pos] + (ll)m[i] * (ll)(i - pos);
        }
        update(1,i,mp[m[i]]);
    }
    memset(tr,0,sizeof(tr));
    cnt2[n] = m[n];
    build(1,1,index);
    update(1,1,mp[m[n]]);
    for(int i = n-1;i >= 1;--i){
        if(m[i] >= m[i+1])
            cnt2[i] = cnt2[i+1] + m[i];
        else{
            int pos = query(1,1,mp[m[i]]);
            cnt2[i] = cnt2[n-pos+1] + (ll)m[i] * (ll)(n-pos+1-i);
        }
        update(1,n-i+1,mp[m[i]]);
    }
    int pos = 0;
    for(int i = 1;i <= n;++i){
        now = cnt1[i] + cnt2[i] - m[i];
        if(mx <= now)
            mx = now,pos = i;
    }
    ans[pos] = m[pos];
    for(int i = pos-1;i >= 1;--i){
        ans[i] = min(ans[i+1],m[i]);
    }
    for(int i = pos+1;i <= n;++i){
        ans[i] = min(ans[i-1],m[i]);
    }
    cout << ans[1];
    for(int i = 2;i <= n;++i)
        cout << " " << ans[i];
    cout << "\n";
    return 0;
}



内容更新于: 2020-02-24 15:52:01
链接地址: http://blog.leanote.com/post/icontofig/CodeForces

上一篇: CodeForces 1303G. Sum of Prefix Sums 点分治+李超线段树

下一篇: CodeForces 1303F. Number of Components 并查集

423 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航