• <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 閱讀(388) 評論(0)  編輯 收藏 引用 所屬分類: 線段樹|樹狀數組 、POJ
            国内精品久久久久影院优 | 久久综合中文字幕| 久久久青草青青亚洲国产免观| 久久―日本道色综合久久| 国产精品日韩深夜福利久久| 久久久久亚洲精品无码网址| 伊人热热久久原色播放www| 一本一本久久A久久综合精品 | 93精91精品国产综合久久香蕉| 日产久久强奸免费的看| 无码人妻精品一区二区三区久久| 亚洲精品高清久久| 97精品伊人久久久大香线蕉| 国产成人AV综合久久| 久久青青草原精品国产| 久久久久99精品成人片三人毛片| 亚洲AV无码久久精品色欲| 久久久久久久久久久免费精品| 久久久久久国产精品无码超碰| 久久久久亚洲精品无码网址| 久久精品国产99国产精品澳门| 国产69精品久久久久9999APGF | 久久久青草青青亚洲国产免观| 99蜜桃臀久久久欧美精品网站| 久久国产免费| 成人精品一区二区久久久| 99国产精品久久| 久久丫精品国产亚洲av| 99久久国产宗和精品1上映| 无夜精品久久久久久| 久久高清一级毛片| 国产精品激情综合久久| 成人亚洲欧美久久久久| 亚洲国产精久久久久久久| 91精品国产色综合久久| 国产麻豆精品久久一二三| 久久久久免费看成人影片| 日本欧美久久久久免费播放网| 伊人久久大香线蕉综合影院首页| 波多野结衣久久一区二区| 国产69精品久久久久APP下载|