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

            







            
	    
    




            






            

				

            



    
    







            
	   
	



亚洲综合伊人久久大杳蕉|
久久夜色tv网站|
日韩欧美亚洲综合久久|
无码AV中文字幕久久专区|
久久精品国产清高在天天线|
久久综合九色综合精品|
亚洲AⅤ优女AV综合久久久|
亚洲av成人无码久久精品|
久久er国产精品免费观看2|
久久笫一福利免费导航|
亚洲国产精品久久|
亚洲综合日韩久久成人AV|
国产精品热久久无码av|
国内精品久久人妻互换|
亚洲天堂久久久|
久久久久国产日韩精品网站|
人妻丰满AV无码久久不卡|
亚洲国产成人精品久久久国产成人一区二区三区综
|
久久这里有精品视频|
久久久久久久97|
久久久久噜噜噜亚洲熟女综合|
一级做a爰片久久毛片免费陪|
国内精品久久久久久久97牛牛|
午夜精品久久久久久影视riav|
精品久久久久久久中文字幕|
俺来也俺去啦久久综合网|
亚洲AV日韩精品久久久久|
久久精品青青草原伊人|
中文字幕亚洲综合久久菠萝蜜|
久久精品国产欧美日韩|
国产精品丝袜久久久久久不卡|
97久久精品午夜一区二区|
国产精品久久久久jk制服|
久久久久人妻精品一区二区三区|
一本色综合网久久|
99久久国产精品免费一区二区
|
国产精品久久自在自线观看|
成人国内精品久久久久影院|
久久香蕉国产线看观看99|
四虎国产精品免费久久5151|
99久久国产综合精品网成人影院|