#P5442. [Ceoi2018]Global warming

    ID: 2796 传统题 1000ms 256MiB 尝试: 174 已通过: 76 难度: 7 上传者: 标签>CF2200提高最长上升子序列前后缀状态分解线性 DP树状数组离散化

[Ceoi2018]Global warming

[CEOI2018] Global warming

题目描述

给定长度为 nn 的整数序列 aa。选择一个非空区间 [l,r][l,r](1≤l≤r≤n1\le l\le r\le n)和一个整数 dd(−x≤d≤x-x\le d\le x),给区间中的每个元素同时加上 dd。允许选 d=0d=0。求执行这次操作后,严格上升子序列长度的最大值。子序列中的元素可以来自不连续的位置。

输入格式

第一行两个整数 n,xn,x。

第二行 nn 个整数表示 a1a_1 至 ana_n。

输出格式

一个数,即 aa 数组的最大严格上升子序列长度。

样例 #1

样例输入 #1

8 10
7 3 5 12 2 7 3 4

样例输出 #1

5

提示

对于 100%100\% 的数据,1≤n≤2×1051\le n\le2\times10^5,0≤x≤1090\le x\le10^9,1≤ai≤1091\le a_i\le10^9。

题目来源