HDU-6284

Posted on | Edited on | In | Views:

Longest Increasing Subsequence

题意

有一个长度为 $n$ 的数组 $a(0\le a_i\le n)$ ,$f(x)$ 表示把 $0$ 变成 $x$ , 序列的 $LIS(严格递增)$ , 求$\sum\limits_{i=1}^ni\times f(i)$

题解

设 $bg[i], en[i]$ 分别表⽰以点 $i$ 开始、结束的 $LIS$ ⻓度，$L$ 是原来的 $LIS$ ⻓度。对于每个 $i$，找出它下⼀个 $0$ 后⾯的 $a[j]$ 满⾜ $en[i]+bg[j] = L$，那么当 $x$ 在 $[a[i] + 1, a[j] − 1]$ 的区间内时，答案是 $L + 1$.

从后往前扫, 用一个数组 $\text{max_r[i]}$ 记录扫过的最后一个 $0$ 右边区域的 $bg=i$ 的最大值

以 $0$ 为分隔, 用一个 $vector$ 存当前分块的 $ \text{max_r}$ 值, 当遇到下一个 $0$ 的时候更新 $\text{max_r}$ , 注意当 $bg=L$ 时要特殊考虑

代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>
using namespace std;
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define forr(i, r, l) for (int i = r; i >= l; i--)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define fro1(i, n) for (int i = 1; i <= n; i++)
#define for0(i, n) for (int i = 0; i < n; i++)
#define fro0(i, n) for (int i = 0; i < n; i++)
#define meminf(a) memset(a, inf, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define memcp(a,b) memcpy(a,b,sizeof(b))
#define oper(type) bool operator <(const type y)const
#define mp make_pair
#define pu_b push_back
#define pu_f push_front
#define po_b pop_back
#define po_f pop_front
#define fi first
#define se second
#define whiel while
#define retrun return
typedef pair<long long, long long> pll;
typedef vector<long long> vll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef vector<int> vii;
typedef long double db;
typedef long long ll;
typedef int itn;
int in(int &a,int &b,int &c,int &d){return scanf("%d%d%d%d",&a,&b,&c,&d);}
int in(int &a,int &b,int &c){return scanf("%d%d%d",&a,&b,&c);}
int in(int &a,int &b){return scanf("%d%d",&a,&b);}
int in(ll &a){return scanf("%lld",&a);}
int in(int &a){return scanf("%d",&a);}
int in(char *s){return scanf("%s",s);}
int in(char &s){return scanf("%c",&s);}
int in(db &a){return scanf("%Lf",&a);}
void out(int a){printf("%d",a);}
void outln(int a){printf("%d\n",a);}
void out(ll a){printf("%lld",a);}
void outln(ll a){printf("%lld\n",a);}
const db pi = acos((db)-1);
const int inf =0x3f3f3f3f;
const db eps = 1e-8;
const int N = 1.1e5;
const ll mod = 1e9+7;
int sign(db a) { return a < -eps ? -1 : a > eps;}
int db_cmp(db a, db b){ return sign(a-b); }

int a[N],bg[N],en[N],dp[N],fu[N],max_r[N];
vector<pii> peding;
int l_bound(int l,int r,int x){
    r--;
    whiel(l<=r){
        int mid=(l+r)/2;
        if(dp[mid]>x)l=mid+1;
        else r=mid-1;
    }
    return l;
}
int main() {
    itn n;
    whiel(~in(n)){
        int L=0;
        for1(i,n)in(a[i]);
        for1(i,n)max_r[i]=fu[i]=0;
        for1(i,n){
            if(a[i]){
                if(L){
                    if(a[i]>dp[L-1]){
                        dp[L++]=a[i];
                        en[i]=L;
                    }else{
                        int p=lower_bound(dp,dp+L,a[i])-dp;
                        dp[p]=min(dp[p],a[i]);
                        en[i]=p+1;
                    }
                }else{
                    dp[L++]=a[i];
                    en[i]=L;
                }
            }
        }
        L=max(L,1);
        ll ans=(1ll+n)*n/2*L;
        L=0;
        for(itn i=n;i>0;i--){
            if(a[i]){
                if(L){
                    if(a[i]<dp[L-1]){
                        dp[L++]=a[i];
                        bg[i]=L;
                    }else{
                        int p=l_bound(0,L,a[i]);
                        dp[p]=max(dp[p],a[i]);
                        bg[i]=p+1;
                    }
                }else{
                    dp[L++]=a[i];
                    bg[i]=L;
                }
            }
        }
        max_r[0]=0;
        peding.clear();
        for(itn i=n;i>0;i--){
            if(a[i]){
                if(max_r[L-en[i]]>a[i]){
                    fu[a[i]+1]++;
                    fu[max_r[L-en[i]]]--;
                }
                peding.pu_b(pii(bg[i],a[i]));
            }else{
                max_r[0]=n+1;
                whiel(peding.size()){
                    pii kk=peding.back();
                    peding.po_b();
                    if(kk.fi==L){
                        fu[1]++;
                        fu[kk.se]--;
                    }else{
                        max_r[kk.fi]=max(max_r[kk.fi],kk.se);
                    }
                }
            }
        }
        for1(i,n){
            fu[i]+=fu[i-1];
            if(fu[i])ans+=i;
        }
        outln(ans);
    }
    return 0;
}