对于第二种操作,很容易想到只有 \(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;
}
标签:01,log,R2,int,题解,sum,IO,using
From: https://www.cnblogs.com/Scorilon/p/17666149.html