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

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋    

             

            題目地址:

                 http://acm.hdu.edu.cn/showproblem.php?pid=2642 

            題目描述:

            Stars

            Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/65536 K (Java/Others)
            Total Submission(s): 166    Accepted Submission(s): 66


            Problem Description
            Yifenfei is a romantic guy and he likes to count the stars in the sky.
            To make the problem easier,we considerate the sky is a two-dimension plane.Sometimes the star will be bright and sometimes the star will be dim.At first,there is no bright star in the sky,then some information will be given as "B x y" where 'B' represent bright and x represent the X coordinate and y represent the Y coordinate means the star at (x,y) is bright,And the 'D' in "D x y" mean the star at(x,y) is dim.When get a query as "Q X1 X2 Y1 Y2",you should tell Yifenfei how many bright stars there are in the region correspond X1,X2,Y1,Y2.

            There is only one case.
             

            Input
            The first line contain a M(M <= 100000), then M line followed.
            each line start with a operational character.
            if the character is B or D,then two integer X,Y (0 <=X,Y<= 1000)followed.
            if the character is Q then four integer X1,X2,Y1,Y2(0 <=X1,X2,Y1,Y2<= 1000) followed.
             

            Output
            For each query,output the number of bright stars in one line.
             

            Sample Input
            5 B 581 145 B 581 145 Q 0 600 0 200 D 581 145 Q 0 600 0 200
             

            Sample Output
            1 0
             

             

            題目分析 :

             與 HDU 1892 基本相同的一道題,  只是矩陣數組的值被限定在 [0,1] ,   是一道 二維 樹狀數組的 裸題,  直接 模板, 加上對題目數據做一些

            處理即可.

             

            代碼如下 :

            /*
            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
                      http://www.cnblog.com/MiYu
            Author By : MiYu
            Test      : 1
            Program   : 2642
            */

            #include <iostream>
            #include <algorithm>
            using namespace std;
            #define lowbit(x) (x&(-x))
            int T;
            const int MAX = 1001;
            int mat[1002][1002];
            int com[1002][1002];
            void modify ( int x,int y, int n )
            {
                 while ( x <= MAX ){
                       int t = y;
                       while ( t <= MAX ){
                              com[x][t] += n;
                              t += lowbit(t); 
                       } 
                       x += lowbit(x);
                 } 
            }
            int quy ( int x, int y )
            {
                 int sum = 0;
                 while ( x > 0 ){
                       int t = y;
                       while ( t > 0 ){
                              sum += com[x][t];
                              t ^= lowbit(t); 
                       } 
                       x ^= lowbit(x);
                 } 
                 return sum; 
            }
            inline bool scan_d(int &num) 
            {
                    char in;bool IsN=false;
                    in=getchar();
                    if(in==EOF) return false;
                    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
                    if(in=='-'){ IsN=true;num=0;}
                    else num=in-'0';
                    while(in=getchar(),in>='0'&&in<='9'){
                            num*=10,num+=in-'0';
                    }
                    if(IsN) num=-num;
                    return true;
            }
            int main ()
            {
                  while ( scan_d(T) ) {
                        int ca = 1;
                               char s[5];  int a,b,x,y,m,res,maxx,maxy,minx,miny;
                               memset ( com, 0, sizeof ( com ) );
                               while ( T -- ) {
                                     scanf ( "%s",s );
                                     switch ( s[0] ){
                                            case 'Q' : scan_d(a);scan_d(x);scan_d(b);scan_d(y); minx = min ( a,x );miny=min(b,y);maxx=max(a,x)+1;maxy=max(b,y)+1;
                                                       res = 0;  res += quy( maxx,maxy ); res -= quy (maxx,miny); res -= quy(minx,maxy); res += quy(minx,miny);
                                                       printf ( "%d\n",res ); break;   
                                            case 'B' : scan_d(x);scan_d(y); x++;y++; if ( !mat[x][y] ) { modify ( x,y,1 ); mat[x][y] = 1; } break;
                                            case 'D' : scan_d(x);scan_d(y); x++;y++; if ( mat[x][y] ) { modify ( x,y,-1 ); mat[x][y] = 0; } break;  
                                     } 
                               }
                }
                return 0;
            }

             

             

            综合久久给合久久狠狠狠97色| 日韩乱码人妻无码中文字幕久久| 久久精品国产亚洲αv忘忧草| 国产精品99久久精品爆乳| 久久久精品2019免费观看| 伊人久久综合无码成人网 | 婷婷国产天堂久久综合五月| 中文字幕久久欲求不满| 国产精品岛国久久久久| 久久精品嫩草影院| 久久精品成人| 久久久久人妻一区精品果冻| 久久国产精品国语对白| 亚洲精品乱码久久久久久蜜桃| 久久久久九九精品影院| 少妇久久久久久被弄到高潮| 香蕉久久夜色精品国产2020| 久久久久久久精品成人热色戒| 国产A级毛片久久久精品毛片| 囯产极品美女高潮无套久久久 | 欧美性猛交xxxx免费看久久久| 久久午夜福利电影| 中文字幕精品久久久久人妻| 亚洲国产另类久久久精品小说 | 久久综合色区| 综合久久国产九一剧情麻豆| 91精品国产综合久久久久久| 99久久成人18免费网站| 2021国产精品久久精品| 精品久久久久久国产潘金莲 | 久久精品一本到99热免费| 色综合久久中文综合网| 亚洲综合久久久| 国产日产久久高清欧美一区| 久久久久人妻一区精品| 国产精品久久久久AV福利动漫| 精品久久久久久久久久久久久久久| 久久综合伊人77777麻豆| 久久久久久久久久久久中文字幕 | 国产精品内射久久久久欢欢| 精品久久久久久无码不卡|