• <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>
            隨筆 - 97, 文章 - 22, 評論 - 81, 引用 - 0
            數據加載中……

            PKU 1990 MooFest

            題目鏈接:http://poj.org/problem?id=1990

            /*
            題意:
                約翰農夫有N(N <= 20000)頭牛,每頭牛有一個權值Vi,他將它們排成一排,
            牛i和牛j的閾值是  兩者的距離差*max(Vi, Vj),現在給出每頭牛的權值和它的
            位置,求所有兩頭牛之間的閾值之和。

            題解:
                樹狀數組

            思路:
                我們準備兩個樹狀數組,以每頭牛的位置作為樹狀數組的下標,其中一個用
            來表示當前位置的牛的位置的值,另一個則記錄當前位置牛的個數,然后對所有
            牛以Vi為關鍵字進行遞增排序。
                接下來對每頭牛進行一次線掃,首先統計比當前這頭牛的位置小的和大的牛
            的數目和位置和,然后做差求出以當前牛的權值為最大值的閾值總和。之后將這
            頭牛的數量和位置插入到樹狀數組中進行更新。
            */


            #include 
            <iostream>
            #include 
            <algorithm>

            using namespace std;

            #define maxn 20010
            #define ll __int64

            struct point {
                
            int V;
                
            int pos;
            }
            pt[maxn];

            ll c[
            2][maxn];
            int n, Max;

            ll ABS(ll v) 
            {
                
            return v < 0 ? -v : v;
            }


            int cmp(point a, point b) {
                
            return a.V < b.V;
            }


            int lowbit(int x) {
                
            return x & (-x);
            }


            void add(int idx, int pos, int v) {
                
            while(pos <= Max) {
                    c[idx][pos] 
            += v;
                    pos 
            += lowbit(pos);
                }

            }


            ll sum(
            int idx, int pos) {
                ll s 
            = 0;
                
            while(pos > 0{
                    s 
            += c[idx][pos];
                    pos 
            -= lowbit(pos);
                }

                
            return s;
            }



            int main() {
                
            int i;
                
            while(scanf("%d"&n) != EOF) {
                    Max 
            = 0;
                    
            for(i = 0; i < n; i++{
                        scanf(
            "%d %d"&pt[i].V, &pt[i].pos);
                        
            if(pt[i].pos > Max)
                            Max 
            = pt[i].pos;
                    }


                    
            for(i = 1; i <= Max; i++)
                        c[
            0][i] = c[1][i] = 0;
                    sort(pt, pt 
            + n, cmp);

                    ll ans 
            = 0;
                    
            for(i = 0; i < n; i++{
                        ans 
            += ABS((sum(0, Max) - sum(0, pt[i].pos)
                             
            - (sum(1, Max) - sum(1, pt[i].pos)) * pt[i].pos)) * pt[i].V;

                        ans 
            += ABS((sum(0, pt[i].pos)
                             
            - sum(1, pt[i].pos) * pt[i].pos)) * pt[i].V;

                        add(
            0, pt[i].pos, pt[i].pos);
                        add(
            1, pt[i].pos, 1);
                    }

                    printf(
            "%I64d\n", ans);
                }

                
            return 0;
            }

            posted on 2011-04-09 22:06 英雄哪里出來 閱讀(1327) 評論(0)  編輯 收藏 引用 所屬分類: 樹狀數組

            亚洲av伊人久久综合密臀性色| 国产精品久久久久无码av| 久久久久久无码国产精品中文字幕| 一本久久久久久久| 四虎影视久久久免费观看| 色播久久人人爽人人爽人人片AV| 亚洲精品无码久久久久去q | 久久99国产精品久久99果冻传媒| 久久天堂电影网| 亚洲天堂久久久| 久久er99热精品一区二区| 99国内精品久久久久久久| 国产精品乱码久久久久久软件 | 国产精品欧美亚洲韩国日本久久 | 国产亚洲美女精品久久久久狼| 久久精品国产亚洲7777| 999久久久免费精品国产| 香蕉久久AⅤ一区二区三区| 久久91精品国产91久久户| 久久99精品久久久大学生| 久久精品国产亚洲AV不卡| 久久久久久久97| 精品久久亚洲中文无码| 亚洲?V乱码久久精品蜜桃| 999久久久免费国产精品播放| 久久久久亚洲av无码专区喷水| 精品久久人人做人人爽综合| 久久精品欧美日韩精品| 99久久99久久精品国产片果冻| 久久久久国产视频电影| 色综合合久久天天综合绕视看| 久久精品天天中文字幕人妻| 久久精品aⅴ无码中文字字幕重口 久久精品a亚洲国产v高清不卡 | 久久久精品2019免费观看| 久久免费的精品国产V∧| 亚洲精品乱码久久久久久按摩| 国内精品久久久久影院亚洲| 久久久久女教师免费一区| 久久AⅤ人妻少妇嫩草影院| 国产精品九九久久免费视频| 久久九九免费高清视频|