传送门@百度。。

treap好久没写果然有点生疏了，注意答案是long long

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 using namespace std;10 const int N = 500010;11 #define Ch1 (T[i].s[0])12 #define Ch2 (T[i].s[1])13 #define For(i,n) for(int i=1;i<=n;i++)14 #define Rep(i,l,r) for(int i=l;i<=r;i++)15 16 void read(int &v){17 char ch=getchar();18 int num=0;19 while(ch>'9'||ch<'0') ch=getchar();20 while(ch>='0'&&ch<='9'){21 num=num*10+ch-'0';22 ch=getchar();23 }24 v=num;25 }26 27 struct treap{28 int v,size,pri;29 int s[2];30 void Sets(int x,int y){v=x;pri=y;size=1;}31 }T[N];32 33 int n,x,cnt,root;34 long long ans;35 36 void Update(int i){37 T[i].size=T[Ch1].size+T[Ch2].size+1;38 }39 40 void Rot(int &y,int f){41 int x=T[y].s[!f];42 T[y].s[!f]=T[x].s[f];43 T[x].s[f]=y;44 Update(y);Update(x);45 y=x;46 }47 48 void Insert(int &i,int x){49 if(!i){50 T[i=++cnt].Sets(x,rand());51 T[i].s[0]=T[i].s[1]=0;52 return;53 }54 int f=T[i].v>x;55 Insert(T[i].s[!f],x);56 if(T[T[i].s[!f]].pri>T[i].pri) Rot(i,f);57 else Update(i); 58 }59 60 int find(int i,int x){61 if(T[i].v==x) return T[Ch1].size+1;62 if(T[i].v
             
              x) return find(Ch1,x);64 }65 66 int main(){67 while(read(n),n){68 ans=0;69 cnt=root=0;70 For(i,n){71 read(x);72 Insert(root,x); 73 ans+=i-(find(root,x)); 74 }75 cout<
              
               <