#P7139. [2023测试]序列

    ID: 6969 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 6 上传者: 标签>动态规划贪心数据结构栈CF2000堆排序模拟

[2023测试]序列

序列

题目描述

给定序列 a1,…,ana_1,\ldots,a_n,以及参数 X,AX,A。选择一个子序列,其下标依次为 1≤p1<p2<⋯<pk≤n1\le p_1<p_2<\cdots<p_k\le n。若对每个 i=1,2,…,ni=1,2,\ldots,n 都有

A−iX+∑j:pj≤i(apj+X)≥0,A-iX+\sum_{j:p_j\le i}(a_{p_j}+X)\ge0,

则称这个子序列为优秀的。

等价地,从数值 AA 开始,依次处理每个位置:选入的位置加上 aia_i,未选入的位置减去 XX;每处理完一个位置,当前数值必须非负。

给定分段端点 b0=0<b1<⋯<bm=nb_0=0<b_1<\cdots<b_m=n 和阈值 hih_i。记第 ii 段未选入的位置数为

ci=bi−bi−1−#{j:bi−1<pj≤bi}.c_i=b_i-b_{i-1}-\#\{j:b_{i-1}<p_j\le b_i\}.

优秀子序列的价值是满足 ci≥hic_i\ge h_i 的段数,即

∑i=1m[ci≥hi].\sum_{i=1}^{m}[c_i\ge h_i].

其中方括号表示条件成立取 11,否则取 00。求价值最大的优秀子序列。

输入格式

第一行四个整数 n,m,X,An,m,X,A。

第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

接下来 mm 行,第 ii 行两个整数 bi,hib_i,h_i。

输出格式

第一行输出最大价值。

第二行输出所选子序列长度 kk。

第三行输出递增的下标 p1,…,pkp_1,\ldots,p_k;k=0k=0 时输出空行。若有多个方案,输出任意一个。

若第一行正确且输出格式正确,可以获得 40% 的分数。

样例输入

5 3 3 3
7 1 0 1 2
1 1
3 1
5 2

样例输出

2
2
1 2

样例说明

选择位置 1,21,2,三段未选入的位置数依次为 0,1,20,1,2,故价值为 0+1+1=20+1+1=2。

数据范围

  • 测试点 1、2:n≤20n\le20。
  • 测试点 3、4:n≤100n\le100,X,ai≤10X,a_i\le10。
  • 测试点 5:所有 aia_i 相等。
  • 测试点 6:n≤500n\le500,m≤18m\le18。
  • 测试点 7、8:n≤500n\le500。
  • 对于全部数据,1≤n≤500001\le n\le50000,1≤m≤501\le m\le50,0≤ai,X,A≤100000\le a_i,X,A\le10000,bi<bi+1b_i<b_{i+1},bm=nb_m=n。