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

             

             

            国产一区二区三精品久久久无广告| 国产精品成人精品久久久| 性高湖久久久久久久久AAAAA| 日本欧美国产精品第一页久久| 亚洲欧美伊人久久综合一区二区| 日韩AV无码久久一区二区| 品成人欧美大片久久国产欧美...| 亚洲精品乱码久久久久久不卡| 国产精品一区二区久久精品| 一本色综合久久| 国产毛片久久久久久国产毛片| 亚洲乱码精品久久久久..| 国产毛片久久久久久国产毛片| 久久国产欧美日韩精品| 亚洲精品综合久久| 91久久精品无码一区二区毛片| 久久久久人妻精品一区二区三区 | 性高湖久久久久久久久AAAAA | 久久久精品国产亚洲成人满18免费网站 | 精品久久8x国产免费观看| 日韩精品无码久久一区二区三| 狠狠久久亚洲欧美专区| 久久香蕉超碰97国产精品| 国产精品久久婷婷六月丁香| 人人狠狠综合久久亚洲88| 狠狠精品久久久无码中文字幕| …久久精品99久久香蕉国产| 五月丁香综合激情六月久久 | 日日躁夜夜躁狠狠久久AV| 最新久久免费视频| 久久天天躁狠狠躁夜夜2020老熟妇| 97r久久精品国产99国产精| 久久99精品久久只有精品| 99精品久久久久久久婷婷| 久久国产免费直播| 人妻无码αv中文字幕久久琪琪布| 久久免费国产精品| 狠狠色丁香婷婷久久综合| 久久人人爽人人人人爽AV | 情人伊人久久综合亚洲| 丁香五月综合久久激情|