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
不会正确性证明

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MaxN = 1000000;
int Max1[MaxN + 5], Max2[MaxN + 5], Max3[MaxN + 5];
#define lowbit(_) ((_) & (-_))
void Update1(int a, int b)
{
    for (int i = a; i <= MaxN; i += lowbit(i))
    {
        Max1[i] = max(b, Max1[i]);
    }
}
void Update2(int a, int b)
{
    for (int i = a; i > 0; i -= lowbit(i))
    {
        Max2[i] = max(b, Max2[i]);
    }
}
int MAX1(int x)
{
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i))
    {
        ans = max(ans, Max1[i]);
    }
    return ans;
}
int MAX2(int x)
{
    int ans = 0;
    for (int i = x; i <= MaxN; i += lowbit(i))
    {
        ans = max(ans, Max2[i]);
    }
    return ans;
}
int a[500005], op[500005];
int f[500005][4], n, k;
void add(int len, int a)
{
    int W = (len - 1) % k + 1;
    switch (op[W])
    {
    case 1:
        Update1(a, len);
        break;
    case 2:
        Update2(a, len);
        break;
    case 3:
        Max3[a] = max(len, Max3[a]);
        break;
    default:
        printf("ERROR\n");
        exit(0);
        break;
    }
}
int main()
{
    //freopen("mot.in", "r", stdin);
    //freopen("mot.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    char c;
    for (int i = 1; i <= k; i++)
    {
        c = getchar();
        while (c != '<' && c != '>' && c != '=')
            c = getchar();
        switch (c)
        {
        case '<':
            op[i] = 1;
            break;
        case '>':
            op[i] = 2;
            break;
        case '=':
            op[i] = 3;
        }
    }
    int ans = 0;
    //f[1][1] = f[1][2] = f[1][3] = 1;
    for (int i = 1; i <= n; i++)
    {
        f[i][1] = MAX1(a[i] - 1) + 1;
        f[i][2] = MAX2(a[i] + 1) + 1;
        f[i][3] = Max3[a[i]] + 1;
        for (int j = 1; j <= 3; j++)
        {
            add(f[i][j], a[i]);
            ans = max(ans, f[i][j]);
        }
    }
    //for(int i=1;i<=n;i++)
    //    printf("%d %d %d\n",f[i][1],f[i][2],f[i][3]);
    // while(1);
    printf("%d", ans);
}