@[Lhz1313](/user/311830) 你这个算法最坏是 $O(n^2)$ 的吧，$100$ 分需要 $O(n\log n)$ 或者 $O(n)$ 的做法
by FunnyCreatress @ 2020-07-16 13:46:09
（话说我第一眼看你的用户名以为和我首字母一样qwq）
by FunnyCreatress @ 2020-07-16 13:47:10
@[FunnyCreatress](/user/77174) ....我首字母就LHZ...我也想不出有啥优化的了
by Lhz1313 @ 2020-07-16 14:36:21
@[FunnyCreatress](/user/77174) 多谢多谢
by Lhz1313 @ 2020-07-16 14:36:46
@[Lhz1313](/user/311830) 了解下差分？
by 剑雪清寒 @ 2021-07-23 16:41:12
我很奇怪，在洛谷中过了，但在站外 T 了最后一个点。怎样的数据把我卡掉了？[（我的记录）](https://www.luogu.com.cn/record/77537740)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
int a[N]={0};
int n,m,t,s=0;
void build(int l,int r){
if(l>=r)return;
int i,minn=N;
for(i=l;i<r;i++){
minn=min(minn,a[i]);
}
s+=minn;
int nl=l;
for(i=l;i<r;i++){
a[i]-=minn;
if(!a[i])build(nl,i),nl=i+1;
}
build(nl,r);
}
int main(){
int i;
//freopen("6_18.in","r",stdin);
//freopen("6_18.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",a+i);
build(1,n+1);
printf("%d",s);
return 0;
}
```
by __K2FeO4 @ 2022-06-18 12:46:15
我也是拆楼，只不过一起拆，次数减少，这是一种优化。
我需要找到合适的数据把我 hack 掉。
by __K2FeO4 @ 2022-06-18 12:50:35
好了，我找到了。
$1\sim10000$ 循环 $10$ 次，复杂度 $\Theta(\frac{10000\times(10000+1)}{2}\times10)=\Theta(5\times10^8)$，会爆掉。
希望本数据加入本题。
重申数据：
$$
\begin{aligned}
1,2,3,\dots,10000,1,2,3,\dots,10000,\\
1,2,3,\dots,10000,1,2,3,\dots,10000,\\
1,2,3,\dots,10000,1,2,3,\dots,10000,\\
1,2,3,\dots,10000,1,2,3,\dots,10000,\\
1,2,3,\dots,10000,1,2,3,\dots,10000.
\end{aligned}
$$
by __K2FeO4 @ 2022-06-18 13:25:45