#P6672. [2019年3月雅礼集训]duliu

    ID: 6522 传统题 2000ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-排序与序列处理一维前缀和数据结构普通并查集动态规划有限候选集缩减二分查找离线与分治离线查询事件排序普通线段树CF2600

[2019年3月雅礼集训]duliu

[2019年3月雅礼集训]duliu

题目描述

有 nn 道题,编号为 11 到 nn,第 ii 道题的难度为 did_i。定义两道题 j,kj,k 的函数值为

f(j,k)=dj+dk.f(j,k)=d_j+d_k.

给定 mm 次询问。每次询问给出 l,r,xl,r,x,你需要选择一个非空连续区间 [a,b][a,b],满足 l≤a≤b≤rl\le a\le b\le r,并且

∑j=ab∑k=abf(j,k)≥x.\sum_{j=a}^{b}\sum_{k=a}^{b} f(j,k)\ge x.

求所选区间中最大难度 max⁡a≤i≤bdi\max_{a\le i\le b}d_i 的最小可能值。如果不存在满足条件的区间,输出 −1-1。

这里 j,kj,k 独立遍历整个区间,计算的是所有有序题目对,包含 j=kj=k 的情况。因此,上面的求和也等于

2(b−a+1)∑i=abdi.2(b-a+1)\sum_{i=a}^{b}d_i.

每次询问独立,不改变题目的难度。

输入格式

第一行两个整数 n,mn,m,分别表示题目数量和询问数量。

第二行 nn 个正整数 d1,d2,…,dnd_1,d_2,\ldots,d_n。

接下来 mm 行,每行三个整数 l,r,xl,r,x,表示一次询问。

输出格式

对于每次询问,输出一行一个整数,表示答案;若无解,输出 −1-1。

样例输入 1

5 2
1 1 2 3 4
1 5 2
1 5 11

样例输出 1

1
2

样例输入 2

5 4
1 3 2 4 6
1 3 3
1 3 2
2 4 10
1 1 1556528051

样例输出 2

2
1
3
-1

数据范围

所有数据满足 1≤n≤3×1051\le n\le3\times10^5,0≤m≤3×1050\le m\le3\times10^5,1≤di≤1071\le d_i\le10^7,1≤l≤r≤n1\le l\le r\le n,1≤x≤10181\le x\le10^{18}。

子任务 分值 附加限制
1 6 分 n,m≤300n,m\le300
2 15 分 n,m≤5000n,m\le5000
3 18 分 n,m≤50000n,m\le50000
4 1 分 m=0m=0
5 所有 di≤1d_i\le1
6 10 分 所有 di≤2d_i\le2
7 11 分 所有 di≤3d_i\le3
8 7 分 所有询问的 x=1x=1
9 11 分 所有询问的 l=1,r=nl=1,r=n
10 20 分 无