• <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
            

            

            


            
	
		

            常用鏈接
            

		

            統(tǒng)計(jì)
            
	
		

            積分與排名
            


		
		
            百事通
            
		
				
			
	

		

            最新評(píng)論
	
            

            
	
			
		

            
		
	

            

            
	
					
	
            
		
            
			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) 評(píng)論(0)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            



            


            

	
            
		
		
            只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
            
		
            
		
				
		
		
		
            
		
            			
		
		
		
		
            
		
            
			
		
            
		
            
			
		
            
		
            
			
            網(wǎng)站導(dǎo)航:
			博客園  
			IT新聞  
			BlogJava  			
			博問(wèn)  
			Chat2DB  
			管理
			
            		
		
            
		
            
			
				

            


            

            		
		
            
	
            	

            



            

				

            



    
    







            
	   
	



久久艹国产|
久久久久亚洲av无码专区导航|
国产精品久久久99|
久久综合伊人77777|
久久免费看黄a级毛片|
精品久久久久久综合日本|
合区精品久久久中文字幕一区|
亚洲国产精品一区二区久久hs|
久久精品国产秦先生|
日韩电影久久久被窝网|
99久久成人国产精品免费|
欧美性猛交xxxx免费看久久久|
久久久久亚洲Av无码专|
久久伊人亚洲AV无码网站|
久久精品a亚洲国产v高清不卡|
久久久久亚洲?V成人无码|
国产亚洲美女精品久久久久狼|
热99RE久久精品这里都是精品免费|
国产美女久久精品香蕉69|
婷婷久久综合|
色综合久久最新中文字幕|
性色欲网站人妻丰满中文久久不卡|
久久涩综合|
久久99精品国产麻豆蜜芽|
国产精品久久久久jk制服|
国产成人久久精品一区二区三区
|
久久亚洲私人国产精品vA|
久久这里只有精品视频99|
国产福利电影一区二区三区，免费久久久久久久精
|
亚洲精品tv久久久久|
色综合久久综精品|
国产成人无码久久久精品一|
久久成人国产精品免费软件|
内射无码专区久久亚洲|
国产精品无码久久综合网|
麻豆精品久久精品色综合|
精品久久久久久国产潘金莲|
麻豆AV一区二区三区久久
|
日韩精品久久久久久免费|
国产69精品久久久久观看软件|
亚洲精品国产第一综合99久久|