• <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 閱讀(429) 評論(1)  編輯 收藏 引用 所屬分類: POJ
            欧美伊人久久大香线蕉综合69| 久久99久国产麻精品66| 国产精品久久久久影视不卡| 久久r热这里有精品视频| 精品综合久久久久久88小说| 久久精品国产亚洲AV忘忧草18| 久久久久亚洲AV片无码下载蜜桃| 久久电影网2021| 日韩电影久久久被窝网| 色欲久久久天天天综合网精品| 精品久久香蕉国产线看观看亚洲 | 久久伊人精品青青草原日本| 久久无码AV一区二区三区| 99久久无码一区人妻a黑| 久久国产视屏| 狠狠色丁香婷婷久久综合不卡| 亚洲人成无码久久电影网站| 秋霞久久国产精品电影院| 久久天天躁狠狠躁夜夜2020一| 中文精品久久久久国产网址 | 久久精品国产精品亚洲精品| 亚洲精品第一综合99久久| 久久亚洲综合色一区二区三区| AV无码久久久久不卡蜜桃| 久久93精品国产91久久综合| 精品久久久久久中文字幕| 一本久久a久久精品亚洲| 亚洲精品视频久久久| 久久久亚洲精品蜜桃臀| 国产高清国内精品福利99久久| 狠狠色丁香久久婷婷综| avtt天堂网久久精品| 久久久久99精品成人片欧美| 久久久无码精品亚洲日韩按摩 | 国产综合久久久久| 无码国内精品久久人妻| 久久精品国产色蜜蜜麻豆| 精品熟女少妇AV免费久久| 综合网日日天干夜夜久久| 97精品依人久久久大香线蕉97| 亚洲国产欧美国产综合久久|