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

    
            

            




            







												


        


            


            coreBugZJ
            

            此 blog 已棄。
            

            




            
	
					
	
            
		
            
			EOJ 2458 Frequent values
		
            
		
              1/*
              2EOJ 2458 Frequent values
              3
              4
              5----問題描述：
              6
              7You are given a sequence of n integers a1 , a2 ,  , an in non-decreasing order.
              8In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n).
              9For each query, determine the most frequent value among the integers ai ,  , aj.
             10
             11
             12----輸入：
             13
             14The input consists of several test cases.
             15Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000).
             16The next line contains n integers a1 ,  , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, , n}) separated by spaces.
             17You can assume that for each i ∈ {1, , n-1}: ai ≤ ai+1.
             18The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n),
             19which indicate the boundary indices for the query.
             20 
             21The last test case is followed by a line containing a single 0.
             22
             23
             24----輸出：
             25
             26For each query, print one line with one integer:
             27The number of occurrences of the most frequent value within the given range.
             28
             29
             30----樣例輸入：
             31
             3210 3
             33-1 -1 1 1 1 1 3 10 10 10
             342 3
             351 10
             365 10
             370
             38
             39
             40----樣例輸出：
             41
             421
             434
             443
             45
             46
             47----分析：
             48
             49方案一，
             50線段樹，樹中結點保存
             51        左端，右端，最頻  的實際數值；
             52        左端，右端，最頻  的數值的頻度；
             53        左右端點。
             54
             55方案二，
             56RMQ ST 算法。
             57
             58*/
             59
             60
             61
             62/**********************************************
             63版本二：
             64AC 1019MS
             65RMQ ST 算法。
             66*/
             67
             68
             69#include <iostream>
             70#include <cstdio>
             71#include <cmath>
             72#include <algorithm>
             73
             74using namespace std;
             75
             76const int L = 100009;
             77
             78template<class T = int, unsigned int L = 100009, unsigned int L2 = 18>
             79class  RmqSt
             80{
             81public : 
             82        int init( T a[], int le, int ri) {
             83                int i, j, k;
             84
             85                fr[ le ] = le;
             86                for ( i = le+1; i < ri; ++i ) {
             87                        if ( a[ i ] == a[ i - 1 ] ) {
             88                                fr[ i ] = fr[ i - 1 ];
             89                        }
             90                        else {
             91                                fr[ i ] = i;
             92                        }
             93                }
             94
             95                la[ ri-1 ] = ri;
             96                for ( i = ri-1; i > le; --i ) {
             97                        if ( a[ i ] == a[ i - 1 ] ) {
             98                                la[ i - 1 ] = la[ i ];
             99                        }
            100                        else {
            101                                la[ i - 1 ] = i;
            102                        }
            103                }
            104
            105                for ( i = le; i < ri; ++i ) {
            106                        f[ i ][ 0 ] = 1;
            107                }
            108                k = 1;
            109                while ( (1 << k) <= ri - le ) {
            110                        for ( i = ri - (1<<k); i >= le; --i ) {
            111                                j = i + (1<<(k-1));
            112                                f[ i ][ k ] = max(f[i][k-1], f[j][k-1]);
            113                                if ( a[ j ] == a[ j - 1 ] ) {
            114                                        f[ i ][ k ] = max(f[i][k], min(la[j], i+(1<<k)) - max(fr[j], i));
            115                                }
            116                        }
            117                        ++k;
            118                }
            119                return 0;
            120        }
            121        int query(int le, int ri) {
            122                int k = (int)(floor(log(((double)(ri)) - le) / log(2.0)));
            123                int j = ri - (1<<k);
            124                int q = max(f[le][k], f[j][k]);
            125                if ( (le < j) && (a[j] == a[j-1]) ) {
            126                        q = max(q, min(la[j], ri) - max(fr[j], le));
            127                }
            128                j = le + (1<<k);
            129                if ( (j < ri) && (a[j] == a[j-1])) {
            130                        q = max(q, min(la[j], ri) - max(fr[j], le));
            131                }
            132                return q;
            133        }
            134
            135private : 
            136        T    f[ L ][ L2 ];
            137        int  fr[ L ], la[ L ]; // fr[i] 表示 a[i] 第一次出現的位置，la 類似，表最后
            138}            ;
            139
            140RmqSt<int> prob;
            141int a[ L ];
            142int n;
            143
            144int main() {
            145        int i, q, le, ri;
            146        while ( (1 == scanf("%d", &n)) && (0 < n) ) {
            147                scanf("%d", &q);
            148                for ( i = 1; i <= n; ++i ) {
            149                        scanf("%d", a+i);
            150                }
            151                prob.init(a, 1, n+1);
            152                while ( q-- > 0 ) {
            153                        scanf("%d%d", &le, &ri);
            154                        printf("%d\n", prob.query(le, ri+1));
            155                }
            156        }
            157        return 0;
            158}
            159
            160
            161
            162/**********************************************
            163版本一：
            164AC 941 MS
            165線段樹。
            166*/
            167/*
            168#include <iostream>
            169#include <cstdio>
            170#include <algorithm>
            171
            172using namespace std;
            173
            174const int L = 100009;
            175
            176template<class T = int, unsigned int L = 100009>
            177class  SegTree
            178{
            179public : 
            180        int init(T a[], int le, int ri) {
            181                this->a  = a;
            182                return this->init(1, le, ri);
            183        }
            184        int query(int le, int ri) {
            185                this->le = le;
            186                this->ri = ri;
            187                Node  qr;
            188                return this->query(1, qr);
            189        }
            190
            191private : 
            192        struct  Node
            193        {
            194                T   lv, rv, mv; // 左端，右端，最頻  值
            195                int ln, rn, mn; // 左端，右端，最頻  頻
            196                int le, ri;     // 左右端點
            197        };
            198        Node  node[ L * 3 ];
            199
            200        T     *a;
            201        int   le, ri;
            202
            203        int init(int idx, int le, int ri) {
            204                if ( le + 1 == ri ) {
            205                        node[ idx ].le = le;
            206                        node[ idx ].ri = ri;
            207                        node[ idx ].lv = node[ idx ].rv = node[ idx ].mv = a[ le ];
            208                        node[ idx ].ln = node[ idx ].rn = node[ idx ].mn = 1;
            209                        return 1;
            210                }
            211                int lc = (idx<<1);
            212                int rc = (idx<<1)|1;
            213                init(lc, le,         (le+ri)>>1);
            214                init(rc, (le+ri)>>1, ri        );
            215
            216                node[ idx ].le = le;
            217                node[ idx ].ri = ri;
            218                node[ idx ].lv = node[ lc ].lv;
            219                node[ idx ].ln = node[ lc ].ln;
            220                node[ idx ].rv = node[ rc ].rv;
            221                node[ idx ].rn = node[ rc ].rn;
            222                if ( node[ lc ].mn < node[ rc ].mn ) {
            223                        node[ idx ].mn = node[ rc ].mn;
            224                        node[ idx ].mv = node[ rc ].mv;
            225                }
            226                else {
            227                        node[ idx ].mn = node[ lc ].mn;
            228                        node[ idx ].mv = node[ lc ].mv;
            229                }
            230
            231                if ( node[ lc ].rv == node[ rc ].lv ) {
            232                        if ( node[ lc ].lv == node[ lc ].rv ) {
            233                                node[ idx ].ln += node[ rc ].ln;
            234                        }
            235                        if ( node[ rc ].lv == node[ rc ].rv ) {
            236                                node[ idx ].rn += node[ lc ].rn;
            237                        }
            238                        if ( node[ idx ].mn < node[ lc ].rn + node[ rc ].ln ) {
            239                                node[ idx ].mn = node[ lc ].rn + node[ rc ].ln;
            240                                node[ idx ].mv = node[ lc ].rv;
            241                        }
            242                }
            243                return 1;
            244        }
            245        int query(int idx, Node &qr) {
            246                if ( (this->le <= node[idx].le) && (node[idx].ri <= this->ri) ) {
            247                        qr = node[ idx ];
            248                        return qr.mn;
            249                }
            250                if ( (this->le >= node[idx].ri) || (this->ri <= node[idx].le) ) {
            251                        qr.le = -1;
            252                        qr.ri = -2;
            253                        qr.ln = qr.rn = qr.mn = 0;
            254                        qr.lv = qr.rv = qr.mv = 0;
            255                        return 0;
            256                }
            257                int lc  = (idx<<1);
            258                int rc  = (idx<<1)|1;
            259                int mid = (node[idx].le + node[idx].ri)>>1;
            260
            261                if ( (this->le < mid) && ( this->ri > mid) ) {
            262                        Node qle, qri;
            263                        query(lc, qle);
            264                        query(rc, qri);
            265
            266                        qr.le = le;
            267                        qr.ri = ri;
            268                        qr.lv = qle.lv;
            269                        qr.ln = qle.ln;
            270                        qr.rv = qri.rv;
            271                        qr.rn = qri.rn;
            272                        if ( qle.mn < qri.mn ) {
            273                                qr.mn = qri.mn;
            274                                qr.mv = qri.mv;
            275                        }
            276                        else {
            277                                qr.mn = qle.mn;
            278                                qr.mv = qle.mv;
            279                        }
            280
            281                        if ( qle.rv == qri.lv ) {
            282                                if ( qle.lv == qle.rv ) {
            283                                        qr.ln += qri.ln;
            284                                }
            285                                if ( qri.lv == qri.rv ) {
            286                                        qr.rn += qle.rn;
            287                                }
            288                                if ( qr.mn < qle.rn + qri.ln ) {
            289                                        qr.mn = qle.rn + qri.ln;
            290                                        qr.mv = qle.rv;
            291                                }
            292                        }
            293
            294                        return qr.mn;
            295                }
            296                if ( this->ri > mid ) {
            297                        return query(rc, qr);
            298                }
            299                return query(lc, qr);
            300        }
            301};
            302
            303SegTree<int> prob;
            304int a[ L ];
            305int n;
            306
            307int main() {
            308        int i, q, le, ri;
            309        while ( (1 == scanf("%d", &n)) && (0 < n) ) {
            310                scanf("%d", &q);
            311                for ( i = 1; i <= n; ++i ) {
            312                        scanf("%d", a+i);
            313                }
            314                prob.init(a, 1, n+1);
            315                while ( q-- > 0 ) {
            316                        scanf("%d%d", &le, &ri);
            317                        printf("%d\n", prob.query(le, ri+1));
            318                }
            319        }
            320        return 0;
            321}
            322*/
            323
            
		
            
			posted on 2012-04-22 22:48 coreBugZJ 閱讀(648) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、DataStructure 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久久久久国产精品免费免费|
久久久久久综合一区中文字幕|
国产产无码乱码精品久久鸭|
亚洲精品国产第一综合99久久
|
久久久久亚洲av无码专区喷水|
久久久久综合国产欧美一区二区|
久久99国内精品自在现线|
欧美亚洲国产精品久久|
婷婷久久五月天|
亚洲天堂久久久|
久久国产欧美日韩精品免费|
亚洲中文字幕伊人久久无码|
久久久精品国产Sm最大网站|
久久精品国产国产精品四凭|
精品久久人人做人人爽综合
|
99久久人妻无码精品系列|
亚洲va中文字幕无码久久不卡|
久久天天躁狠狠躁夜夜网站|
久久综合给久久狠狠97色|
av午夜福利一片免费看久久|
成人免费网站久久久|
久久精品国产亚洲av瑜伽|
综合久久精品色|
久久久无码精品亚洲日韩蜜臀浪潮|
国内精品久久人妻互换|
久久精品国内一区二区三区|
一本久久a久久精品综合夜夜|
久久国产精品二国产精品|
久久综合久久综合亚洲|
国产情侣久久久久aⅴ免费|
国产精品美女久久久网AV|
一本大道久久东京热无码AV
|
久久亚洲国产成人精品性色|
久久综合综合久久97色|
亚洲国产精品嫩草影院久久|
久久精品aⅴ无码中文字字幕重口
久久精品a亚洲国产v高清不卡
|
久久久久亚洲AV片无码下载蜜桃
|
伊人久久综合精品无码AV专区|
国产∨亚洲V天堂无码久久久|
国产69精品久久久久99尤物|
国内精品久久国产|