• <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原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋    

             

            題目地址:

                 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 基本相同的一道題,  只是矩陣數(shù)組的值被限定在 [0,1] ,   是一道 二維 樹狀數(shù)組的 裸題,  直接 模板, 加上對題目數(shù)據(jù)做一些

            處理即可.

             

            代碼如下 :

            /*
            MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
                      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;
            }

             

             

            亚洲中文字幕无码久久精品1| 久久九九青青国产精品| 国产精品久久久久aaaa| 久久人爽人人爽人人片AV| 亚洲精品乱码久久久久久按摩| 久久精品中文闷骚内射| 99久久综合狠狠综合久久| 爱做久久久久久| 午夜精品久久久久久久| 久久精品无码专区免费| 久久久黄色大片| AV无码久久久久不卡蜜桃| 久久综合久久性久99毛片| 久久久久亚洲AV无码网站| 久久久久无码精品国产| 久久亚洲国产午夜精品理论片| 精品九九久久国内精品| 精品人妻伦九区久久AAA片69| 久久精品国产影库免费看| 久久伊人精品青青草原高清| 国产精品日韩深夜福利久久| 久久久国产精品| 久久婷婷色香五月综合激情| 婷婷伊人久久大香线蕉AV| 大伊人青草狠狠久久| 国产免费久久精品99久久| 青青草国产97免久久费观看| 激情伊人五月天久久综合| 亚洲精品高清国产一久久| 无码人妻久久一区二区三区 | 久久精品99久久香蕉国产色戒 | 精品国产乱码久久久久久呢| 久久国产亚洲精品无码| 欧美日韩中文字幕久久久不卡| 亚洲AV无码久久精品狠狠爱浪潮| 国产 亚洲 欧美 另类 久久 | 亚洲精品乱码久久久久久| 成人精品一区二区久久| 久久天堂AV综合合色蜜桃网| 久久中文精品无码中文字幕| 国产精品无码久久综合 |