[ABC038C] 単調増加
题意翻译
问有多少个子串(不包括空串,其实我觉得应该读子序列)是单调上升的
注意:类似于[1] [8848] [233] 这样一个数字的也属于单调上升的
感谢 @RioBlu 的翻译
题目描述
[problemUrl]: https://atcoder.jp/contests/abc038/tasks/abc038_c
$ N $個の数からなる数列が与えられます。$ i $番目の数を$ a_i $と呼びましょう。
$ a_l,a_{l+1},...,a_r $ が単調増加、すなわち $ l≦r $ であって $ a_i\ <\ a_{i+1} $ が$ l≦i\ <\ r $ を満たす全ての$ i $に対して成り立つような$ (l,r) $の数を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ a_1 $ $ a_2 $ … $ a_N $
输出格式
$ a_l,a_{l+1},...,a_r $ が単調増加となるような$ (l,r) $の数を $ 1 $ 行に出力せよ。
输入输出样例
输入样例 #1
5
1 2 3 2 1
输出样例 #1
8
输入样例 #2
4
1 2 3 4
输出样例 #2
10
输入样例 #3
6
3 3 4 1 2 2
输出样例 #3
8
输入样例 #4
6
1 5 2 3 4 2
输出样例 #4
10
说明
### 制約
- $ 1≦N≦10^5 $
- $ 1≦a_i≦10^5 $
- $ a_i $は全て整数である
### 部分点
- $ N\ ≦\ 3,000 $ を満たすテストケース全てに正解した場合、部分点として$ 40 $点が与えられる。
### Sample Explanation 1
条件を満たす$ (l,r) $は$ (1,1),(1,2),(1,3),(2,2),(2,3),(3,3),(4,4),(5,5) $の$ 8 $つです。
### Sample Explanation 2
$ 1≦l≦r≦N $を満たす$ (l,r) $全てが条件を満たします。
### Sample Explanation 3
例えば、$ 3,\ 3,\ 4 $はこの問題で単調増加ではないことに注意してください。