• <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
            久久人人爽人人爽人人片AV不| 午夜天堂av天堂久久久| 亚洲嫩草影院久久精品| 超级碰久久免费公开视频| 色综合久久88色综合天天 | 久久青青草视频| 91久久精品国产91性色也| 青青草原1769久久免费播放| 成人精品一区二区久久 | 97精品久久天干天天天按摩| 久久亚洲精品视频| 一本一道久久a久久精品综合| 久久婷婷成人综合色综合| 久久人人爽人人爽人人片AV麻豆 | 色综合久久无码五十路人妻| 国产 亚洲 欧美 另类 久久| 婷婷综合久久中文字幕蜜桃三电影 | 久久精品国产福利国产琪琪| 久久精品中文騷妇女内射| 香蕉aa三级久久毛片| 国产成人久久久精品二区三区| 久久婷婷国产剧情内射白浆| 久久无码国产| 精品久久久久久久中文字幕| 久久噜噜电影你懂的| 久久久久亚洲AV无码麻豆| 久久精品国产乱子伦| 日本久久久久久久久久| 久久久久久亚洲精品不卡 | 午夜人妻久久久久久久久| 波多野结衣久久精品| 精品伊人久久大线蕉色首页| 色婷婷久久综合中文久久一本| 国产成人精品久久一区二区三区av | 国产免费久久精品丫丫| 久久久精品免费国产四虎| 国产欧美一区二区久久| 成人免费网站久久久| 国产精品久久免费| 精品国产乱码久久久久久浪潮| 日韩精品国产自在久久现线拍|