• <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>
            #include <iostream>
            #include 
            <cstdio>

            using namespace std;

            struct CNode
            {
                
            int L, R;
                CNode 
            * pLeft, * pRight;
                
            long long nSum, Inc;
            };

            CNode Tree[
            1000000];

            int nCount = 0;

            void BuildTree( CNode * pRoot, int L, int R )
            {
                pRoot
            ->= L;
                pRoot
            ->= R;
                pRoot
            ->nSum = 0;
                pRoot
            ->Inc = 0;

                
            if( L == R )    return;
                nCount
            ++;
                pRoot
            ->pLeft = Tree + nCount;
                nCount
            ++;
                pRoot
            ->pRight = Tree + nCount;
                BuildTree( pRoot
            ->pLeft, L, ( L + R ) / 2 );
                BuildTree( pRoot
            ->pRight, ( L + R ) / 2 + 1, R );
            }

            void Insert( CNode * pRoot, int i, int v )
            {
                
            if( pRoot->== i && pRoot->== i )
                {
                    pRoot
            ->nSum = v;
                    
            return;
                }
                pRoot
            ->nSum += v;
                
            if( i <= ( pRoot->+ pRoot->R ) / 2 )
                    Insert( pRoot
            ->pLeft, i, v );
                
            else
                    Insert( pRoot
            ->pRight, i, v);
            }

            void Add( CNode * pRoot, int a, int b, long long c )
            {
                
            if( a == pRoot->&& b == pRoot->R )
                {
                    pRoot
            ->Inc += c;
                    
            return;
                }
                pRoot
            ->nSum += ( b - a + 1 ) * c;
                
            if( b <= ( pRoot->+ pRoot->R ) / 2)
                    Add( pRoot
            ->pLeft, a, b, c );
                
            else if ( a >= (pRoot->+ pRoot->R ) / 2 + 1 )
                    Add ( pRoot
            ->pRight, a, b, c );
                
            else
                {
                    Add( pRoot
            ->pLeft, a, ( pRoot->+ pRoot->R ) / 2, c );
                    Add( pRoot
            ->pRight, (pRoot->+ pRoot->R ) / 2 + 1, b, c );
                }
            }

            long long QuerynSum( CNode * pRoot, int a, int b )
            {
                
            if ( a == pRoot->&& b == pRoot->R )
                    
            return (pRoot->nSum + (pRoot->- pRoot->+ 1 ) * pRoot->Inc);
                pRoot
            ->nSum += (pRoot->- pRoot->+ 1 ) * pRoot->Inc;
                Add( pRoot
            ->pLeft, pRoot->L, (pRoot->+ pRoot->R ) / 2, pRoot->Inc );
                Add( pRoot
            ->pRight, (pRoot->+ pRoot->R ) / 2 + 1, pRoot->R, pRoot->Inc );
                pRoot
            ->Inc = 0;

                
            if( b <= (pRoot->+ pRoot->R ) /2 )
                    
            return QuerynSum( pRoot->pLeft, a, b );
                
            else if ( a >= (pRoot->+ pRoot->R ) / 2 + 1 )
                    
            return QuerynSum ( pRoot->pRight, a, b);
                
            else
                    
            return QuerynSum( pRoot->pLeft, a, (pRoot->L  +pRoot->R ) / 2 ) + QuerynSum( pRoot->pRight, (pRoot->+ pRoot->R ) / 2 + 1, b ) ;
            }

            int main()
            {
                
            int n,q;
                scanf(
            "%d%d"&n, &q );
                nCount 
            = 0;
                BuildTree( Tree, 
            1, n);
                
            int temp;
                
            forint i = 1; i <= n; i++ )
                {
                    scanf(
            "%d"&temp);
                    Insert( Tree, i, temp );
                }
                
            char c_temp[10];
                
            int a, b, c;
                
            forint i = 0; i < q; i++ )
                {
                    scanf(
            "%s", c_temp);
                    
            if( c_temp[0== 'C' )
                    {
                        scanf(
            "%d%d%d"&a, &b, &c );
                        Add( Tree, a, b, c);
                    }
                    
            else
                    {
                        scanf(
            "%d%d"&a, &b );
                        printf(
            "%I64d\n",QuerynSum( Tree, a, b ));
                    }
                }
                
            return 0;
            }
            posted on 2010-07-29 07:16 Vontroy 閱讀(386) 評論(0)  編輯 收藏 引用 所屬分類: 線段樹|樹狀數組POJ
            人妻丰满AV无码久久不卡| 精品熟女少妇a∨免费久久| 久久亚洲欧美日本精品| 办公室久久精品| 色婷婷噜噜久久国产精品12p| 久久天天躁狠狠躁夜夜躁2014| 波多野结衣AV无码久久一区| 国产精品无码久久久久久| 久久久WWW成人免费毛片| 狠狠色丁香久久婷婷综合| 色综合合久久天天综合绕视看| 无码任你躁久久久久久| 精品免费久久久久久久| 亚洲一区精品伊人久久伊人| 高清免费久久午夜精品| 人人妻久久人人澡人人爽人人精品| 久久99精品久久久久久 | 久久久噜噜噜www成人网| 天天综合久久久网| 国产精品久久久久久久人人看| 狠狠色丁香久久综合婷婷| 久久精品极品盛宴观看| 久久国产美女免费观看精品| 久久久久人妻精品一区二区三区| 亚洲成av人片不卡无码久久| 精品久久久久久国产牛牛app| 精品免费tv久久久久久久| 亚洲va中文字幕无码久久不卡| 怡红院日本一道日本久久 | 伊人色综合久久天天人手人婷 | 蜜臀av性久久久久蜜臀aⅴ麻豆| 三级韩国一区久久二区综合 | 久久免费的精品国产V∧| 综合久久精品色| 欧美大战日韩91综合一区婷婷久久青草| 精品久久久久久成人AV| 久久精品一本到99热免费| 日韩精品久久久久久免费| 国产精品99久久久精品无码 | 成人亚洲欧美久久久久| 一本大道加勒比久久综合|