BZOJ 2090 [Poi2010] Monotonicity 2

Description#

给出N个正整数a[1..N]，再给出K个关系符号（>、<或=）s[1..k]。选出一个长度为L的子序列（不要求连续），要求这个子序列的第i项和第i+1项的的大小关系为s[(i-1)mod K+1]。求出L的最大值。

Input#

第一行两个正整数，分别表示N和K (N, K <= 500,000)。第二行给出N个正整数，第i个正整数表示a[i]（a[i] <= 10^6）。第三行给出K个空格隔开关系符号（>、<或=），第i个表示s[i]。

Output#

一个正整数，表示L的最大值。

Sample Input#

7 3
2 4 3 1 3 5 3
< > =

Sample Output#

6

HINT#

选出的子序列为2 4 3 3 5 3，相邻大小关系分别是< > = < >。

题解#

权值树状数组优化DP
不会正确性证明

1
#include <cstdio>
2
#include <cstring>
3
#include <cstdlib>
4
#include <algorithm>
5
using namespace std;
6
const int MaxN = 1000000;
7
int Max1[MaxN + 5], Max2[MaxN + 5], Max3[MaxN + 5];
8
#define lowbit(_) ((_) & (-_))
9
void Update1(int a, int b)
10
{
11
    for (int i = a; i <= MaxN; i += lowbit(i))
12
    {
13
        Max1[i] = max(b, Max1[i]);
14
    }
15
}
16
void Update2(int a, int b)
17
{
18
    for (int i = a; i > 0; i -= lowbit(i))
19
    {
20
        Max2[i] = max(b, Max2[i]);
21
    }
22
}
23
int MAX1(int x)
24
{
25
    int ans = 0;
26
    for (int i = x; i > 0; i -= lowbit(i))
27
    {
28
        ans = max(ans, Max1[i]);
29
    }
30
    return ans;
31
}
32
int MAX2(int x)
33
{
34
    int ans = 0;
35
    for (int i = x; i <= MaxN; i += lowbit(i))
36
    {
37
        ans = max(ans, Max2[i]);
38
    }
39
    return ans;
40
}
41
int a[500005], op[500005];
42
int f[500005][4], n, k;
43
void add(int len, int a)
44
{
45
    int W = (len - 1) % k + 1;
46
    switch (op[W])
47
    {
48
    case 1:
49
        Update1(a, len);
50
        break;
51
    case 2:
52
        Update2(a, len);
53
        break;
54
    case 3:
55
        Max3[a] = max(len, Max3[a]);
56
        break;
57
    default:
58
        printf("ERROR\n");
59
        exit(0);
60
        break;
61
    }
62
}
63
int main()
64
{
65
    //freopen("mot.in", "r", stdin);
66
    //freopen("mot.out", "w", stdout);
67
    scanf("%d%d", &n, &k);
68
    for (int i = 1; i <= n; i++)
69
    {
70
        scanf("%d", &a[i]);
71
    }
72
    char c;
73
    for (int i = 1; i <= k; i++)
74
    {
75
        c = getchar();
76
        while (c != '<' && c != '>' && c != '=')
77
            c = getchar();
78
        switch (c)
79
        {
80
        case '<':
81
            op[i] = 1;
82
            break;
83
        case '>':
84
            op[i] = 2;
85
            break;
86
        case '=':
87
            op[i] = 3;
88
        }
89
    }
90
    int ans = 0;
91
    //f[1][1] = f[1][2] = f[1][3] = 1;
92
    for (int i = 1; i <= n; i++)
93
    {
94
        f[i][1] = MAX1(a[i] - 1) + 1;
95
        f[i][2] = MAX2(a[i] + 1) + 1;
96
        f[i][3] = Max3[a[i]] + 1;
97
        for (int j = 1; j <= 3; j++)
98
        {
99
            add(f[i][j], a[i]);
100
            ans = max(ans, f[i][j]);
101
        }
102
    }
103
    //for(int i=1;i<=n;i++)
104
    //    printf("%d %d %d\n",f[i][1],f[i][2],f[i][3]);
105
    // while(1);
106
    printf("%d", ans);
107
}