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

            ArcTan

            dfs
            隨筆 - 16, 文章 - 117, 評論 - 6, 引用 - 0
            數據加載中……

            poj 3468 線段樹

            http://poj.org/problem?id=3468

            線段數的構造,查詢,修改!
            struct node{
               int l,r,m;
               long long sum;//當前區間的和
               long long add;//區間需要加上的數值
            }

            題意:
                  給定n個數字A1,A2,..,An,Q個操作。
                  C x y z,把區間x y內的數都加上z
                  Q x y,求區間x y內所有數的和。
            總結:
                  基礎代碼一定要對,調試了半天,最后發現是swap(x,y,t)寫錯了!!!!
                  WA了一次,數據是long long才行,要分析清楚數據范圍?。?!

            #include <cstdio>
            #include 
            <cstdlib>
            #include 
            <cstring>
            #include 
            <cmath>
            #include 
            <ctime>
            #include 
            <cassert>
            #include 
            <iostream>
            #include 
            <sstream>
            #include 
            <fstream>
            #include 
            <map>
            #include 
            <set>
            #include 
            <vector>
            #include 
            <queue>
            #include 
            <algorithm>
            #define min(x,y) (x<y?x:y)
            #define max(x,y) (x>y?x:y)
            #define swap(x,y,t) (t=x,x=y,y=t)
            #define clr(list) memset(list,0,sizeof(list))
            #define LL long long
            #define maxn 200005
            using namespace std;
            struct node{
                
            int l,r,m;
                LL sum;
                LL add;
            } tree[
            2*maxn];
            int a[maxn];
            LL build(
            int l,int r,int root)
            {
                tree[root].l
            =l;
                tree[root].r
            =r;
                tree[root].m
            =(l+r)/2;
                tree[root].add
            =0;
                
            if (l==r)
                {
                    tree[root].sum
            =a[l];
                    
            return tree[root].sum;
                }
                
            long long sum_l=build(l,(l+r)/2,root*2);
                
            long long sum_r=build((l+r)/2+1,r,root*2+1);
                tree[root].sum
            =sum_l+sum_r;
                
            return tree[root].sum;
            }
            int insert(int l,int r,int add,int root)
            {
                
            if (l<=tree[root].l && r>=tree[root].r)
                {
                    tree[root].add
            +=add;
                    tree[root].sum
            +=add * (tree[root].r-tree[root].l+1);
                    
            return 0;
                }
                
            if (tree[root].add) //向下更新
                {
                    tree[
            2*root].sum+=tree[root].add * (tree[root*2].r-tree[root*2].l+1);
                    tree[
            2*root].add+=tree[root].add;
                    tree[
            2*root+1].sum+=tree[root].add * (tree[root*2+1].r-tree[root*2+1].l+1);
                    tree[
            2*root+1].add+=tree[root].add;
                    tree[root].add
            =0;
                }
                
            if (l<=tree[root].m)
                    insert(l,r,add,root
            *2);
                
            if (r>tree[root].m)
                    insert(l,r,add,root
            *2+1);
                tree[root].sum
            =tree[root*2].sum+tree[root*2+1].sum;   //這里回溯啊
                return 0;
            }
            LL search(
            int l,int r,int root)
            {
                
            if (l<=tree[root].l && r>=tree[root].r)
                    
            return tree[root].sum;
                
            if (tree[root].add)  //向下更新
                {
                    tree[
            2*root].sum+=tree[root].add * (tree[root*2].r-tree[root*2].l+1);
                    tree[
            2*root].add+=tree[root].add;
                    tree[
            2*root+1].sum+=tree[root].add * (tree[root*2+1].r-tree[root*2+1].l+1);
                    tree[
            2*root+1].add+=tree[root].add;
                    tree[root].add
            =0;
                }
                LL sum_l
            =0,sum_r=0;
                
            if (l<=tree[root].m)
                    sum_l
            =search(l,r,2*root);
                
            if (r>tree[root].m)
                    sum_r
            =search(l,r,2*root+1);
                
            return sum_l+sum_r;
            }
            int main()
            {
                
            int n,m;
                
            int x,y,z;
                
            int tmp;
                
            char ch;
                scanf(
            "%d%d",&n,&m);
                
            for (int i=1;i<=n;i++)
                    scanf(
            "%d",&a[i]);
                build(
            1,n,1);

                
            for (int i=1;i<=m;i++)
                {
                    scanf(
            "\n%c",&ch);
                    
            if (ch=='C')
                    {
                        scanf(
            "%d%d%d",&x,&y,&z);
                        
            if (x>y)
                            swap(x,y,tmp);
                        insert(x,y,z,
            1);
                    }
                    
            else
                    {
                        scanf(
            "%d%d",&x,&y);
                        
            if (x>y)
                            swap(x,y,tmp);
                        printf(
            "%I64d\n",search(x,y,1));
                    }
                }
                
            return 0;
            }


            posted on 2012-07-25 10:54 wangs 閱讀(415) 評論(0)  編輯 收藏 引用 所屬分類: ACM-數據結構

            国内精品久久久久久麻豆| 国产精品久久久久久久久| 狠狠精品久久久无码中文字幕| 久久成人国产精品| 国产日韩欧美久久| 久久综合给合久久狠狠狠97色| 国产成人久久精品一区二区三区 | 国产成人99久久亚洲综合精品| 久久精品国产一区| 国产亚洲美女精品久久久2020| 99久久精品国产一区二区蜜芽| 香蕉久久av一区二区三区| 久久综合一区二区无码| 久久综合九色综合欧美狠狠| 久久久噜噜噜www成人网| 人人狠狠综合久久亚洲88| 尹人香蕉久久99天天拍| 久久精品国产一区二区电影| 97久久天天综合色天天综合色hd| 久久久WWW成人免费毛片| 亚洲精品无码久久久久sm| 国产高清美女一级a毛片久久w| 久久久精品国产免大香伊| 亚洲国产天堂久久综合| 精品久久久久久中文字幕| 久久九九久精品国产免费直播| 国产高潮久久免费观看| 麻豆精品久久久一区二区| 亚洲AV无码成人网站久久精品大| 青青青青久久精品国产h久久精品五福影院1421 | 久久国产精品一国产精品金尊| 精品久久久久久久久久中文字幕| 无码AV中文字幕久久专区| 欧美日韩精品久久久久| 国产激情久久久久影院小草| 精品国产乱码久久久久久郑州公司 | 色天使久久综合网天天| 久久久艹| 久久强奷乱码老熟女网站| 国产精品欧美亚洲韩国日本久久| 99久久99久久久精品齐齐 |