CF1832D2.Red-Blue Operations (Hard Version)
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
The only difference between easy and hard versions is the maximum values of n and q .
You are given an array, consisting of n integers. Initially, all elements are red.
You can apply the following operation to the array multiple times. During the i -th operation, you select an element of the array; then:
- if the element is red, it increases by i and becomes blue;
- if the element is blue, it decreases by i and becomes red.
The operations are numbered from 1 , i. e. during the first operation some element is changed by 1 and so on.
You are asked q queries of the following form:
- given an integer k , what can the largest minimum in the array be if you apply exactly k operations to it?
Note that the operations don't affect the array between queries, all queries are asked on the initial array a .
输入格式
The first line contains two integers n and q ( 1≤n,q≤2⋅105 ) — the number of elements in the array and the number of queries.
The second line contains n integers a1,a2,…,an ( 1≤ai≤109 ).
The third line contains q integers k1,k2,…,kq ( 1≤kj≤109 ).
输出格式
For each query, print a single integer — the largest minimum that the array can have after you apply exactly k operations to it.
输入输出样例
输入#1
4 10 5 2 8 4 1 2 3 4 5 6 7 8 9 10
输出#1
3 4 5 6 7 8 8 10 8 12
输入#2
5 10 5 2 8 4 4 1 2 3 4 5 6 7 8 9 10
输出#2
3 4 5 6 7 8 9 8 11 8
输入#3
2 5 2 3 10 6 8 1 3
输出#3
10 7 8 3 3