P7809 01 序列

01 序列：把子序列状态压缩成可合并信息

问题

P7809 [JRKSJ R2] 01 序列
给定一个静态 01 序列，多次查询区间最长不下降子序列或最长上升子序列的长度。

数据规模：$n\le 10^6$，$m\le 5\times 10^6$。

看到 LIS 和 LNDS，其实第一反应是 DP 模型，但这个多次询问就很麻烦了，观察发现本题的值域只有 $0$ 和 $1$，所以状态数是很有限的。

可以直接枚举，比如说 LIS 最长只有 0 -> 1，LNDS 也只有三种情况 00...0，11...1，00...1。于是发现，一个区间只需要维护四个量：cnt0、cnt1、lis 和 lnds。

考虑线段树的做法，两个区间应该如何合并。设相邻两段分别为 $A$ 和 $B$，对于 LIS 来说，只要 A 中有 0，且 B 中有 $1$，就可以凑长度为 $2$，或者直接继承 A 和 B 中较长的那一段 LIS。

对于 LNDS 来说，$0/1$ 的分界点只有两个位置，若分界点在 $A$ 中，则此时可以取 $A.lnds + B.cnt1$，若分界点在 $B$ 中，则此时可以取 $A.cnt0 + B.lnds$。

于是就可以线段树维护了，但是本题查询量极大，所以如果要用线段树，需要使用迭代版本优化常数。

时间复杂度为 $O(n+m\log n)$，空间复杂度为 $O(n)$。

▶

P7809

struct SegTree {
/* ======================================== */
struct Node { 
    int cnt0, cnt1;
    int lis, lnds;
} tr[maxn << 2];

int base;

Node merge( const Node &A, const Node &B ) {
    Node res;
    res.cnt0 = A.cnt0 + B.cnt0;
    res.cnt1 = A.cnt1 + B.cnt1;
    res.lnds = max( A.lnds + B.cnt1, A.cnt0 + B.lnds );
    res.lis = max( A.lis, B.lis );
    if( A.cnt0 > 0 && B.cnt1 > 0 ) res.lis = max( res.lis, 2 );
    return res;
}

void build( int n, int val[] ) {
    base = 1;
    while( base < n ) base <<= 1;
    for( int i = 1; i <= n; ++ i ) {
        Node &cur = tr[base + i - 1];
        cur.cnt0 = ( val[i] == 0 );
        cur.cnt1 = ( val[i] == 1 );
        cur.lis = cur.lnds = 1;
    }
    for( int i = base - 1; i >= 1; -- i ) {
        tr[i] = merge( tr[i << 1], tr[i << 1 | 1] );
    }
}

Node ask( int l, int r ) {
    l += base - 1, r += base - 1;
    Node L = { }, R = { };
    while( l <= r ) {
        if( l & 1 ) {
            L = merge( L, tr[l] );
            l ++;
        }
        if( !( r & 1 ) ) {
            R = merge( tr[r], R );
            r --;
        }
        l >>= 1, r >>= 1;
    }
    return merge( L, R );
}
/* ======================================== */
} seg;

int a[maxn];

void solve( ) {
    int n = read( ), m = read( );
    for( int i = 1; i <= n; ++ i ) a[i] = read( );

    seg.build( n, a );

    for( int i = 1; i <= m; ++ i ) {
        int t = read( ), l = read( ), r = read( );
        if( t == 1 ) printf( "%d\n", seg.ask( l, r ).lnds );
        else printf( "%d\n", seg.ask( l, r ).lis );
    }
}

注：线段树部分已经 “溶解”。

当然其实本题正解不是线段树，我们发现枚举某一段的 LNDS 只与前缀 0 和 后缀 1 的数量有关，不妨预处理 $Pre0$ 和 $Pre1$。

假设在 $k$ 点分割，那么答案就是 $\displaystyle \max_{l \le k \le r}(Pre0[k] - Pre0[l-1] + Pre1[r] - Pre1[k])$，而枚举的变量是 $k$，所以另外两项对于每次查询都是常数，可以预处理。

发现只要维护 $Dif[k] = Pre0[k] - Pre1[k]$，然后对于每一次查询，都维护一个区间最值即可，由于没有动态修改，不难想到本题正解其实是 ST 表。

注：这种情况下 $k$ 的枚举范围为 $[l-1, r]$，左边界表示一个 $0$ 都不选，右边界表示一个 $1$ 都不选。

实现略。

记录

• 归属：线段树信息合并、[[ST 表]]
• 新增：小值域使一般 LIS 状态压缩成有限的子序列形态；设计线段树信息时，应先写出跨越左右区间的合法答案如何组成。
• 分类：待定