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

            HDOJ 1698 Just A Hook 線段樹

            Problem Description
            In the game of DotA, Pudge’s meat hook is actually the most horrible thing for most of the heroes. The hook is made up of several consecutive metallic sticks which are of the same length.



            Now Pudge wants to do some operations on the hook.

            Let us number the consecutive metallic sticks of the hook from 1 to N. For each operation, Pudge can change the consecutive metallic sticks, numbered from X to Y, into cupreous sticks, silver sticks or golden sticks.
            The total value of the hook is calculated as the sum of values of N metallic sticks. More precisely, the value for each kind of stick is calculated as follows:

            For each cupreous stick, the value is 1.
            For each silver stick, the value is 2.
            For each golden stick, the value is 3.

            Pudge wants to know the total value of the hook after performing the operations.
            You may consider the original hook is made up of cupreous sticks.
             

            Input
            The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 10 cases.
            For each case, the first line contains an integer N, 1<=N<=100,000, which is the number of the sticks of Pudge’s meat hook and the second line contains an integer Q, 0<=Q<=100,000, which is the number of the operations.
            Next Q lines, each line contains three integers X, Y, 1<=X<=Y<=N, Z, 1<=Z<=3, which defines an operation: change the sticks numbered from X to Y into the metal kind Z, where Z=1 represents the cupreous kind, Z=2 represents the silver kind and Z=3 represents the golden kind.
             

            Output
            For each case, print a number in a line representing the total value of the hook after the operations. Use the format in the example.
             

            Sample Input
            1
            10
            2
            1 5 2
            5 9 3
             

            Sample Output
            Case 1: The total value of the hook is 24.
             

            Source

            #include <iostream>
            using namespace std;

            const int MAXN = 100001;
            struct segment{
                
            int left,right,color;
                
            bool cover;
            }
            tree[MAXN*3];

            void create(int l,int r,int step){
                tree[step].left
            =l,tree[step].right=r;
                tree[step].color
            =tree[step].cover=1;
                
            if(l==r) return ;
                
            int mid=(l+r)>>1;
                create(l,mid,
            2*step);
                create(mid
            +1,r,2*step+1);
            }

            void update(int l,int r,int c,int step){
                
            if(l==tree[step].left&&r==tree[step].right){
                    tree[step].color
            =c;
                    tree[step].cover
            =1;
                    
            return;
                }

                
            if(tree[step].cover){
                    tree[step].cover
            =0;
                    tree[
            2*step].cover=tree[2*step+1].cover=1;
                    tree[
            2*step].color=tree[2*step+1].color=tree[step].color;
                }

                
            if(r<=tree[2*step].right)
                    update(l,r,c,
            2*step);
                
            else if(l>=tree[2*step+1].left)
                    update(l,r,c,
            2*step+1);
                
            else{
                    update(l,tree[
            2*step].right,c,2*step);
                    update(tree[
            2*step+1].left,r,c,2*step+1);
                }

            }

            int query(int step){
                
            if(tree[step].cover) 
                    
            return tree[step].color*(tree[step].right-tree[step].left+1);
                
            else 
                    
            return query(2*step)+query(2*step+1);
            }

            int main(){
                
            int i,t,n,q,l,r,c;
                scanf(
            "%d",&t);
                
            for(i=1;i<=t;i++){
                    scanf(
            "%d %d",&n,&q);
                    create(
            1,n,1);
                    
            while(q--){
                        scanf(
            "%d %d %d",&l,&r,&c);
                        update(l,r,c,
            1);
                    }

                    printf(
            "Case %d: The total value of the hook is %d.\n",i,query(1));
                }

                
            return 0;
            }

            posted on 2009-05-12 16:32 極限定律 閱讀(511) 評論(1)  編輯 收藏 引用 所屬分類: ACM/ICPC

            評論

            # re: HDOJ 1698 Just A Hook 線段樹 2009-08-13 21:02 zeus

            good 剛剛做了也是1y
            呵呵你寫什么都很詳細啊 學習了  回復  更多評論   

            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            午夜肉伦伦影院久久精品免费看国产一区二区三区 | 99精品国产综合久久久久五月天| 国产精品日韩深夜福利久久| 久久无码一区二区三区少妇| 日韩欧美亚洲综合久久| 狠狠狠色丁香婷婷综合久久五月 | 蜜臀久久99精品久久久久久小说| 久久久久亚洲av无码专区导航| 精品久久久久久久久中文字幕| 久久久WWW成人免费毛片| 亚洲国产精品综合久久一线| 久久综合精品国产二区无码| 久久精品国产亚洲Aⅴ蜜臀色欲| 亚洲国产另类久久久精品黑人| 91精品国产综合久久香蕉 | 久久国产V一级毛多内射| 伊人久久大香线蕉av不卡| 国产一区二区三精品久久久无广告| 精产国品久久一二三产区区别| 狠色狠色狠狠色综合久久| 日产精品久久久久久久| 久久久久无码精品国产app| 精品综合久久久久久97超人| 午夜精品久久久久久毛片| 思思久久99热免费精品6| 久久av免费天堂小草播放| 成人久久久观看免费毛片| 一本久道久久综合狠狠爱| 亚洲精品成人久久久| 日韩精品无码久久一区二区三| 亚洲国产精品久久久久| 青青草原综合久久大伊人精品| 久久夜色精品国产噜噜噜亚洲AV| 欧美久久久久久| 久久国产AVJUST麻豆| 怡红院日本一道日本久久 | 久久久久国产一级毛片高清板| 精品久久久久香蕉网| 99久久久国产精品免费无卡顿| 亚洲精品国产美女久久久| 精品国产99久久久久久麻豆|