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

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            gzwzm06
            
				
            
			            		
		
            
	
            

            

            
	
            
		
            
			
 
C++博客 ::
首頁 ::
新隨筆 ::
聯系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				1 
				隨筆 ::
				52 文章
				::
				17 評論
				::
				0 Trackbacks
			
		
            
	
            

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		
              1#include <cstdio>
              2#include <cmath>
              3
              4const int SIZE = 100101;
              5
              6int arr[SIZE], N;
              7int cntFront[SIZE], cntBack[SIZE];
              8int Max[18][SIZE];
              9
             10inline int GetMax(const int& a, const int& b)
             11{
             12    return (a > b ? a : b);
             13}
             14
             15void Init()
             16{
             17    int i, cnt;
             18
             19    cntFront[1] = 1;
             20    cnt = 1;
             21    for ( i = 2; i <= N; ++i )
             22    {
             23        if ( arr[i] != arr[i - 1] )
             24        {
             25            cnt = 1;
             26        }
             27        else {
             28            cnt++;
             29        }
             30        cntFront[i] = cnt;
             31    }
             32
             33    cntBack[N] = 1;
             34    cnt = 1;
             35    for ( i = N - 1; i > 0; --i )
             36    {
             37        if ( arr[i] != arr[i + 1] )
             38        {
             39            cnt = 1;
             40        }
             41        else
             42        {
             43            cnt++;
             44        }
             45        cntBack[i] = cnt;
             46    }
             47}
             48
             49void MakeRMQ()
             50{
             51    int i, j;
             52
             53    for ( i = 1; i <= N; ++i )
             54    {
             55        Max[0][i] = cntFront[i];
             56    }
             57
             58    for ( j = 1; (1 << j) <= N; ++j )
             59        for ( i = 1; i + (1 << j) - 1 <= N; ++i )
             60        {
             61            Max[j][i] = GetMax( Max[j - 1][i], Max[j - 1][i + (1 << (j - 1))] );
             62        }
             63}
             64
             65inline int RMQ(const int& i, const int& j)
             66{
             67    int k = (int)(log((double)(j - i + 1)) / log(2.0));
             68
             69    return GetMax( Max[k][i], Max[k][j - (1 << k) + 1] ) ;
             70}
             71
             72int Query(int s, int e)
             73{
             74    if ( s == e )
             75        return 1;
             76    else 
             77    {
             78        int t, lv, rv;
             79
             80        lv = cntBack[s];
             81        rv = cntFront[e];
             82
             83        if ( s + lv - 1 > e - rv + 1 )
             84        {
             85            return (e - s + 1);
             86        }
             87
             88        t = GetMax( lv, rv );
             89
             90        s = s + lv;
             91        e = e - rv;
             92
             93        if ( s < e )
             94        {
             95            t = GetMax( t, RMQ( s, e ) );
             96        }
             97
             98        return t;
             99
            100    }
            101}
            102
            103int main()
            104{
            105//    freopen("1.txt", "r", stdin);
            106
            107    int i, s, e, Q;
            108
            109    while ( scanf("%d", &N) , N != 0 )
            110    {
            111        scanf("%d", &Q);
            112
            113        for ( i = 1; i <= N; ++i )
            114        {
            115            scanf("%d", &arr[i]);
            116        }
            117        
            118        Init();
            119        MakeRMQ();
            120
            121        for ( i = 0; i < Q; ++i )
            122        {
            123            scanf("%d %d", &s, &e);
            124
            125            printf("%d\n", Query( s, e ));
            126
            127        }
            128
            129    }
            130
            131    return 0;
            132}
            

	
            
	
	
            
		posted on 2009-05-08 08:00 巫 閱讀(143) 評論(0)  編輯 收藏 引用  所屬分類: 數據結構 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



99国产精品久久久久久久成人热|
99热精品久久只有精品|
久久人人爽人人爽人人片AV不|
国产精品乱码久久久久久软件|
久久亚洲精品无码aⅴ大香|
91精品国产乱码久久久久久|
欧美久久亚洲精品|
国产综合久久久久|
亚洲国产一成久久精品国产成人综合
|
91久久精品电影|
久久人人爽人人爽人人片AV不
|
开心久久婷婷综合中文字幕|
亚洲精品无码久久久久sm|
99久久亚洲综合精品成人|
久久精品国产免费观看三人同眠|
99久久国语露脸精品国产|
久久国产AVJUST麻豆|
成人亚洲欧美久久久久|
奇米影视7777久久精品|
精品久久久久久久国产潘金莲|
久久伊人精品青青草原高清|
蜜臀久久99精品久久久久久小说|
亚洲国产成人精品91久久久
|
久久91综合国产91久久精品|
久久久亚洲欧洲日产国码是AV|
国产精品伊人久久伊人电影|
精品国产一区二区三区久久|
国产偷久久久精品专区|
亚洲人成无码www久久久|
国产精品热久久毛片|
国产国产成人久久精品|
色噜噜狠狠先锋影音久久|
粉嫩小泬无遮挡久久久久久|
日产精品久久久久久久性色|
伊人色综合久久天天人手人婷|
99精品久久精品一区二区|
久久综合久久美利坚合众国|
狠狠色噜噜色狠狠狠综合久久|
伊人久久大香线蕉AV一区二区|
伊人 久久 精品|
狠狠精品久久久无码中文字幕|