• <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
            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(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;
            }

             

             

            精品久久久久久无码中文野结衣 | 国产精品综合久久第一页| 亚洲精品无码久久久久| 亚洲精品无码专区久久久 | 国产精品久久久久蜜芽| 午夜精品久久久久久99热| 久久久婷婷五月亚洲97号色| 国产精品久久影院| 人妻中文久久久久| 精品国产乱码久久久久久1区2区 | 久久精品一本到99热免费| 成人国内精品久久久久一区| 久久精品国产99久久香蕉| 久久综合久久综合亚洲| 91精品观看91久久久久久| 伊人伊成久久人综合网777| 国产精品99精品久久免费| 亚洲天堂久久久| 国内精品久久久久影院网站| 久久精品亚洲日本波多野结衣| 久久强奷乱码老熟女| 久久精品国产亚洲沈樵| 国产亚洲精品久久久久秋霞| 国产亚州精品女人久久久久久 | 久久精品国产日本波多野结衣| 日本免费久久久久久久网站| 久久久噜噜噜久久熟女AA片| 亚洲国产精品成人AV无码久久综合影院 | 一本色道久久99一综合| 亚洲精品乱码久久久久久蜜桃 | 久久久久免费视频| 国产2021久久精品| 久久综合狠狠综合久久激情 | 国产精品久久久久久影院| 久久久久亚洲精品天堂| 久久精品国产亚洲av影院| 久久人人爽人人爽人人AV东京热| 久久国产免费直播| 嫩草伊人久久精品少妇AV| .精品久久久麻豆国产精品| 久久久久亚洲AV成人片|