前言

传送门

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("");
    }
}