CF869div2 C. Almost Increasing Subsequence

落日映苍穹つ 2024-03-22 11:33 31阅读 0赞

[Problem - C - Codeforces][]

题意：

![967e89b3f5584dafb5a3e8b721e277fc.png][]

思路：

关注特殊点：

保留最长的

三元组

对于三元组，删去中间那个元素就破坏了三元组

保留最长的：删除所有三元组中中间那个元素

每次询问都是求区间内最长的保留的元素个数

那么搞一下前缀和就好了

注意对于每次询问两边的不要算

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    
    int N,Q,l,r;
    int a[mxn],f[mxn],sum[mxn];
    
    void solve(){
    	cin>>N>>Q;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	for(int i=2;i<=N-1;i++){
    		if(a[i]<=a[i-1]&&a[i]>=a[i+1]) f[i]=1;
    	}
    	for(int i=1;i<=N;i++) sum[i]=sum[i-1]+f[i];
    	sum[N]=sum[N-1];
    	while(Q--){
    		cin>>l>>r;
    		int ans=r-l+1-(sum[r]-sum[l]);
    		if(f[r]) ans++;
    		cout<<min(ans,r-l+1)<<'\n';
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1818/problem/C
[967e89b3f5584dafb5a3e8b721e277fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/8094b8970112433a9ddeb2b02959ea49.png

发表评论取消回复

表情：

评论列表（有 0 条评论，31人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF869div2 C. Almost Increasing Subsequence

[Problem - C - Codeforces][] 题意： ![967e89b3f5584dafb5a3e8b721e277fc.png][] 思路：关注特殊点

落日映苍穹つ/ 2024年03月22日 11:33/ 0 赞/ 32 阅读

相关【二分or双指针】CF856div2 C. Scoring Subsequences

感觉对CF的套路题稍微有点感觉了考虑特殊条件性质就好了.... [Problem - C - Codeforces][] 题意：定义一个序列的分数为s1\s2\s3

布满荆棘的人生/ 2024年03月22日 10:36/ 0 赞/ 59 阅读

相关 CF#692 div2

A 从后往前找连续)最长长度判断是否大于n/2即可 B 一个数字只会出现1-9，而1-9的最小公倍数为7560 所以你最多自增7560个数后必能找到符合条件的数，所以暴力模拟

缺乏、安全感/ 2022年12月29日 06:47/ 0 赞/ 177 阅读

相关 [leetcode] 491. Increasing Subsequences

Given an integer array, your task is to find all the different possible increasing subse

我不是女神ヾ/ 2022年09月30日 06:48/ 0 赞/ 126 阅读

相关 LeetCode300——Longest Increasing Subsequence

LeetCode300——Longest Increasing Subsequence 题意：最长上升子串，LIS问题，经典的动态规划问题。据说有用到二分的方法，这个还没

青旅半醒/ 2022年08月09日 19:30/ 0 赞/ 59 阅读

相关 leetcode 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

今天药忘吃喽~/ 2022年07月28日 01:20/ 0 赞/ 159 阅读

相关 Longest Increasing Subsequence————LIS个数

Longest Increasing Subsequence 描述给出一组长度为nn的序列，a1,a2,a3,a4...an a 1 , a 2 , a 3 , a

水深无声/ 2022年05月17日 13:04/ 0 赞/ 152 阅读

相关 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

梦里梦外;/ 2022年03月06日 04:34/ 0 赞/ 190 阅读

相关 Longest Increasing Continuous subsequence II

Give you an integer matrix (with row size n, column size m)，find the longest increasing

本是古典何须时尚/ 2021年12月17日 10:27/ 0 赞/ 144 阅读

相关 300.Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

迈不过友情╰/ 2021年10月01日 04:34/ 0 赞/ 237 阅读