boj 1280 나무심기 [bit]

참조 

http://sksdong.egloos.com/6062255

https://fullalgorithmpanic.blogspot.kr/2016/10/boj-1280.html

한참 풀다 안되어서 구글링했다..

이런..ㅠㅠ

X의 좌측에 있는 나무를 고려해보면 (현재 x의 위치 * x보다 왼쪽에 있는 나무의 갯수 ) - (x보다 왼쪽에 있는 모든 나무의 거리 합)

을 하게 되면 모든 나무에서 x로의 거리가 나온다. ( 위의 계산에서 x보다 왼쪽에 있는 모든 나무 거리는 0부터 해당 나무까지 거리의 합이다.)

현재 x의 위치 * x 보다 왼쪽에 있는 나무의 개수

C++하면 성공인데.. java로 하면 실패다..

뭐때문일까??

문제는 int type 때문..ㅠㅠ 결과가 long value이네..ㅠㅠ

import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; public class boj1280 { static int N; static long[] cnt, val; static int MOD = 1000000007; static int MAX_N = 200002; static void add(int h, int v, long[] ar) { for (int i = h; i <= MAX_N; i+=(i&-i)) ar[i]+=v; } static long sum(int h, long[] ar) { long result = 0; for (int i = h; i > 0; i-=(i&-i)) result+=ar[i]; return result; } public static void main(String[] args) throws IOException { System.setIn(new FileInputStream("res/input1280.txt")); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); val = new long[MAX_N+1]; cnt = new long[MAX_N+1]; int v; long ret = 1; for (int i = 0; i < N; i++) { v = Integer.parseInt(br.readLine()); v++; //입력으로 0이 주어지는데 펜윅트리에서는 0을 사용할 수 없다.        if(i!=0){            long p = ((sum(v-1,cnt)*v)-sum(v-1,val)+sum(MAX_N-1,val)-sum(v,val)-(sum(MAX_N-1,cnt)-sum(v,cnt))*v)%MOD;            ret=(ret*p)%MOD;        }        add(v,1,cnt);        add(v,v,val); } System.out.println(ret); } }