뉴비의 PS 낙서장

2차원 배열이 있다고 생각해보면 위에서 아래로 누적합을 한번 하고 왼쪽에서 오른쪽으로 누적합을 한번한다면, 누적합 배열이 만들어 진다. 이제 그러면 포함-배제의 원리를 이용하여 누적합 배열을 채우면 O(2048N) 으로 시간초과가 나지만 이제 11차원으로 늘려보면 11번의 뱡향으로 밀면 된다는 것을 알 수 있다. 그래서 저 방법을 사용하면 O(11N) 으로 11차원 누적합 배열을 전처리 할 수 있다. Do : 지금 쿼리가 a[ret[0][0]~ret[0][1]][ret[1][0]~ret[1][1]] ... [ret[10][0]~ret[10][1]] 일때 값 구하기, 포함-배제의 원리를 사용하는 2차작업 f : 포함-배제의 원리를 사용하는 1차작업 쿼리를 처리할때는 포함-배제의 원리를 사용해도 시간이 충분..