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

            







            
	    
    




            






            

				

            



    
    







            
	   
	



久久亚洲精品无码AV红樱桃|
国产2021久久精品|
亚洲国产精品无码久久久蜜芽|
久久棈精品久久久久久噜噜|
夜夜亚洲天天久久|
国产精品久久新婚兰兰|
99久久久国产精品免费无卡顿|
婷婷久久综合九色综合绿巨人|
国产精品99久久精品|
亚洲日本久久久午夜精品|
99久久精品无码一区二区毛片
|
亚洲第一极品精品无码久久|
精品久久8x国产免费观看|
亚洲午夜无码久久久久小说|
日本久久久久久中文字幕|
久久精品国产亚洲AV高清热|
综合久久久久久中文字幕亚洲国产国产综合一区首
|
激情久久久久久久久久|
久久综合给久久狠狠97色|
久久精品综合网|
久久久精品久久久久特色影视|
久久91精品久久91综合|
国产麻豆精品久久一二三|
欧美黑人激情性久久|
久久精品国产AV一区二区三区
|
国产精品狼人久久久久影院|
激情伊人五月天久久综合|
久久综合噜噜激激的五月天|
久久精品国产免费观看|
成人午夜精品无码区久久|
久久久久波多野结衣高潮|
超级碰碰碰碰97久久久久|
伊人久久亚洲综合影院|
亚洲国产成人久久精品99|
性做久久久久久久久久久|
伊人久久亚洲综合影院|
伊人久久大香线蕉成人|
大香伊人久久精品一区二区
|
日本久久久久亚洲中字幕|
亚洲中文久久精品无码ww16
|
大美女久久久久久j久久|