• <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>

            為生存而奔跑

               :: 首頁(yè) :: 聯(lián)系 :: 聚合  :: 管理
              271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

            留言簿(5)

            我參與的團(tuán)隊(duì)

            搜索

            •  

            積分與排名

            • 積分 - 328403
            • 排名 - 74

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            (所有數(shù)組下標(biāo)從1計(jì))計(jì)算出原數(shù)列中每個(gè)數(shù)出現(xiàn)次數(shù)的數(shù)列,并用RMQ預(yù)處理
            如 a[]={ -1 -1 1 1 1 1 3 10 10 10} 得到 sum[]={ 2 4 1 3 }
            用index數(shù)組記錄a[i]在sum中的下標(biāo)。index[]={1,1,2,2,2,2,3,4,4,4};
            first數(shù)組記錄每組數(shù)據(jù)中第一個(gè)出現(xiàn)的在a中的下標(biāo)
            first[]={1,3,7,8};

            對(duì)于每個(gè)詢問(wèn)的區(qū)間[from,to],首先計(jì)算出from to在sum中對(duì)應(yīng)的位置f,t
            1、如果f==t,則[from,to]區(qū)間中數(shù)據(jù)是一樣的
            2、如果f+1=t,則[from,to]區(qū)間只有兩種數(shù)據(jù)。
            3、如果f+1<t,則[from,to]區(qū)間有大于兩種數(shù)據(jù)
            #include<iostream>
            #include
            <vector>
            #include
            <string>
            #include
            <cmath>
            using namespace std;
            const int maxsize=100001;
            int sum[maxsize],st[maxsize][20],a[maxsize],index[maxsize],first[maxsize];
            void rmq_init(int len)
            {
                
            for(int i=1;i<=len;i++)
                    st[i][
            0]=sum[i];
                
            int m=floor(log((double)len)/log(2.0));
                
            for(int i=1;i<=m;i++)
                    
            for(int j=len;j>0;j--)
                    {
                        st[j][i]
            =st[j][i-1];
                        
            if(i+(1<<(i-1))<=len) st[j][i]=max(st[j][i],st[j+(1<<(i-1))][i-1]);
                    }
            }
            int query(int l,int r)
            {
                
            int m=floor(log((double)(r-l+1))/log(2.0));
                
            return max(st[l][m],st[r-(1<<m)+1][m]);
            }
            int solve(const int & from,const int & to)
            {
                
            int f=index[from],t=index[to];
                
            if(f==t) return to-from+1;
                
            else if(f+1==t) return max(first[t]-from,to-first[t]+1);
                
            else
                {
                    
            int res;
                    res
            =max(first[f+1]-from,to-first[t]+1);
                    res
            =max(res,query(f+1,t-1));
                    
            return res;
                }
            }

            int main()
            {
                
            int from,to;
                
            int n,q;
                
            int len;
                
            while(scanf("%d",&n)!=EOF)
                {
                    
            if(n==0break;
                    scanf(
            "%d",&q);
                    a[
            0]=INT_MAX;
                    
                    len
            =0;
                    memset(sum,
            0,sizeof(sum));
                    
            for(int i=1;i<=n;i++)
                    {
                        scanf(
            "%d",&a[i]);
                        
            if(a[i]==a[i-1])
                        {
                            index[i]
            =len;
                            sum[len]
            ++;
                        }
                        
            else
                        {
                            index[i]
            =++len;
                            sum[len]
            =1;
                            first[len]
            =i;
                        }
                    }
                    rmq_init(len);
                    
            while(q--)
                    {
                        scanf(
            "%d%d",&from,&to);
                        printf(
            "%d\n",solve(from,to));
                    }
                }
            }


            posted on 2009-10-25 21:58 baby-fly 閱讀(228) 評(píng)論(0)  編輯 收藏 引用 所屬分類: Algorithm
            久久福利资源国产精品999| 国产精品久久久福利| 欧美成a人片免费看久久| 久久99国产精品久久99小说| 精品国产乱码久久久久久呢 | 99久久伊人精品综合观看| 国产福利电影一区二区三区,免费久久久久久久精 | 国产精品美女久久久久网| 国产无套内射久久久国产| 色婷婷综合久久久久中文字幕 | 奇米综合四色77777久久| 久久精品成人免费网站| 久久免费视频一区| 久久精品一本到99热免费| 久久久久人妻精品一区三寸蜜桃| 久久www免费人成看片| 国产午夜福利精品久久| 久久久久高潮综合影院| 精品久久人人爽天天玩人人妻| 亚洲中文字幕久久精品无码喷水| 久久国产精品久久国产精品| 国产精品久久久久a影院| A级毛片无码久久精品免费| 三上悠亚久久精品| 久久笫一福利免费导航 | 无码人妻久久一区二区三区蜜桃| 精品久久久久久成人AV| 三级韩国一区久久二区综合| 免费观看久久精彩视频| 久久久免费精品re6| 欧美va久久久噜噜噜久久| 亚洲日韩欧美一区久久久久我| 久久久久久a亚洲欧洲aⅴ| 日本强好片久久久久久AAA| 久久久久久久久66精品片| 日韩AV毛片精品久久久| 日本高清无卡码一区二区久久| 四虎影视久久久免费| 久久se精品一区精品二区国产| 狠狠色丁香婷婷综合久久来| 成人综合伊人五月婷久久|