P7809 [JRKSJ R2] 01 序列题解

Scorilon / 2023-08-30 / 原文

对于第二种操作，很容易想到只有 \(1\) 或 \(2\) 两种答案，若该区间内存在 \(01\) 这个子序列，那么答案为 \(2\) 反之为 \(1\).可以通过对该 \(01\) 串做一个前缀和，若出现 \(01\) 这个子序列就累加，最后判断左右端点是否相等即可，时间复杂度 \(O(n)\).

对于第一种操作，\(\text{Subtest 1}\) 很明显答案为 \(r-l+1\).

然后考虑正解，很明显该最长不下降子序列形如 \(0,0,0,\dots,1,1,1\)，即由若干个连续的 \(0\) 和若干个连续的 \(1\) 构成，基于这一点，我们可以做一个前缀和，统计到 \(i\) 时 \([1,i]\) 中 \(0\) 和 \(1\) 的数量，那么答案就是 \(\max^r_{i=l} sum_{i,0}-sum_{l-1,0}+sum_{r,1}-sum_{i-1,1}\)，而 \(sum_{r,1}-sum_{l-1,0}\) 很明显是定值，那么只需要求最大的 \(sum_{i,0}-sum_{i-1,1}\) 即可，可用 ST 表维护，时间复杂度为 \(O(n\log n)\).

因此总时间复杂度为 \(O(n \log n+m)\)，足以通过本题。

#include <cstdio>
#include <iostream>
//#include<bits/stdc++.h>

using namespace std;

namespace IO{//by cyffff
	int len=0;
	char ibuf[(1<<20)+1],*iS,*iT,out[(1<<26)+1];
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
	#define reg register
	inline int read(){
		reg char ch=gh();
		reg int x=0;
		reg char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
	inline void putc(char ch){
		out[len++]=ch;
	}
	template<class T>
	inline void write(T x){
		if(x<0)putc('-'),x=-x;
		if(x>9)write(x/10);
		out[len++]=x%10+48;
	}
	inline void flush(){
		fwrite(out,1,len,stdout);
		len=0;
	}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::putc;

const int N=1e6;
const int M=5e6;
const int Log=20;

int n,m;
int sum[N+5][2];
int sum2[N+5];
int f[N+5][Log];
int log[N+5];

void init() {
	log[0]=log[1]=0;
	for(int i=2;i<=n;i++) log[i]=log[i>>1]+1;
}

int query(int l,int r) {
	int s=log[r-l+1];
	return max(f[l][s],f[r-(1<<s)+1][s]);
}

int main() {
	n=read();m=read();
	init();
	int lst=-1,a;
	for(int i=1;i<=n;i++) {
		a=read();
		sum[i][0]=sum[i-1][0];
		sum[i][1]=sum[i-1][1];
		sum[i][a]++;
		sum2[i]=sum2[i-1]+(lst==0&&a==1);
		lst=a;
	}
	for(int i=1;i<=n;i++) f[i][0]=sum[i][0]-sum[i-1][1];
	for(int j=1;j<=Log;j++) {
		for(int i=1;i+(1<<j)-1<=n;i++) {
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	int op,l,r;
	while(m--) {
		op=read();l=read();r=read();
		int ans=0;
		if(op==1) {
			ans=max(1,sum[r][1]-sum[l-1][0]+query(l,r));
			write(ans);putc('\n');
		} else {
			int x;
			if(sum2[l]==sum2[r]) x=1;
			else x=2;
			write(x);putc('\n');
		}
	}
	flush();
	return 0;
}