PS 이야기

0. 표지 1. horses 문제: 말을 한 번 팔 때, 모두 팔아버리는 것이 좋음을 알 수 있다. $i$번 해에 말을 파는게 제일 좋기 위한 필요조건은 $i 1$인 $i$들 중 30개 보다 앞에 있는 날에 말을 파는 것은 안좋다는 것을 알 수 있다. 결국 답으로 가능한 구간이 최대 30개 생기는 꼴인데 매 쿼리마다 각 구간 별로 최대 $Y[i]$를 인덱스트리나 세그먼트 트리로 구해놓은 다음에 말을 팔고 남은 최대 이익을 계산하면 된다. 그러면 하나의 쿼리를 $30 \lg N$ 에 조금 비례한 회수의 연산으로 해결할 수 있다. #include using namespace std; #define MAXN 500005 #define TS 1048576 #define pb push_back #define sz..