멋진 구간

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

요약
각 i에서 A[i] ≤ C[i] ≤ B[i]인 배열 C가 [l, r]에서 최대 부분합을 갖도록 하는 (l, r) 쌍의 수를 구간 질의에 답하며 센다.
난이도

어려움10점 중 9점

유형
세그먼트 트리, 동적 계획법, 누적 합, 분할 정복
정답자
아직 제출이 없습니다

문제

지후는 정수로 이루어진 길이 NN의 배열 AA, BB를 가지고 있다. 모든 정수 0≤i≤N−10 \le i \le N-1에 대해 A\[i]≤B\[i]A\[i] \le B\[i]를 만족한다.

다음 조건을 모두 만족하는 \[l,r]\[l, r]을 멋진 구간이라고 정의한다:

  • ll, rr은 정수

  • 0≤l≤r≤N−10 \le l \le r \le N-1

  • 다음 조건을 모두 만족하는 정수로 이루어진 길이 NN의 배열 CC가 존재한다:

    • 모든 정수 0≤i≤N−10 \le i \le N-1에 대해, A\[i]≤C\[i]≤B\[i]A\[i] \le C\[i] \le B\[i]
    • 모든 정수 0≤s≤e≤N−10 \le s \le e \le N-1에 대해, ∑_i=lrC\[i]≥∑_i=seC\[i]\sum\_{i=l}^{r} C\[i] \ge \sum\_{i=s}^{e} C\[i]. 즉, C\[l…r]C\[l \ldots r]은 CC의 최대 합 부분 배열(부분 배열 중 원소의 합이 가장 큰 부분 배열)이다.

지후는 멋진 구간이 얼마나 있는지 궁금해졌다.

구체적으로, 지후의 궁금증은 00부터 Q−1Q-1까지의 번호가 붙은 QQ개의 질문으로 구성되어 있으며, 이는 정수로 이루어진 길이 QQ의 배열 L1L1, R1R1, L2L2, R2R2로 표현된다.

jj (0≤j≤Q−10 \le j \le Q-1)번 질문은 다음과 같다: L1\[j]≤l≤R1\[j]L1\[j] \le l \le R1\[j]와 L2\[j]≤r≤R2\[j]L2\[j] \le r \le R2\[j]를 모두 만족하는 멋진 구간 \[l,r]\[l, r]은 몇 개인가?

여러분은 지후의 질문들에 답하는 프로그램을 작성해야 한다.

제한

  • 1≤N,Q≤250,0001 \le N, Q \le 250\\,000
  • 모든 정수 0≤i≤N−10 \le i \le N-1에 대해 −109≤A\[i]≤B\[i]≤109-10^{9} \le A\[i] \le B\[i] \le 10^{9}
  • 모든 정수 0≤j≤Q−10 \le j \le Q-1에 대해 0≤L1\[j]≤R1\[j]≤N−10 \le L1\[j] \le R1\[j] \le N-1
  • 모든 정수 0≤j≤Q−10 \le j \le Q-1에 대해 0≤L2\[j]≤R2\[j]≤N−10 \le L2\[j] \le R2\[j] \le N-1

예제

이 문제는 공개된 예제가 없습니다.