HDU_5141

题意

求[i,j]的自区间个数，要求子区间的LIS等于父区间的LIS。

思路

poursoul的博客

枚举终点j，每一个并且让符合条件的起点i尽量靠右。那么，在j点时，区间个数为i个。
例如 1 3 2 5 4，LIS的起点是1，j=4时，1 3 2 5 是符合条件的。
我的代码中s数组是标准的lower_bound求LIS的数组。cnt里放的是尽量靠右的起点。
真的很难用语言描述啊，我也是非了很多脑子才懂得。如果听不懂我再说什么，还是点上面的链接去看看poursoul大神的讲解吧。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>  
#include <vector>  
#include <cstring>  
#include <cmath>  
#include <algorithm>  
using namespace std ;  
#define ll long long  
const int MAXN = 100005 ;  
ll cnt[MAXN] ;  
ll s[MAXN] ;  
int n ;  
void work(){
    ll ans = 0,tmp,top=0;
    for(int i = 1 ;i<= n ;i++){
        scanf("%I64d",&tmp);
        if(!top || s[top] < tmp){
            s[++top]=tmp;
            if(top == 1)cnt[1] = i;
            else cnt[top] = cnt[top -1]; 
            ans = cnt[top] ;
        }
        else{
            ll tmpl = lower_bound(s+1,s+1+top,tmp)-s;
            if( tmpl == 1)cnt[1]=i;
            else cnt[tmpl] = cnt[tmpl - 1];
            s[tmpl] = tmp;
            ans += cnt[top];
        }
    }
    printf("%I64d\n",ans);
}
int main () {  
    while ( ~scanf ( "%d" , &n )) work();
    return 0 ;  
}