P7809 [JRKSJ R2] 01 序列 题解

· · 题解

前言

传送门

blog

思路

Problem 1

问题一问的是最长不下降子序列的长度，在一个 01 串中的最长不下降子序列，总共有三种 000\dots，000\dots111\dots 和 111111\dots。

可以把找到以上三种最长不下降子序列问题变为：

\max^r_{i =l}(\sum_{j = l}^i[a_j=0])+(\sum_{j = i + 1}^r[a_j=1])

可以看做以 i 分界，l 到 i 为 0，i + 1 到 r 为 1。

那么我们又可以使用前缀和优化，设 sumfront_y 为从 1 到 y 的 0 的个数，sumback_y 为从 n 到 y 的 1 的个数，上式可以简化为：

\max^r_{i =l}sumfront_i-sumfront_{l-1}+sumback_i-sumback_{r + 1}

再次优化

上式中 sumfront_{l-1} 与 sumback_{r + 1} 已经固定，所以我们要求的就是 \max^r_{i =l}sumfront_i+sumback_i

算区间最大值的我们使用 st 表优化。

AC Code

#include <bits/stdc++.h>
using namespace std;

inline int read(){
    int x = 0,f = 1;char ch = getchar();
    while (ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

int n,m;
bool a[1000010];
int sum[1000010],sum_front[1000010],sum_back[1000010];
int LOG2[1000010],st[1000010][21];

void init(){
    for(int i = 2;i <= n;++i)
        LOG2[i] = LOG2[i >> 1] + 1;
    for(int i = 1;i <= n;++i)
        st[i][0] = sum_front[i] + sum_back[i];
    int k = LOG2[n];
    for(int i = 1;i <= k;++i)
        for(int j = 1;j + (1 << i) - 1 <= n;++j)
            st[j][i] = max(st[j][i - 1],st[j + (1 << i - 1)][i - 1]);
}

int get(int l,int r){
    int s = LOG2[r - l + 1];
    return max(st[l][s],st[r - (1 << s) + 1][s]);
}

int main(){
    n = read(),m = read();
    for(int i = 1;i <= n;++i){
        a[i] = read();
        sum_front[i] = sum_front[i - 1] + (a[i] == 0);
        if(i > 1)sum[i] = sum[i - 1] + (a[i] == 1 && a[i - 1] == 0);
    }
    for(int i = n;i >= 1;--i)
        sum_back[i] = sum_back[i + 1] + (a[i] == 1);
    init();
    for(int i = 1;i <= m;++i){
        int problem,l,r;
        problem = read(),l = read(),r = read();
        if(problem == 1)
            printf("%d",get(l,r) - sum_front[l - 1] - sum_back[r + 1]);
        else 
            printf("%d",1 + !(sum[l] == sum[r]));
        puts("");
    }
}