题解 P7809【[JRKSJ R2] 01 序列】

· · 题解

\text{Link}

算法 1

针对 \text{Subtask 1}。

显然对于询问 1，答案为 r-l+1，对于询问 2，答案为 1。

时间复杂度 O(n+m)。期望得分 5\text{pts}。

算法 2

暴力求区间最长不降/上升子序列，时间复杂度 O(mn^2)。期望得分 10\text{pts}，结合算法 1 可得 15\text{pts}。

算法 3

设 pre_{x,i}=\sum_{j=1}^i[a_i=x]，（0\le x\le1，1\le i\le n）。

第一问：

其实本质是求 \max_{i=l}^r pre_{0,i}-pre_{0,l-1}+pre_{1,r}-pre_{1,i}。

怎么理解这个柿子呢？显然 pre 是前缀和的形式，所以 pre_{0,i}-pre_{0,l-1} 即 \sum_{j=l}^i[a_i=0]，pre_{1,r}-pre_{1,i} 即 \sum_{j=i+1}^r[a_i=1]。我们可以理解 i 为分界线，分界线前选 0，分界线后选 1，枚举所有 l\le i\le r，显然可以取到最大值，时间复杂度 O(mn)。

还需要特判只选 1 的情况，当然你也可以看为求 \displaystyle\max_{i=l-1}^rpre_{0,i}-pre_{0,l-1}+pre_{1,r}-pre_{1,i}。

第二问：

显然有答案为 1 或 2，答案为 2 时只有在有 0 在最后一个 1 前面，否则为 1。

于是我们考虑维护 bef_i 为 a_i=1 时 i 前最后一个 0 所在的位置，否则为 0。

答案显然为 1+[(\max_{i=l}^r bef_i)\ge l]，暴力枚举，时间复杂度 O(mn)。

总时间复杂度 O(mn)。期望得分 25\text{pts}。

算法 4

上面那个东西可以套路ST表处理，时间复杂度 O(n\log n+m)，期望得分 100\text{pts}。

当然开 2 个ST表常数较大。

用 +1-1RMQ 可以做到严格 O(n+m)，常数较大，不做为本题最优做法。

这里还有一个后来发现的一个减小常数方法：

发现第二问只有 1 和 2 两种答案，要有 2 则区间中必须出现连续的 0-1，于是我们维护 0-1 出现次数的前缀和，如果左端点前缀和等于右端点前缀和，则答案为 1，否则为 2。可以大大减小常数，如果实现优秀，则可以所有点进 1s。

#include<bits/stdc++.h>
using namespace std;
namespace IO{//by cyffff

}
const int N=1e6+10;
int n,m,st[20][N],lg[N],a[N],pre[N],pp[N];
inline int query(int l,int r){
    int q=lg[r-l+1];
    return max(st[q][l],st[q][r-(1<<q)+1]);
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    a[0]=2;
    int sum=0,o=0,z=0;
    for(int i=1;i<=n;i++){
        if(a[i]) sum--,o++;
        else sum++,z++;
        st[0][i]=z-o;
        pp[i]=o;
        pre[i]=pre[i-1]+(a[i]==1&&a[i-1]==0);
    }
    for(int i=2;i<=n;i++)
        lg[i]=lg[i>>1]+1;
    for(int i=1;i<=19;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            st[i][j]=max(st[i-1][j],st[i-1][j+(1<<i-1)]);
    for(int i=1;i<=m;i++){
        int opt=read(),l=read(),r=read();
        if(opt==1)
            write(max(pp[r]-pp[l-1],query(l,r)-(l-1-pp[l-1])+pp[r]));
        else
            write(1+!(pre[l]==pre[r]));
        putc('\n');
    }
    flush();
    return 0;
}

再见 qwq~

upd：好像赛时还被线段树过了，考虑加入主题库后缩小时限。