import java.util.Scanner; class Seg_Tree {//线段树节点 int left,right; int val;//区间内已插入的节点数 int calmid() { return (left+right)/2; } } public class Main{ private int LL(int x) { return x<<1;} //两倍; private int RR(int x) { return x<<1|1;} //两倍+1; Seg_Tree tt[]; public Main(){ tt=new Seg_Tree[16370];//用数组实现线段树 for(int i=0;i<16370;i++) tt[i]=new Seg_Tree(); } private void build(int left,int right,int idx) {//构建一棵val值全为0的线段树 tt[idx].left = left; tt[idx].right = right; tt[idx].val = 0; if(left == right) return ; int mid = tt[idx].calmid(); build(left,mid,LL(idx)); build(mid+1,right,RR(idx)); } /* 如果将节点全部插入,应该是下面结果: C:\java>java Main 10 1 3 6 9 0 8 5 7 4 2 [0,0]=.val=1 [0,1].val=2 [1,1].val=1 [0,2].val=3 [2,2].val=1 [0,4].val=5 [3,3].val=1 [3,4].val=2 [4,4].val=1 [0,9].val=10 [5,5].val=1 [5,6].val=2 [6,6].val=1 [5,7].val=3 [7,7].val=1 [5,9].val=5 [8,8].val=1 [8,9].val=2 [9,9].val=1 */ private void insert(int aim,int l,int r,int k){ //将aim插入到线段树 if(tt[k].left==aim&&tt[k].right==aim) { tt[k].val++;return ; } if(aim<=tt[k].calmid()) insert(aim,l,tt[k].calmid(),LL(k)); else insert(aim,tt[k].calmid()+1,r,2*k+1); tt[k].val=tt[LL(k)].val+tt[RR(k)].val; } public void printTree(int i){//中序遍历线段树 if(2*i>16370) return; printTree(2*i); if(tt[i].right!=0) System.out.print("["+tt[i].left+","+tt[i].right+"]"+".val="+tt[i].val+" ");//注意,没有输出[0,0] printTree(2*i+1); } //查询[left,right]中已插入的节点数 private int query(int left,int right,int idx){ if(left == tt[idx].left && right == tt[idx].right) return tt[idx].val; int mid = tt[idx].calmid(); if(right <= mid){ return query(left,right,LL(idx)); } else if(mid < left) { return query(left,right,RR(idx)); } else { return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx)); } } public static void main(String[] args){ Scanner in=new Scanner(System.in); int n; while(in.hasNext()) { n=in.nextInt(); Main ma=new Main(); int val[]=new int[n]; ma.build(0,n-1,1); int sum = 0; for(int i=0;i<n;i++){ val[i]=in.nextInt(); sum += ma.query(val[i],n-1,1);//先查询 ma.insert(val[i],0,n-1,1);//后插入 } // ma.printTree(1); // System.out.println();//中序遍历线段树 // System.out.println(sum); int ret = sum; for(int i=0;i<n;i++){ sum = sum - val[i] + (n - val[i] - 1); ret=Math.min(ret,sum); } System.out.println(ret); } } }
0票
开心
0票
板砖
0票
感动
0票
有用
0票
疑问
0票
难过
0票
无聊
0票
震惊
顶
踩