JZTXT

【题解】CF1817 合集

发布时间 2023-09-19 21:18:54作者: ricky_lin

CF1817A Almost Increasing Subsequence

考虑几乎上升的序列的长度，就是我们的区间长度减去 \(a_{i-2} \geq a_{i-1} \geq a_i\) 的对数，然后维护即可，当然个人感觉自己的代码有点长，可以考虑看洛谷题解代码

code:

#include<bits/stdc++.h>
using namespace std;
const int NN = 2e5 + 8;
int n,q;
int a[NN];
int pre[NN],cnt[NN],ck[NN];
int main(){
//	freopen("1.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);
	for(int i = 1; i <= n; ++i){
		if(i < n && a[i] >= a[i+1]) pre[i] = 1,ck[i] = 1;
		if(i < n && a[i] >= a[i+1] && a[i-1] < a[i]) cnt[i] = 1;
		pre[i] += pre[i-1];
		cnt[i] += cnt[i-1];
	}
//	for(int i = 1; i <= n; ++i) printf("%d ",pre[i]);puts("");
//	for(int i = 1; i <= n; ++i) printf("%d ",cnt[i]);puts("");
	while(q--){
		int l,r;
		scanf("%d%d",&l,&r);
		if(l == r){puts("1");continue;}
		if(l == r-1){puts("2");continue;}
		printf("%d\n",(r-l+1) - (pre[r-1] - pre[l-1]) + (cnt[r-1] - cnt[l] + ck[l]));
	}
}