Codeforces Round #622 (Div. 2)C2 Skyscrapers最大"尖"性矩形，思维||分治

题：https://codeforces.com/contest/1313/problem/C2

题意：给出n个数，分别代表第i个位置所能搭建的最大高度，问以哪一个位置的塔的高度为基准向左的每一个塔都小于等于临近右边的塔，向右每一个塔都大于等于临近的左边的塔所构建的高度之和是最大的，输出最大的高度之和；

分析：我们设一个fir[i]数组，表示当前 i 位置向左能构造的最大高度和（就想阶梯一样，i位置是阶梯的最高处），sec[i]则是向右的；

　　　因为求出这俩个数组后，我们直接o（n）的访问fir[i]+sec[i]-a[i]找最大的既可找出能构造出最大面积和的位置；

　　　对于这个fir[]的求法，对于位置 i ，可以利用前面已经算得的结果，假设位置 j （j<i）很明显的fir[i]=fir[j]+（i-j）*a[i],因为再i~j间的高度都是大于a[i]的，fir[i]是取不到fir[i~j]间的部分面积的，所以把i~j高度降为和 i 位置的高度一样即可贪心地求最大，sec[]求法类似

#include<bits/stdc++.h>
using namespace std;
const int M=5e5+5;
typedef long long ll;
ll a[M],pre[M],las[M],s[M],fir[M],sec[M],ans[M];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,top=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        while(top&&a[i]<a[s[top]])
            top--;
        pre[i]=s[top];
        s[++top]=i;
        fir[i]=fir[pre[i]]+1ll*(i-pre[i])*a[i];
    } 
    s[top=0]=n+1;
    for(int i=n;i>=1;i--){
        while(top&&a[i]<a[s[top]])
            top--;
        las[i]=s[top];
        s[++top]=i;
        sec[i]=sec[las[i]]+1ll*(las[i]-i)*a[i];
    }
    int pos=0;
    for(int i=1;i<=n;i++){
        if(fir[i]+sec[i]-a[i]>fir[pos]+sec[pos]-a[pos])
            pos=i;
    }
    for(int i=pos;i;i=pre[i])
        for(int j=i;j>pre[i];j--)
            ans[j]=a[i];
    for(int i=pos;i;i=las[i])
        for(int j=i;j<las[i];j++)
            ans[j]=a[i];
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<' ';
    return 0;
}

View Code

分治做法:

分析：对于任意一段[l,r]的高度限制，假设a[i]是其中最小的高度，那么要么是 i 的右边的高度全设为a[i]，要么 i 的左边的高度全设为a[i]这俩种可能，那我们就分治下这些区间就行了；

　　　找最小的高度用线段树实现即可，也可用其他方法；

　　　复杂度分析，退化的情况我们分治的区间是[1,n],[1,n-1],[1,n-2]。。。这样n个区间，那么只要我们保证每个区间只是log级别的复杂度即可；

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define lson root<<1,l,midd
#define rson root<<1|1,midd+1,r
typedef long long ll;
const int inf=0x3f3f3f3f;
const int M=5e5+5;
int n;
struct node{
    ll val,id;
}tr[M<<2];
ll a[M],ans[M];
void up(int root){
    if(tr[root<<1].val<=tr[root<<1|1].val){
        tr[root]=tr[root<<1];
    }
    else
        tr[root]=tr[root<<1|1];
}
void build(int root,int l,int r){
    if(l==r){
        tr[root].val=a[l];
        tr[root].id=l;
        return ;
    }
    int midd=(l+r)>>1;
    build(lson);
    build(rson);
    up(root);
}
node query(int L,int R,int root,int l,int r){
    if(L<=l&&r<=R){
        return tr[root];
    }
    node res;
    res.val=1e9+7;
    int midd=(l+r)>>1;
    if(L<=midd){
        node now=query(L,R,lson);
        if(now.val<res.val)
            res=now;
    }
    if(R>midd){
        node now=query(L,R,rson);
        if(now.val<res.val)
            res=now;
    }
    return res;
}
ll solve(int l,int r){
//    cout<<l<<"!!"<<r<<endl;
    if(l>r)
        return 0ll;
    if(l==r){
        ans[l]=a[l];
        return a[l];
    }
    node now=query(l,r,1,1,n);
//    cout<<now.id<<"!!"<<endl;
    ll lsum=solve(l,now.id-1);
    ll rsum=solve(now.id+1,r);
    if(lsum+now.val+1ll*now.val*(r-now.id)>1ll*now.val*(now.id-l)+now.val+rsum){
        for(int i=now.id;i<=r;i++)
            ans[i]=now.val;
        return lsum+now.val+now.val*(r-now.id);
    }
    else{
        for(int i=l;i<=now.id;i++)
            ans[i]=now.val;
        return now.val*(now.id-l)+now.val+rsum;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<=4*n;i++)
        tr[i].val=inf; 
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);

    solve(1,n);
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<' ';
    return 0;
}

View Code