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

            







            
	    
    




            






            

				

            



    
    







            
	   
	



亚洲国产精品热久久|
开心久久婷婷综合中文字幕|
国产成人精品久久一区二区三区av
|
久久中文字幕人妻熟av女|
久久本道久久综合伊人|
亚洲精品国产第一综合99久久|
亚洲精品无码久久毛片|
99精品久久精品一区二区|
久久国产精品二国产精品|
久久综合九色欧美综合狠狠
|
天天综合久久一二三区|
性做久久久久久久久浪潮|
亚洲精品蜜桃久久久久久|
国产福利电影一区二区三区，免费久久久久久久精
|
jizzjizz国产精品久久|
亚洲国产高清精品线久久|
99蜜桃臀久久久欧美精品网站
|
久久精品国内一区二区三区|
亚洲国产精品无码久久一区二区
|
久久777国产线看观看精品|
亚洲精品成人久久久|
成人国内精品久久久久影院|
偷窥少妇久久久久久久久|
国产69精品久久久久99|
国产精品一区二区久久|
亚洲中文久久精品无码ww16|
久久国产精品免费|
99久久无码一区人妻a黑|
亚洲中文字幕无码久久2020|
久久无码国产专区精品|
狠狠人妻久久久久久综合|
国产精品国色综合久久|
欧美熟妇另类久久久久久不卡|
午夜精品久久久内射近拍高清|
97久久久久人妻精品专区
|
久久精品国产黑森林|
久久亚洲精品成人AV|
热re99久久6国产精品免费|
久久久久久精品成人免费图片|
国产精品一区二区久久精品涩爱
|
久久国产视屏|