@[Itst](/space/show?uid=96296) 把O(n)优化成O(nlogn)？（滑稽
by A星际穿越 @ 2018-11-10 19:45:11
@[Itst](/space/show?uid=96296)
有毒吧...
这样还不如写n2暴力啊
by x_angelkawaii_x @ 2018-11-10 19:45:11
@[A星际穿越](/space/show?uid=62138)
线段树好想好写,何乐而不为
by x_angelkawaii_x @ 2018-11-10 19:45:37
@[沉迷学习的YSJ](/space/show?uid=93483) 差分更好想更好写，何乐而不为
by A星际穿越 @ 2018-11-10 19:46:25
@[沉迷学习的YSJ](/space/show?uid=93483) 11行代码
by A星际穿越 @ 2018-11-10 19:46:56
@[A星际穿越](/space/show?uid=62138)
你觉得是吗
by x_angelkawaii_x @ 2018-11-10 19:47:16
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[100010];
long long ans;
int main(){
scanf("%d\n",&n);
for(int i=1;i<=n;++i)scanf("%d ",&a[i]);
for(int i=1;i<=n;i++)ans+=max(0,a[i]-a[i-1]);
printf("%d",ans);
return 0;
}
```
by A星际穿越 @ 2018-11-10 19:47:18
@[沉迷学习的YSJ](/space/show?uid=93483)
by A星际穿越 @ 2018-11-10 19:47:31
@[A星际穿越](/space/show?uid=62138)
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000+10;
#define LL long long
int n;
int a[maxn];
struct node
{
int minx;
int pos;
}tree[maxn<<2];
#define mid ((l+r)>>1)
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
inline void pushup(int rt)
{
if(tree[ls].minx<tree[rs].minx)
{
tree[rt].minx=tree[ls].minx;
tree[rt].pos=tree[ls].pos;
}
else
{
tree[rt].minx=tree[rs].minx;
tree[rt].pos=tree[rs].pos;
}
}
void build(int rt,int l,int r)
{
if(l==r)
{
scanf("%d",&tree[rt].minx);
tree[rt].pos=l;
a[l]=tree[rt].minx;
return;
}
build(lson),build(rson);
pushup(rt);
}
int query(int rt,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return tree[rt].pos;
if(R<=mid)return query(lson,L,R);
if(L>mid)return query(rson,L,R);
int p1=query(lson,L,mid),p2=query(rson,mid+1,R);
return a[p1]<a[p2]?p1:p2;
}
LL solve(int l,int r,int k)
{
if(l>r)return 0;
if(l==r)return a[l]-k;
int p=query(1,1,n,l,r);
return (LL)a[p]-(LL)k+solve(l,p-1,a[p])+solve(p+1,r,a[p]);
}
int main()
{
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
scanf("%d",&n);
build(1,1,n);
cout<<solve(1,n,0)<<endl;
return 0;
}
```
by x_angelkawaii_x @ 2018-11-10 19:47:56
23333
by A星际穿越 @ 2018-11-10 19:48:13