盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 5141 LIS again(LIS+dp+线段树)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5141

题意

有n个数的序列,另该序列的最长上升子序列的长度为k。求该序列中子串满足最长上升子序列长度也为k的个数。1≤n≤100000

思路

首先我们用线段树可以求出以第i位为结尾的最大长度。假如当前dp[i]=k, 如果可以求得以i结尾,符合条件的最短子串,那么用左边的长度 * 右边的长度就是符合条件的个数。当然,如果后面还有一个符合dp[i’]=k, 那么右边只能到i’-1, 之后的在i’时在计算,可以避免重复
可以用线段树维护以i结尾符合条件的lis最靠右的起始位置。

代码

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define INF 1 << 30
#define fi first
#define se second
#define debug puts("=====================");
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define pii pair<int, int>
#define mkp make_pair
using namespace std;
typedef long long ll;
const int N = 1e5 + 100;
int a[N], b[N], n, cnt;
int f[N][2];
int mx[N << 2], id[N << 2];
int ans;
void pushup(int rt) {
if (mx[rt << 1] < mx[rt << 1 | 1]) mx[rt] = mx[rt << 1 | 1], id[rt] = id[rt << 1 | 1];
else mx[rt] = mx[rt << 1], id[rt] = id[rt << 1];
}
void build(int l, int r, int rt) {
if (l == r) {
mx[rt] = id[rt] = 0;
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushup(rt);
}
pii query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return mkp(mx[rt], id[rt]);
}
int m = (l + r) >> 1;
pii t1, t2;
t1.first = 0, t2.first = 0;
if (L <= m) t1 = query(L, R, lson);
if (R > m) t2 = query(L, R, rson);
if (t1.first < t2.first) return t2;
else return t1;
}
void update(int L, int R, int x, int y, int l, int r, int rt) {
if (L <= l && r <= R) {
mx[rt] = x, id[rt] = y;
return ;
}
int m = (l + r) >> 1;
if (L <= m) update(L, R, x, y, lson);
if (R > m) update(L, R, x, y, rson);
pushup(rt);
}
int main () {
while(~scanf("%d", &n)) {
for (int i = 0; i < n; i++) scanf("%d", a + i), b[i] = a[i];
sort(b, b + n);
cnt = unique(b, b + n) - b;
ans = 0;
for (int i = 0; i < n; i++) a[i] = lower_bound(b, b + cnt, a[i]) - b + 1; //, cout<<a[i]<<endl;
build(1, cnt, 1);
//debug;
pii tmp;
for (int i = 0; i < n; i++) {
if (a[i] == 1) tmp.first = 0;
else tmp = query(1, a[i] - 1, 1, cnt, 1);
if (tmp.first == 0) tmp.second = i + 1;
tmp.first++;
f[i][0] = tmp.first, f[i][1] = tmp.second;
ans = max(ans, tmp.first);
//cout<<f[i][0]<<" "<<f[i][1]<<endl;
update(a[i], a[i], tmp.first, tmp.second, 1, cnt, 1);
}
ll res = 0;
vector< pii > g;
for (int i = 0; i < n; i++) if (f[i][0] == ans) {
g.push_back(mkp(i + 1, f[i][1]));
}
g.push_back(mkp(n + 1, 0));
for (int i = 0; i < g.size() - 1; i++) {
res += (ll)(g[i + 1].first - g[i].first) * g[i].second;
}
printf("%I64d\n", res);
}
return 0;
}