//计算逆序数
	private static int solve(int[] array,int n) {
		int[] temp = new int[n];			
		return mergeSort(array,temp,0,n);
	}
	// 包括low,不包括high.
	private static int mergeSort(int[] src, int[] dest, int low, int high) {		
		int length = high - low;		
		if (length==1) return 0;		
		int mid = (low + high) >> 1;
		int c1 = mergeSort(src, dest, low, mid);
		int c2 = mergeSort(src, dest, mid, high);
		if (src[mid-1]<=src[mid]) {			
			return c1+c2;
		}
		int c3 = 0;		
		int i=low, p = low, q = mid;
		while(p<mid&&q<high) {
			if (src[p]<=src[q]) {
				dest[i++] = src[p++];
				c3 += (q-mid); 
			}				
			else {
				dest[i++] = src[q++];	
				//c3 += (mid-p); 
			}
		}
		while(p<mid) {
			dest[i++] = src[p++];
			c3 += (q-mid); 			
		}
		while(q<high) {
			dest[i++] = src[q++];			
		}
		System.arraycopy(dest, low, src, low, length);
		
		return c1+c2+c3;
	}

• int64 (976) achilles 2005-12-20 15:06:17
  • Re:int64 (54) liuyuyangfoam 2005-12-24 01:31:05
    • Re:int64 (63) lastone 2006-07-25 12:02:53