线段树，但是50ptsMLE+TLE

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct Info{
    int pos,val;
};
int n,sum=0;
int a[N];
namespace SegmentTree{
    int Min[N<<2],pos[N<<2],b[N<<2];
    inline void pushup(int node){
        if (Min[node<<1]>Min[node<<1 | 1]) {Min[node]=Min[node<<1 | 1],pos[node]=pos[node<<1 | 1];}
        else {Min[node]=Min[node<<1],pos[node]=pos[node<<1];}
    }
    inline void pushdown(int node,int l,int r)
    {
        int mid=(l+r) >> 1;
        if (b[node])
        {
            Min[node<<1]-=b[node];b[node<<1]+=b[node];
            Min[node<<1 | 1]-=b[node];b[node<<1 | 1]+=b[node];
            b[node]=0;
        }
        return ;
    }
    inline void build(int node,int l,int r)
    {
        if (l==r)
        {
            b[node]=0;
            Min[node]=a[l];
            pos[node]=l;
            return ;
        }
        int mid=(l+r) >> 1;
        build(node<<1,l,mid);
        build(node<<1 | 1,mid+1,r);
        pushup(node);
    }
    inline void minus(int node,int l,int r,int s,int t,int c)
    {
        // cout<<"minus!  l:"<<s<<"  r:"<<r<<"  node:"<<node<<"  l:"<<l<<"  r:"<<r<<endl;
        if (l<=s && r>=t) 
        {
            Min[node]-=c;b[node]+=c;
            return ;
        }
        int mid=(s+t) >> 1;
        pushdown(node,s,t);
        if (l<=mid) minus(node<<1,l,r,s,mid,c);
        if (r>mid) minus(node<<1 | 1,l,r,mid+1,t,c);
        pushup(node);
    }
    Info query(int node,int l,int r,int s,int t)
    {
        // cout<<"query!  l:"<<s<<"  r:"<<t<<"  node:"<<node<<"  val:"<<Min[node]<<"  pos:"<<pos[node]<<endl;
        if (l<=s && r>=t) return (Info){pos[node],Min[node]};
        int mid=(s+t) >> 1;
        pushdown(node,s,t);
        Info Min_ans;Min_ans.val=0x3f;
        if (l<=mid) 
        {
            Info res=query(node<<1,l,r,s,mid);
            if (Min_ans.val>res.val) 
                {Min_ans=res;}
        }
        if (r>mid) 
        {
            Info res=query(node<<1 | 1,l,r,mid+1,t);
            if (Min_ans.val>res.val) 
                {Min_ans=res;}
        }
        pushup(node);
        return Min_ans;
    }   
    void find(int l,int r)
    {
        // cout<<"find!  l:"<<l<<"  r:"<<r<<"  sum:"<<sum<<endl;
        if (l==r) {sum+=query(1,l,r,1,n).val;return ;}
        Info nMin=query(1,l,r,1,n);
        sum+=nMin.val;
        minus(1,l,r,1,n,nMin.val);
        int place=nMin.pos;
        // cout<<"place!"<<place<<"   val:"<<nMin.val<<endl;
        if (place>l) find(l,place-1);
        if (place<r) find(place+1,r);
    }
}
using namespace SegmentTree;
inline int read(){
    int s=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') {f=-1;} ch=getchar();}
    while(isdigit(ch)) {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
    return s*f;
}
inline void write(int x){
    int top=0,sta[35];
    while(x) {sta[top++]=x%10,x/=10;}
    while(top) {putchar(sta[--top]+'0');}
}
int main()
{
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    find(1,n);
    printf("%d",sum);
    return 0;
}