• <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 閱讀(389) 評論(0)  編輯 收藏 引用 所屬分類: 線段樹|樹狀數組POJ
            久久久久久九九99精品| 久久成人小视频| 国产成人精品久久二区二区| 亚洲狠狠综合久久| 久久99热这里只频精品6| 综合人妻久久一区二区精品| 国产精品一久久香蕉产线看| 久久精品国产一区| 久久久久亚洲AV无码专区桃色| 久久久久亚洲AV无码永不| 久久国产乱子伦精品免费强| 香蕉99久久国产综合精品宅男自| 久久综合九色综合欧美狠狠| 久久久久久久97| 久久久久国产| 久久男人AV资源网站| 无码人妻久久一区二区三区免费丨 | 久久热这里只有精品在线观看| 亚洲国产精品无码久久一线| 久久综合九色综合久99| 香蕉久久久久久狠狠色| 精品无码久久久久久久动漫| 国产精品九九久久免费视频 | 国内精品久久久久| 国内精品久久久久影院亚洲| 亚洲国产精品久久久久婷婷软件| 久久精品国产99国产精品亚洲| 色偷偷888欧美精品久久久| 中文国产成人精品久久不卡| 久久综合精品国产一区二区三区| 一本久久a久久精品综合夜夜| 亚洲人成网亚洲欧洲无码久久 | 久久99精品国产麻豆| 色诱久久久久综合网ywww| 久久精品亚洲精品国产色婷| 伊人情人综合成人久久网小说 | 九九久久精品国产| 久久精品国产精品青草app| 成人国内精品久久久久一区| 久久精品国产亚洲av麻豆小说| 久久婷婷五月综合色奶水99啪|