前言
思路
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("");
}
}