题目大意

题意

分析

经典问题

nn 较小时，考虑 g[i]g[i] 为第 ii 个数为末尾的最长上升子序列的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int f[1005];
mint g[1005];
signed main()
{
	int n;cin>>n;
	vector<int> a(n+1);
	for(int i = 1;i<=n;i++) cin>>a[i];
	g[0] = 1;
	for(int i = 1;i <= n;i++)
		for(int j = 0;j < i;j++){
			if(a[i] > a[j]){
				if(f[i] < f[j]+1) g[i] = g[j];
				else if(f[i] == f[j]+1) g[i] += g[j];
				f[i] = max(f[i],f[j]+1);
			}
		}
	int t = *max_element(f+1,f+1+n);
	mint res = 0;
	for(int i = 1;i <= n;i++){
		if(f[i] == t) res += g[i];
	}
	cout << res.get() << endl;
	return 0;
}

对于本题 1<=n<=4e51 <= n <= 4e5 , 规定

mx[i]mx[i] 表示以 ii 结尾的最长上升子序列的长度, cnt[i]cnt[i] 对应这个长度的个数

由于最长上升子序列满足偏序关系，算法学习笔记(20): 二维偏序

我们可以用树状数组来维护以 ii 结尾的最长上升子序列的长度 mx[]mx[]和其对应的长度的个数cnt[]cnt[]

Code

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
const int mod = 1e9+7;
int n;
int cnt[400005],mx[400005];

int lwb(int x){
    return x & -x;
}
void add(int p,int v,int len){
    for(int i = p; i<= n;i+=lwb(i)){
        if(mx[i] < v){
            mx[i] = v;
            cnt[i] = len;
        }
        else if(mx[i] == v){
            cnt[i] = (cnt[i] + len)%mod;
        }
    }
}

pair<int,int> ask(int p){
    pair<int,int> res = {0,0};
    for(int i = p;i;i-=lwb(i)){
        if(res.first < mx[i]){
            res.first = mx[i];
            res.second = cnt[i];
        }
        else if (res.first == mx[i]){
            res.second = (res.second + cnt[i])%mod;
        }
    }
    return res;
}

signed main()
{
    cin>>n;
    vector<int> a(n+1),b(n+1);
    for(int i = 1;i <= n;i++)  cin >> a[i],b[i] = a[i];
    sort(b.begin()+1,b.end());
    b.erase(unique(b.begin()+1,b.end()),b.end());
    for(int i = 1;i <= n;i++) a[i] = lower_bound(b.begin()+1,b.end(),a[i]) - b.begin();

    int maxn = 0;
    vector<pair<int,int>> ans;
    for(int i = 1;i <= n;i++){
        auto t = ask(a[i]-1);
        maxn = max(maxn,t.first+1);
        if(! t.second ) t.second = 1;
        ans.push_back({t.first+1,t.second});
        add(a[i],t.first+1,t.second);
    }
    int res = 0;
    for(auto i:ans){
        if(i.first == maxn) res = (res + i.second)%mod;
    }
    cout << res << endl;
    return 0;
}