• <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>
            posts - 100,  comments - 15,  trackbacks - 0
            //離散化+st ?
            #include <iostream>
            #include 
            <math.h>
            using namespace std;

            int a[100005];
            int index[100005];
            int f[100005];
            int start[100005];
            int mf[100005][100];
            int n;

            void rmq_init()
            {
                
            int i,j,k=floor(log(double(n))/log(2.0));
                
            for(i=1; i<=n; i++) mf[i][0]=f[i];
                
            for(j=1; j<=k; j++)
                    
            for(i=1; i+(1<<(j-1))<=n; i++)
                        mf[i][j]
            =max(mf[i][j-1],mf[i+(1<<(j-1))][j-1]);
            }

            int rmq(int l,int r)
            {
                
            int il,ir, m,k;
                il
            =index[a[l]],ir=index[a[r]];
                
            if(il==ir)
                    
            return r-l+1;
                
            else
                
            if(il+1==ir)
                    
            return max(start[ir]-l, r-start[ir]+1);
                
            else
                
            {
                    m
            =max( start[il+1]-l, r-start[ir]+1);
                    il
            ++,ir--;
                    k
            =floor(log(double(ir-il+1))/log(2.0));
                    m
            =max( m, max(mf[il][k], mf[ir-(1<<k)+1][k]));
                    
            return m;
                }

            }

            int main()
            {
                
            int i,N,Q,l,r;
                
            while(scanf("%d"&N)!=EOF && N)
                
            {
                    scanf(
            "%d"&Q);
                    memset(f, 
            0sizeof(f));
                    
            for(a[0]=0,i=1, n=0; i<=N; i++)
                    
            {
                        scanf(
            "%d", a+i);
                        
            if(a[i]!=a[i-1])
                            index[ a[i] ]
            =++n, start[n]=i;
                        f[n]
            ++;
                    }

                    rmq_init();
                    
            for(i=0; i<Q; i++)
                    
            {
                        scanf(
            "%d%d"&l, &r);
                        printf(
            "%d\n", rmq(l,r));
                    }

                }

                
            return 0;
            }

            posted on 2010-03-27 14:50 wyiu 閱讀(440) 評(píng)論(1)  編輯 收藏 引用 所屬分類: POJ
            久久婷婷五月综合国产尤物app| 精品99久久aaa一级毛片| 久久伊人精品一区二区三区| 久久精品国产99国产精品导航 | 婷婷久久五月天| 亚洲va国产va天堂va久久| 97久久超碰国产精品旧版| 久久久久99精品成人片牛牛影视| 久久精品国产亚洲AV影院| 99久久精品毛片免费播放| 思思久久精品在热线热| 久久国产亚洲精品麻豆| 久久精品极品盛宴观看| 久久精品国产91久久麻豆自制| 女人高潮久久久叫人喷水| 女人香蕉久久**毛片精品| 嫩草伊人久久精品少妇AV| 亚洲国产精品无码久久久不卡| 国产精品久久99| 伊人久久精品无码av一区| 久久久久免费视频| 久久免费美女视频| 伊人久久大香线蕉亚洲五月天| 久久精品中文字幕第23页| 久久久久国产一级毛片高清版| 午夜精品久久久久久久久| 伊人热热久久原色播放www| 国产毛片久久久久久国产毛片| 久久免费的精品国产V∧| 欧美一区二区三区久久综| 亚洲欧美成人久久综合中文网| 久久久久亚洲av成人无码电影 | 欧美一区二区久久精品| 久久久久97国产精华液好用吗| 国产精久久一区二区三区| 伊人久久综在合线亚洲2019| 久久r热这里有精品视频| 亚洲午夜精品久久久久久人妖| 日韩精品久久久久久免费| 午夜欧美精品久久久久久久| 亚洲精品无码专区久久久|