[일반] div2 c 질문

[익명(61.42)]

b c로 n^2 루프 돌리고

b 왼쪽에 있는 수들로 세그트리 하나

c 오른쪽에 있는 수들로 세그트리 하나 해서

업데이트 해가면서 쿼리 돌려줬는데

n^2*logn이라 안돌아가는거 같아요 어떻게 개선할수 있나요??

[익명(119.202)]

난 k보다 작은 값의 갯수를 prefix sum, suffix sum 을 N*N 테이블로 쫙 관리한다음에 내부 2개 선택을 2중for문을 하고, 테이블에서 O(1)로 픽업하는식으로 O(N^2) 했음