树状数组优化解决最长公共子序列

树状数组可以用来解决最长公共子序列问题。下面是使用树状数组优化的最长公共子序列求解算法。

首先，我们需要将两个序列分别离散化，将每个数映射到一个连续的整数区间内，然后将它们分别存储在两个数组中。

接着，我们定义一个二维数组`dp`，其中`dp[i][j]`表示序列1中前i个数和序列2中前j个数的最长公共子序列长度。则有以下状态转移方程：

if (a[i] == b[j])
    dp[i][j] = dp[i-1][j-1] + 1;
else
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

其中，`a`和`b`分别是两个离散化后的序列。

时间复杂度为O(n^2)。

然后，我们可以使用树状数组来优化这个算法，将时间复杂度降至O(nlogn)。

我们需要定义一个树状数组`c`，其中`c[i]`表示序列1中前i个数中最后一个数在序列2中出现的位置。然后，我们可以用二分查找来找到序列1中第i个数在序列2中出现的最晚位置，即`c[i]`。

接着，我们可以通过遍历序列1中的每个数，用树状数组更新`c`数组，并根据`c`数组和状态转移方程来更新`dp`数组。

具体来说，对于序列1中的第i个数，我们可以用二分查找在序列2中找到它出现的最晚位置`pos`，然后用树状数组将`pos`更新为i。接着，我们可以遍历序列2中的每个数，如果它在序列1中出现过，则可以根据状态转移方程来更新`dp`数组。

时间复杂度为O(nlogn)。

以下是使用树状数组优化的最长公共子序列求解算法的完整代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 100000

int a[MAX_N + 10], b[MAX_N + 10];
int c[MAX_N + 10];
int dp[MAX_N + 10][2];
int n, m;

int lowbit(int x)
{
    return x & (-x);
}

void update(int x, int val)
{
    while (x <= n)
    {
        c[x] = max(c[x], val);
        x += lowbit(x);
    }
}

int query(int x)
{
    int res = 0;
    while (x)
    {
        res = max(res, c[x]);
        x -= lowbit(x);
    }
    return res;
}

int main()
{
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }

    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &b[i]);
    }

    // 离散化
    int k = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = k; j <= m; j++)
        {
            if (a[i] == b[j])
            {
                a[i] = j;
                k = j + 1;
                break;
            }
        }
    }

    // 初始化
    memset(c, 0, sizeof(c));
    memset(dp, 0, sizeof(dp));

    // 动态规划求解
    for (int i = 1; i <= n; i++)
    {
        int pos = query(a[i]);
        dp[i][0] = dp[i-1][1];
        dp[i][1] = dp[i-1][1];
        if (pos > 0)
        {
            dp[i][1] = max(dp[i][1], dp[pos-1][0] + i - pos + 1);
        }
        update(a[i], i);
    }

    printf("%d\n", dp[n][1]);

    return 0;
}