• <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 巫 閱讀(136) 評論(0)  編輯 收藏 引用  所屬分類: 數據結構 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



久久综合日本熟妇|
一本大道久久东京热无码AV|
久久人妻无码中文字幕|
久久久久免费精品国产|
精品无码久久久久国产|
国产精品午夜久久|
久久伊人精品一区二区三区|
99久久成人国产精品免费|
yy6080久久|
精品熟女少妇a∨免费久久|
色综合久久中文综合网|
久久婷婷国产剧情内射白浆|
久久精品亚洲精品国产色婷
|
精品熟女少妇a∨免费久久|
久久精品国产亚洲5555|
色婷婷综合久久久久中文|
久久婷婷人人澡人人|
国产91色综合久久免费|
免费精品久久天干天干|
久久99精品久久久久久水蜜桃
|
精品久久久久久无码人妻蜜桃|
久久精品国产免费观看三人同眠|
久久美女网站免费|
久久久女人与动物群交毛片|
久久综合亚洲色HEZYO社区|
91秦先生久久久久久久|
WWW婷婷AV久久久影片|
无码人妻久久一区二区三区免费
|
久久亚洲欧洲国产综合|
亚洲午夜精品久久久久久人妖|
亚洲国产精品久久电影欧美|
久久99国产精品久久99小说|
性做久久久久久久久|
久久久久久极精品久久久|
国产成人香蕉久久久久
|
四虎国产精品成人免费久久|
蜜桃麻豆www久久国产精品|
久久久久国产亚洲AV麻豆|
99久久精品免费|
国产三级精品久久|
久久激情亚洲精品无码?V|