• <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 英雄哪里出來 閱讀(1325) 評論(0)  編輯 收藏 引用 所屬分類: 樹狀數組

            久久青青草原精品影院| 国产毛片久久久久久国产毛片| 久久精品国产一区二区 | 欧洲精品久久久av无码电影| 亚洲精品乱码久久久久久| 色综合久久精品中文字幕首页| 久久精品国产一区二区三区| 亚洲精品无码久久久久sm| 国产一区二区精品久久凹凸 | 久久亚洲天堂| www久久久天天com| 色综合久久天天综线观看| 国产成人无码久久久精品一| 欧美成a人片免费看久久| 精品久久777| 久久久久久精品免费看SSS| 91久久精品国产免费直播| 国产成人精品三上悠亚久久| 精品久久久久久无码国产| 久久精品国内一区二区三区| 亚洲香蕉网久久综合影视 | 成人综合伊人五月婷久久| 亚洲午夜精品久久久久久app| 亚洲国产成人久久综合一| 久久久精品国产sm调教网站 | 国产精品久久久久久久人人看| 99热都是精品久久久久久| 久久久久国产精品熟女影院 | 99久久精品九九亚洲精品| 久久久久国产精品熟女影院| 亚洲精品高清国产一线久久 | 欧美噜噜久久久XXX| 国产毛片欧美毛片久久久| 亚洲第一永久AV网站久久精品男人的天堂AV | 久久久精品久久久久久| 97精品国产97久久久久久免费| 2020久久精品国产免费| 久久精品国产精品青草| 天天爽天天爽天天片a久久网| 狠狠狠色丁香婷婷综合久久俺| 久久精品国产亚洲77777|