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

            題目描述: 

            Rotate

            Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
            Total Submission(s): 250    Accepted Submission(s): 68


            Problem Description
            Recently yifenfei face such a problem that give you millions of positive integers,tell how many pairs i and j that satisfy F[i] smaller than F[j] strictly when i is smaller than j strictly. i and j is the serial number in the interger sequence. Of course, the problem is not over, the initial interger sequence will change all the time. Changing format is like this [S E] (abs(E-S)<=1000) that mean between the S and E of the sequece will Rotate one times.
            For example initial sequence is 1 2 3 4 5.
            If changing format is [1 3], than the sequence will be 1 3 4 2 5 because the first sequence is base from 0.
             

            Input
            The input contains multiple test cases.
            Each case first given a integer n standing the length of integer sequence (2<=n<=3000000) 
            Second a line with n integers standing F[i](0<F[i]<=10000)
            Third a line with one integer m (m < 10000)
            Than m lines quiry, first give the type of quiry. A character C, if C is ‘R’ than give the changing format, if C equal to ‘Q’, just put the numbers of satisfy pairs.
             

            Output
            Output just according to said.
             

            Sample Input
            5 1 2 3 4 5 3 Q R 1 3 Q
             

            Sample Output
            10 8
             

             題目分析:

            如果是暴力 , 沒一次更新都要重新計算的話,  時間上的開銷會非常大.

            對數據進行分析,可以看到, 當旋轉的時候, 除了 第一個數, 其他的數的對數的個數值都與這個數有關,   因此, 只要開始

            先把總的對數 sum 算出來, 再 根據旋轉時 每個數跟第一個數的大小 比較 ,對sum 進行更新就可以了.

             

            代碼如下:

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

            #include 
            <iostream>
            #include 
            <algorithm>
            using namespace std;
            const int MAX = 10000;
            int nCount = 0, N, M, x , y;
            int com[MAX + 1], num[300 * MAX + 1]; 
            long long sum = 0
            char ask[5];
            inline 
            int low ( int x ) {
                   
            return x & ( -x );
            }
            void modify ( int x, int val ){     // 修改 
                 while ( x <= MAX ){
                        com[x] 
            += val; x += low ( x );
                 }     
            }
            int quy ( int x ){                  // 查詢 
                int sum = 0;
                
            while ( x > 0 ){
                       sum 
            += com[x]; x ^= low ( 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 ( N ) ){
                       memset ( com, 
            0sizeof ( com ) ); sum = 0;
                       
            for ( int i = 0; i < N; ++ i ){
                            scan_d ( num[i] ); modify ( num[i], 
            1 ); 
                            sum 
            += quy ( num[i] - 1 );
                       }
                       scan_d ( M );
                       
            while ( M -- ){
                              scanf ( 
            "%s",ask );  int temp; 
                              
            switch ( ask[0] ){
                                      
            case 'Q' : cout << sum << endl; break;
                                      
            case 'R' : scan_d ( x ), scan_d ( y ); temp = num[x];
                                                 
            while ( x < y ) { num[x] = num[x+1]; 
                                                         num[x] 
            > temp ? sum -- : num[x] == temp ?: sum++ ; x ++
                                                 } 
                                                 num[y] 
            = temp; break;                             
                              }
                       }
                }
                
            return 0;
            }

             

             

             

            久久亚洲国产午夜精品理论片| 色综合久久无码五十路人妻| 久久精品国产影库免费看| 久久精品毛片免费观看| 久久精品国产99国产精偷| 久久亚洲天堂| 久久天天躁狠狠躁夜夜avapp| 国产成人久久精品区一区二区| 久久九九久精品国产| 国产毛片欧美毛片久久久| 久久香蕉国产线看观看乱码| 国产精品无码久久四虎| 亚洲欧美另类日本久久国产真实乱对白| 亚洲国产天堂久久久久久| 日韩乱码人妻无码中文字幕久久 | 久久午夜无码鲁丝片| 青青草原综合久久大伊人精品| 成人综合久久精品色婷婷| 91精品国产高清久久久久久国产嫩草| 91久久成人免费| 久久久久久亚洲精品成人| 欧美精品一区二区久久| 中文字幕成人精品久久不卡| 热re99久久精品国99热| 色妞色综合久久夜夜| 亚洲国产成人久久综合碰| 激情久久久久久久久久| 亚洲国产精品久久久久网站 | 久久亚洲日韩看片无码| 久久久久综合中文字幕| 91超碰碰碰碰久久久久久综合| 久久国产精品99国产精| 性欧美大战久久久久久久久 | 久久精品成人免费网站| 久久久久久毛片免费播放| 国产精品久久婷婷六月丁香| 亚洲国产小视频精品久久久三级| 久久久精品日本一区二区三区 | 国产成人99久久亚洲综合精品| 久久最近最新中文字幕大全 | 亚洲日本va中文字幕久久|