• <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>

            poj 1195 Mobile phones 二維樹狀數組

            Mobile phones
            Time Limit: 5000MS Memory Limit: 65536K
            Total Submissions: 7087 Accepted: 3030

            Description

            Suppose that the fourth generation mobile phone base stations in the Tampere area operate as follows. The area is divided into squares. The squares form an S * S matrix with the rows and columns numbered from 0 to S-1. Each square contains a base station. The number of active mobile phones inside a square can change because a phone is moved from a square to another or a phone is switched on or off. At times, each base station reports the change in the number of active phones to the main base station along with the row and the column of the matrix.

            Write a program, which receives these reports and answers queries about the current total number of active mobile phones in any rectangle-shaped area.

            Input

            The input is read from standard input as integers and the answers to the queries are written to standard output as integers. The input is encoded as follows. Each input comes on a separate line, and consists of one instruction integer and a number of parameter integers according to the following table.

            The values will always be in range, so there is no need to check them. In particular, if A is negative, it can be assumed that it will not reduce the square value below zero. The indexing starts at 0, e.g. for a table of size 4 * 4, we have 0 <= X <= 3 and 0 <= Y <= 3.

            Table size: 1 * 1 <= S * S <= 1024 * 1024
            Cell value V at any time: 0 <= V <= 32767
            Update amount: -32768 <= A <= 32767
            No of instructions in input: 3 <= U <= 60002
            Maximum number of phones in the whole table: M= 2^30

            Output

            Your program should not answer anything to lines with an instruction other than 2. If the instruction is 2, then your program is expected to answer the query by writing the answer as a single line containing a single integer to standard output.

            Sample Input

            0 4
            1 1 2 3
            2 0 0 2 2
            1 1 1 2
            1 1 2 -1
            2 1 1 2 3
            3
            

            Sample Output

            3
            4

            Source


            一維樹狀數組用一維數組來存儲部分元素的和,二維樹狀數組只需用二維數組來存儲即可,獲得和,修正的函數同一維數組差別不大。
            /*Source Code

            Problem: 1195  User: y09 
            Memory: 4956K  Time: 579MS 
            Language: C++  Result: Accepted 

            Source Code 
            */

            #include 
            <stdio.h>
            const int MAX=1200;
            int c[MAX][MAX];
            int n;
            int LowBit(int t)
            {
                
            return t&(t^(t-1));
            }


            int Sum(int endx,int endy)
            {
                
            int sum=0;
                
            int temp=endy;
                
            while(endx>0)
                
            {
                    endy
            =temp;//注意記錄endy的值,本人在此出錯,找半天錯誤不得
                    while (endy>0)
                    
            {
                        sum
            +=c[endx][endy];
                        endy
            -=LowBit(endy);
                    }

                    
                    endx
            -=LowBit(endx);
                }

                
            return sum;
            }

            void plus(int posx,int posy,int num)
            {
                
            int temp=posy;
                
            while (posx <=n)
                
            {
                    posy
            =temp;
                    
            while(posy<=n)
                    
            {
                        c[posx][posy]
            +=num;
                        posy
            +=LowBit(posy);
                    }

                    posx
            +=LowBit(posx);
                }

            }

            int GetSum(int l,int b,int r,int t)
            {
                
            return Sum(r,t)-Sum(r,b-1)-Sum(l-1,t)+Sum(l-1,b-1);
            }

            int main()
            {
                
            int I;
                
            int x,y,a;
                
            int l,b,r,t;
                
            while(scanf("%d",&I))
                
            {
                    
            switch (I)
                    
            {
                    
            case 0:
                        scanf(
            "%d",&n);
                        
            break;
                    
            case 1:
                        scanf(
            "%d%d%d",&x,&y,&a);
                        plus(x
            +1,y+1,a);
                        
            break;
                    
            case 2:
                        scanf(
            "%d%d%d%d",&l,&b,&r,&t);
                        printf(
            "%d\n",GetSum(l+1,b+1,r+1,t+1));
                        
            break;
                    
            case 3:
                        
            return 0;
                        
                    }

                }

                
                
            return 0;
            }

            posted on 2010-08-27 16:28 若余 閱讀(395) 評論(0)  編輯 收藏 引用

            導航

            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            統計

            常用鏈接

            留言簿

            隨筆檔案(16)

            搜索

            最新隨筆

            最新評論

            評論排行榜

            久久久久免费看成人影片| 久久精品人人做人人妻人人玩| 三级韩国一区久久二区综合| 色综合久久夜色精品国产| 2021国内精品久久久久久影院| 久久露脸国产精品| www久久久天天com| 久久亚洲精品无码VA大香大香| 久久久久久国产精品免费无码| 国产精品欧美亚洲韩国日本久久 | 久久精品a亚洲国产v高清不卡| 91久久精品电影| 亚洲综合熟女久久久30p| 久久久黄片| 久久亚洲av无码精品浪潮| 国产成人精品久久免费动漫 | 国产美女久久精品香蕉69| 老男人久久青草av高清| 亚洲色欲久久久久综合网| 久久天天躁狠狠躁夜夜2020一| 久久国产免费直播| 亚洲国产精品无码久久青草 | 欧美一级久久久久久久大| 国产亚洲精久久久久久无码AV| 97超级碰碰碰碰久久久久| 99久久国产亚洲高清观看2024| 亚洲一本综合久久| 欧美精品一区二区久久| 三级三级久久三级久久| 天天躁日日躁狠狠久久| 国产精品亚洲综合专区片高清久久久 | 夜夜亚洲天天久久| 欧美久久天天综合香蕉伊| 久久久精品国产免大香伊| 77777亚洲午夜久久多喷| 中文国产成人精品久久亚洲精品AⅤ无码精品 | 久久中文字幕人妻熟av女| 99国内精品久久久久久久| 久久亚洲精品无码AV红樱桃| 亚洲精品国产综合久久一线| 久久亚洲欧美日本精品|