题目分析

题意理解

我们有两个序列：

• 整数序列 a₁, a₂, ..., aₙ
• 符号序列 s₁, s₂, ..., sₖ（由 <, >, = 组成）

我们需要找到整数序列的最长子序列，使得这个子序列相邻元素之间的关系循环匹配给定的符号序列。

关键概念

"实现"符号序列：子序列的相邻元素关系形成的序列，可以通过重复符号序列并删除后缀得到。

例如：

• 符号序列 < > =
• 子序列关系可以是 < > = < > = < > 等
• 只要关系模式是 < > = 的循环重复

问题转化

这实际上是一个带模式约束的最长递增/递减/相等子序列问题。

算法思路

核心思想

使用动态规划结合线段树/树状数组来优化：

1. 状态定义：dp[i] 表示以第 i 个元素结尾的最长子序列长度

2. 转移方程：对于每个位置 i，我们需要找到前面满足当前符号要求的位置 j：

   • 如果当前符号是 <，找 a[j] < a[i] 且 dp 值最大的
   • 如果当前符号是 =，找 a[j] = a[i] 且 dp 值最大的
   • 如果当前符号是 >，找 a[j] > a[i] 且 dp 值最大的

3. 优化：直接遍历会超时，使用三个线段树分别维护：

   • 小于关系的最优解
   • 等于关系的最优解
   • 大于关系的最优解

符号循环处理

由于符号序列是循环使用的，当前应该使用哪个符号由 dp[i] % k 决定。

代码详解

#include <algorithm>
#include <stdio.h>
#include <vector>

typedef long long llt;
typedef unsigned uint;
typedef unsigned long long ullt;
typedef bool bol;
typedef char chr;
typedef void voi;
typedef double dbl;

// 通用工具函数
template<typename T>bol _max(T &a, T b) { return (a < b) ? a = b, true : false; }
template<typename T>bol _min(T &a, T b) { return (b < a) ? a = b, true : false; }

const uint Lim = 1u << 20;  // 线段树大小，支持值域到1000000

// 线段树类，用于维护区间最大值
struct Seg {
    std::pair<int, uint> Val[Lim << 1 | 1];  // 存储(长度, 前驱索引)
    
    Seg() {
        for (auto &v : Val) v = {-1, -1u};  // 初始化为无效值
    }
    
    // 单点更新
    voi chg(uint p, std::pair<int, uint> w) {
        uint a = 1, len = Lim;
        while (true) {
            _max(Val[a], w);  // 更新路径上的最大值
            if (len == 1) return;
            len >>= 1;
            a = (p < len) ? a << 1 : (p -= len, a << 1 | 1);
        }
    }
    
    // 区间查询
    std::pair<int, uint> find(uint l, uint r, uint p = 1, uint len = Lim) {
        if (l >= r) return {-1, 0};
        if (!l && r == len) return Val[p];  // 完全覆盖
        
        if (l < (len >> 1)) {
            if (r <= (len >> 1)) 
                return find(l, r, p << 1, len >> 1);
            else 
                return std::max(
                    find(l, len >> 1, p << 1, len >> 1),
                    find(0, r - (len >> 1), p << 1 | 1, len >> 1)
                );
        } else {
            return find(l - (len >> 1), r - (len >> 1), p << 1 | 1, len >> 1);
        }
    }
};

// 三个线段树分别处理不同关系
Seg A, B, C;  // A: <, B: =, C: >

uint P[500005];      // 存储整数序列
chr S[500005];       // 存储符号序列  
std::pair<int, uint> LastV[500005];  // 存储每个位置的最优解(长度, 前驱)

int main() {
    uint n, k;
    scanf("%u%u", &n, &k);
    
    // 读入数据
    for (uint i = 0; i < n; i++) scanf("%u", P + i);
    for (uint i = 0; i < k; i++) scanf("%s", S + i);
    
    std::pair<int, uint> ans{-1, 0};  // (最大长度, 结束位置)
    uint p = -1;  // 记录最优解的结束位置
    
    // 动态规划主循环
    for (uint i = 0; i < n; i++) {
        // 从三个线段树中查询最优前驱
        LastV[i] = std::max({
            A.find(0, P[i]),           // 找小于当前值的
            B.find(P[i], P[i] + 1),    // 找等于当前值的  
            C.find(P[i] + 1, 1000001)  // 找大于当前值的
        });
        
        LastV[i].first++;  // 长度+1
        
        // 更新全局最优解
        if (_max(ans, LastV[i])) p = i;
        
        // 根据当前长度确定使用哪个符号
        auto v = LastV[i];
        v.second = i;  // 记录前驱为当前索引
        
        chr c = S[v.first % k];  // 循环使用符号序列
        
        // 根据符号更新对应的线段树
        if (c == '<')
            A.chg(P[i], v);      // 更新小于关系的线段树
        else if (c == '=')
            B.chg(P[i], v);      // 更新等于关系的线段树
        else 
            C.chg(P[i], v);      // 更新大于关系的线段树
    }
    
    // 输出结果
    printf("%d\n", ans.first + 1);  // 输出最长长度
    
    // 回溯构造解
    std::vector<uint> A;
    while (~p) {  // 沿着前驱链回溯
        A.push_back(p);
        p = LastV[p].second;
    }
    
    // 输出子序列（注意要逆序输出）
    while (A.size()) {
        printf("%u", P[A.back()]);
        A.pop_back();
        putchar(" \n"[!A.size()]);  // 最后一个输出换行，其他输出空格
    }
    
    return 0;
}

算法流程详解

1. 初始化

• 三个线段树 A、B、C 分别初始化为最小值
• 读取整数序列和符号序列

2. 动态规划过程

对于每个位置 i：

1. 查询最优前驱：

   • 从线段树 A 查询 [0, P[i]) 区间（小于关系）
   • 从线段树 B 查询 [P[i], P[i]+1) 区间（等于关系）
   • 从线段树 C 查询 [P[i]+1, MAX] 区间（大于关系）
   • 取三者中的最大值

2. 更新当前状态：

   • dp[i] = max_value + 1
   • 记录前驱位置

3. 更新线段树：

   • 根据 dp[i] % k 确定下一个符号
   • 将当前状态更新到对应的线段树中

3. 输出结果

• 回溯前驱链构造解
• 逆序输出子序列

复杂度分析

• 时间复杂度：O(n log M)，其中 M 是值域大小（1000000）
• 空间复杂度：O(M)，主要是线段树的空间

关键技巧

1. 线段树优化：将 O(n²) 的 DP 优化到 O(n log M)
2. 三个线段树：分别处理三种不同的比较关系
3. 循环符号：通过取模运算实现符号序列的循环使用
4. 记录前驱：便于最后回溯构造解

总结

这道题的核心在于将模式约束的最长子序列问题转化为带条件的状态转移，并通过数据结构优化来降低复杂度。三个线段树的巧妙设计使得我们能够快速查询满足各种关系的最优前驱，是解决此类问题的经典方法。