• <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年9月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            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;
            }

             

             

            色噜噜狠狠先锋影音久久| 国产精品亚洲综合专区片高清久久久 | 四虎亚洲国产成人久久精品| 久久综合久久鬼色| 亚洲精品无码久久久久| 91久久香蕉国产熟女线看| 久久久久久亚洲精品影院| 久久精品国产亚洲av影院 | 亚洲午夜精品久久久久久app| 中文国产成人精品久久不卡| 999久久久免费国产精品播放| 亚洲国产一成人久久精品| 狠狠久久综合伊人不卡| 狠狠88综合久久久久综合网| 久久中文字幕无码专区| 国产成人精品久久免费动漫| yy6080久久| 精品久久久久久久中文字幕| 亚洲国产精品18久久久久久| 久久久久九国产精品| 久久亚洲高清观看| 无码国产69精品久久久久网站| 久久久青草青青国产亚洲免观| 精品久久久久久中文字幕| 国内精品伊人久久久久777| 国产精品久久久99| 久久精品国产99国产精偷 | 99久久成人国产精品免费| 亚洲色欲久久久综合网东京热| 久久亚洲国产成人精品无码区| 久久国产成人午夜AV影院| 91精品无码久久久久久五月天| 久久精品国产亚洲AV麻豆网站| 伊人色综合久久天天人手人婷 | 亚洲va久久久噜噜噜久久 | 1000部精品久久久久久久久| 亚洲精品乱码久久久久久中文字幕| 久久久久久久精品妇女99| 性色欲网站人妻丰满中文久久不卡| 亚洲人成精品久久久久| 亚洲成色WWW久久网站|