Codeforces Round #305 (Div. 1), problem: (B) Mike and Feet

用線段樹加減暴力尻過

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <utility>

using namespace std;

typedef long long int int64;

void dump(int n, int* arr){
    for(int lx = 0;lx < n;lx++)
        printf("%d ", arr[lx]);
    puts("");
    return;
}

struct minbst{
    vector<int> tree;
    int base;
    minbst(int n, int* arr){
        base = (1<<(int)(ceil(log2(n+3))))-1;
        tree = vector<int>(base*2+2, 2000000000);
        for(int lx = 0;lx<n;lx++)
            tree[lx+base+2] = arr[lx];
        for(int lx = base;lx;lx--)
            tree[lx] = min(tree[lx<<1], tree[(lx<<1)^1]);
        return;
    }
    int query(int a, int b){
        int ans = 2000000000;
        for(a += base+1, b+=base+3; a^b^1;a>>=1, b>>=1){
            if(~a&1) ans = min(ans, tree[a^1]);
            if(b&1) ans = min(ans, tree[b^1]);
        }
        return ans;
    }
};


int n;
int arr[200000];
int bas[200000] = {0};
int poi[200001] = {0};
int ans[200001];
int main(){
    scanf("%d", &n);
    for(int lx = 0;lx < n;lx++)
        scanf("%d", arr+lx);

    //dump(n, arr);

    for(int _ = 0; _ < 2;_++){
        minbst bst(n, arr);
        for(int lx = 0;lx < n;lx++){
            int ll = 0, rr = n-lx;
            while(ll < rr-1){
                int test = (ll+rr)>>1;
                if(bst.query(lx, lx+test) >= arr[lx])
                    ll = test;
                else
                    rr = test;
            }
            bas[lx] += ll;
        }
        //dump(n, bas);
        reverse(arr, arr+n);
        reverse(bas, bas+n);
    }

    for(int lx = 0;lx < n;lx++)
        poi[bas[lx]+1] = max(arr[lx], poi[bas[lx]+1]);

    //dump(n, poi);
    
    int mm = 0;
    for(int lx = n;lx;lx--){
        mm = max(mm, poi[lx]);
        ans[lx-1] = mm;
    }

    dump(n, ans);
    
    return 0;

}