만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

수열과 구간과 구간과 구간과 쿼리

시간 제한5초메모리 제한1024 MB

요약
수열이 주어질 때, 각 질의마다 시작 위치가 a 이상 b 이하이고 끝 위치가 c 이상 d 이하인 구간 중 평균이 가장 큰 값의 정수 부분을 구합니다.
난이도

어려움10점 중 9점

유형
이분 탐색, 누적 합, 기하, 세그먼트 트리
정답자
아직 제출이 없습니다

문제

길이가 NN인 정수 수열 A_1,A_2,...,A_NA\_1, A\_2, ..., A\_N이 주어진다. 이때, 다음 쿼리를 처리하는 프로그램을 작성하시오.

  • a,b,c,da, b, c, d: a≤x≤ba\leq x\leq b, c≤y≤dc\leq y\leq d를 만족하는 두 정수 x,yx, y에 대해 부분 수열 A_x,A_x+1,...,A_yA\_x, A\_{x+1}, ..., A\_y의 평균의 최댓값을 출력한다.

입력

첫째 줄에 수열의 길이 N(1≤N≤100,000)N(1 \leq N \leq 100,000)과 쿼리의 개수 Q(1≤Q≤30,000)Q(1 \leq Q \leq 30,000)가 주어진다.

둘째 줄에는 A_1,A_2,...,A_NA\_1, A\_2, ..., A\_N이 주어진다. (1≤A_i≤108)(1 \leq A\_i \leq 10^8)

셋째 줄부터 QQ개의 줄에 쿼리 a,b,c,da, b, c, d가 한 줄에 하나씩 주어진다. (1≤a≤b≤c≤d≤N)(1 \leq a \leq b \leq c \leq d \leq N)

출력

각 쿼리의 정답을 한 줄에 하나씩 출력한다. 답은 소수점 이하를 버려 정수로 출력한다.

예제1

  1. 예제 1

    입력
    5 3
2 5 6 5 2
1 1 1 1
1 3 3 5
1 2 5 5
    예상 출력
    2
6
4