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

            pku 3468 區間求和+統計,線段樹

            題意很明確,一個區間,給定2種操作
            1、給[s,e]加上一個數
            2、詢問[s,e]的和
            線段樹寫的有點搓,其實沒必要搞那么復雜,還是采取標記下移就可以了。。郁悶
             1 import java.io.*;
             2 public class Main {
             3 
             4     /**
             5      * @param args
             6      */
             7     static class node
             8     {
             9         int s,e;
            10         long add=0;
            11         long sum=0;
            12     }
            13     static node st[]=new node[400000];
            14     static void init(int s,int e,int pos)
            15     {
            16         st[pos].s=s;
            17         st[pos].e=e;
            18         if(e!=s+1)
            19         {
            20             init(s,(s+e)>>1,pos<<1);
            21             init((s+e)>>1,e,(pos<<1)+1);
            22         }
            23     }
            24     static void add(int s,int e,long add,int pos)
            25     {
            26         if(st[pos].s==s&&st[pos].e==e)
            27         {
            28             st[pos].add+=add;
            29             st[pos].sum+=add*(e-s);
            30         }
            31         else
            32         {
            33             int mid=(st[pos].s+st[pos].e)>>1;
            34             if(e<=mid)
            35                 add(s,e,add,pos<<1);
            36             else if(s>=mid)
            37                 add(s,e,add,(pos<<1)+1);
            38             else
            39             {
            40                 add(s,mid,add,pos<<1);
            41                 add(mid,e,add,(pos<<1)+1);
            42             }
            43             st[pos].sum=st[pos<<1].sum+st[(pos<<1)+1].sum+st[pos].add*(st[pos].e-st[pos].s);
            44         }
            45     }
            46     static long getsum(int s,int e,int pos)
            47     {
            48         if(st[pos].s==s&&st[pos].e==e)
            49             return st[pos].sum;
            50         else
            51         {
            52             int mid=(st[pos].s+st[pos].e)>>1;
            53             if(e<=mid)
            54                 return getsum(s,e,pos<<1)+st[pos].add*(e-s);
            55             else if(s>=mid)
            56                 return getsum(s,e,(pos<<1)+1)+st[pos].add*(e-s);
            57             else
            58                 return getsum(s,mid,pos<<1)+getsum(mid,e,(pos<<1)+1)+st[pos].add*(e-s);
            59         }
            60     }
            61     public static void main(String[] args) throws Exception{
            62         StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            63         for(int i=0;i<400000;i++)
            64             st[i]=new node();
            65         int n,q;
            66         in.nextToken();
            67         n=(int)in.nval;
            68         in.nextToken();
            69         q=(int)in.nval;
            70         init(1,n+1,1);
            71         for(int i=1;i<=n;i++)
            72         {
            73             in.nextToken();
            74             add(i,i+1,(long)in.nval,1);
            75         }
            76         for(int i=1;i<=q;i++)
            77         {
            78             in.nextToken();
            79             String jud=in.sval;
            80             in.nextToken();
            81             int a=(int)in.nval;
            82             in.nextToken();
            83             int b=(int)in.nval;
            84             switch(jud.charAt(0))
            85             {
            86             case 'Q':
            87                 System.out.println(getsum(Math.min(a, b),Math.max(a, b)+1,1));
            88                 break;
            89             case 'C':
            90                 in.nextToken();
            91                 add(Math.min(a, b),Math.max(a,b)+1,(long)in.nval,1);
            92                 break;
            93             }
            94         }
            95             
            96     }
            97 
            98 }
            99 


            posted on 2010-10-28 01:34 yzhw 閱讀(209) 評論(0)  編輯 收藏 引用 所屬分類: data struct

            <2010年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            色婷婷综合久久久中文字幕| 91精品国产91热久久久久福利| 欧美亚洲国产精品久久蜜芽| 久久亚洲国产午夜精品理论片| 狠狠狠色丁香婷婷综合久久五月| 久久综合狠狠色综合伊人| 久久se精品一区精品二区国产| 久久久久久久97| 久久久国产精品网站| 一本久久精品一区二区| 久久99国产精品久久99| 99久久国产亚洲综合精品| 久久综合综合久久狠狠狠97色88| 看全色黄大色大片免费久久久| 国产成人无码精品久久久性色| A级毛片无码久久精品免费| 久久久久久久97| 久久一本综合| 青青草国产精品久久| 日本强好片久久久久久AAA| 久久乐国产精品亚洲综合| 久久丫精品国产亚洲av| 99久久免费国产精品特黄| 精品久久久久国产免费| 久久久精品午夜免费不卡| 午夜精品久久久久久99热| 日本国产精品久久| 久久93精品国产91久久综合 | 久久er热视频在这里精品| 久久久久亚洲av综合波多野结衣| 久久成人18免费网站| 国产精品综合久久第一页| 中文字幕亚洲综合久久| 久久精品国产只有精品2020| 久久久久久九九99精品| 久久丫精品国产亚洲av| 欧美丰满熟妇BBB久久久| 奇米影视7777久久精品| 久久久噜噜噜久久中文福利| 久久综合久久自在自线精品自| 久久人人爽人人爽人人爽|