오토에버 3번 세그먼트 트리로 푼애들 뭐냐

[익명(194.195)]

세그먼트 트리로 풀려면 lazy propagation 써야 할것 같던데

이렇게 풀면 거의 백준 플레급 난이도로 접근한거 아니냐?

누적합으로 푸니까 그냥 실버 수준이던데

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(116.38)]

N log N 까지 들어옴

[익명(114.205)]

누적합으로 dp쓰면 뭘해도 연산량이 천만번 안됨. 고로 1초는 넉넉하게 떡을 침

[익명(211.37)]

누적합은 뭐임?

[익명(116.38)]

세그먼트도 임 ㅇㅇ N log N 쳐도 천만임

[익명(114.205)]

걍 누적합이 맞아. 그러라고 나온 문제임. 세그트리는 뭐... 쓰겠다는데 어쩔.

[익명(114.205)]

20만개의 배열에 20만번 연산이 들어오는데 dp저장까지 2n으로 40만번 연산하고 각 도장 횟수도 dp쓰면 연산당 5번을 안넘음 고로 천만번의 얀산이 안필요함. 고로 널널하다

[익명(116.38)]

대충 수도코드 가능? 다시 풀어보게

[익명(211.179)]

아 누적합이었네 생각을 못했다 빡대가리