• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	

            misschuer
            

            

            


            
	
		

            常用鏈接
            

		

            統計
            
	
		

            積分與排名
            


		
		
            百事通
            
		
				
			
	

		

            最新評論
	
            

            
	
			
		

            
		
	

            

            
	
					
	
            
		
            
			hdu 2838 Cow Sorting
		
            
		http://acm.hdu.edu.cn/showproblem.php?pid=2838
            

            #include<iostream>
            #define MAX 100001
            #include             <algorithm>
            #define lowbit(x) (x&(-x))
            using namespace std;

            __int64 sum[MAX],tree[MAX];
            int sum1[MAX],tree1[MAX];
            typedef             struct
            {
                          int data;
                          int pos;
            }            point;

            bool GY (point a , point b)
            {
                          return a.data < b.data;
            }

            __int64 query(            int x)
            {
                __int64 sum             = 0;
                            while (x > 0)
                            {
                    sum             += tree[x];
                    x             -= lowbit(x);
                }
                            return sum;
            }

            void add(int a,int b,int n)
            {
                            while (a <= n)
                            {
                    tree[a]             += b;
                    a             += lowbit(a);
                }
            }


            int query1(int x)
            {
                            int sum = 0;
                            while (x > 0)
                            {
                    sum             += tree1[x];
                    x             -= lowbit(x);
                }
                            return sum;
            }

            void add1(int a,int b,int n)
            {
                            while (a <= n)
                            {
                    tree1[a]             += b;
                    a             += lowbit(a);
                }
            }


            int main()
            {
                            int n , i;
                __int64 ans , x , k;
                point p[ MAX ];
                            while (scanf("%d",&n) == 1)
                            {
                    tree[            0] = sum[0] = 0;
                    tree1[            0] = sum1[0] = 0;

                                for(i=1;i<=n;i++)
                                {
                        scanf(            "%d",&p[ i ].data);
                        p[ i ].pos             = i;
                        sum[i]             = sum[i-1] + p[ i ].data;
                        tree[i]             = sum[i] - sum[i - lowbit(i)]; 

                        sum1[i]             = sum1[i-1] + 1;
                        tree1[i]             = sum1[i] - sum1[i - lowbit(i)];
                    }
                    sort (p             + 1 , p + n + 1 , GY);

                    ans             = 0;
                                for (i = 1;i <= n;++ i)
                                {
                        k             = query (p[ i ].pos - 1);
                                    if (k)
                                    {
                           x             = query1 (p[ i ].pos - 1);
                           ans             = ans + k + x * p[ i ].data;
                        }
                       add (p[ i ].pos ,             - p[ i ].data , n);
                       add1 (p[ i ].pos ,             - 1 , n);
                    }             
                    printf (            "%I64d\n" , ans);
                }
                            return 0;
            }
            

		
            
			posted on 2010-03-26 12:21 此最相思 閱讀(514) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            






            

				

            



    
    







            
	   
	



久久久WWW免费人成精品|
精品无码久久久久久国产|
亚洲国产精品久久久久久|
18岁日韩内射颜射午夜久久成人|
91麻精品国产91久久久久|
99久久婷婷国产综合精品草原|
久久99精品久久久久久久不卡|
人妻无码αv中文字幕久久琪琪布|
久久精品人妻中文系列|
久久午夜夜伦鲁鲁片免费无码影视
|
色综合久久最新中文字幕|
国内精品久久久久影院日本|
性欧美大战久久久久久久久
|
人妻无码αv中文字幕久久琪琪布|
奇米影视7777久久精品|
精品综合久久久久久888蜜芽|
精品熟女少妇av免费久久|
一本伊大人香蕉久久网手机|
亚洲嫩草影院久久精品|
性做久久久久久久久|
国产成人精品久久|
久久国产高清字幕中文|
久久久人妻精品无码一区
|
国产精品无码久久综合|
国产免费久久精品99久久|
久久丝袜精品中文字幕|
一本一本久久A久久综合精品
|
99久久人妻无码精品系列蜜桃|
国产成人久久久精品二区三区|
麻豆久久|
狠狠狠色丁香婷婷综合久久五月|
久久精品国产亚洲av麻豆蜜芽|
国产成人综合久久久久久|
热久久最新网站获取|
久久婷婷国产麻豆91天堂|
思思久久好好热精品国产|
国产精品国色综合久久|
久久精品国产男包|
99久久精品国产麻豆|
久久久亚洲欧洲日产国码是AV|
久久精品国产亚洲麻豆|