• <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
            99久久www免费人成精品| 亚洲乱亚洲乱淫久久| 久久精品这里热有精品| 亚洲精品美女久久久久99小说| 久久精品国产亚洲av麻豆色欲| 久久久黄片| www.久久热.com| 99久久国产精品免费一区二区| 狠狠精品久久久无码中文字幕| 精品久久人人爽天天玩人人妻| 国产亚洲精久久久久久无码AV| 久久久久久久97| 大香伊人久久精品一区二区| 国内精品久久久久久麻豆| 久久99国产综合精品| 伊人久久无码中文字幕| 思思久久99热免费精品6| 国产精品久久自在自线观看| 色狠狠久久AV五月综合| 人人妻久久人人澡人人爽人人精品 | 久久亚洲国产中v天仙www| 亚洲AV日韩AV永久无码久久| 亚洲国产一成久久精品国产成人综合 | 久久线看观看精品香蕉国产| 亚洲色大成网站WWW久久九九| 久久国产亚洲精品| 亚洲v国产v天堂a无码久久| 国产精品永久久久久久久久久| 久久精品九九亚洲精品天堂| 狠狠色丁香婷婷综合久久来| 国产精品对白刺激久久久| 久久综合综合久久综合| 一本色道久久HEZYO无码| 国产aⅴ激情无码久久| 久久亚洲精品无码VA大香大香| 亚洲人AV永久一区二区三区久久| 婷婷久久综合九色综合绿巨人| 伊人久久大香线蕉精品不卡| 思思久久精品在热线热| 久久夜色精品国产亚洲| 色综合久久久久久久久五月 |