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

            forestkeeper

            C++博客 首頁 新隨筆 聯系 聚合 管理
              3 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks
            一道套數據結構的題

            題意是說,螞蟻有n個等級(level),每個等級初始都有一定量的螞蟻,隨后有一系列操作,p a b操作表示把level  a的螞蟻個數轉換成b,q  x  表示詢問在所有螞蟻里排名第x的螞蟻在哪個等級。

            首先一共有的螞蟻數為所有level螞蟻數量總和,不能為每個螞蟻都開一個int數組去存它的level(如果數據量很小則這種方法可以是o(n)的)。對存著每個層的螞蟻可以用求和與x比較來確定它處于哪個level。由于n的數量級,故希望能采用log n級的方法來處理,恰好由線段樹實現的子段和,其無論是更新(update)還是查詢(query)都是log n級的,同時在查詢時可再加一二分,即sort(0,n)開始,于是查詢的復雜度為logn*logn,最終280ms AC。附代碼,代碼中未用線段樹,而是使用了樹狀數組同樣是logn的查找及更新復雜度,空間復雜度及編程復雜度比線段樹低。

            #include <cstring> 
            #include
            <cstdio>
            const int MAXN = 100000
             
            inline 
            int lowbit(int x) 
                
            return (x & (x ^ (x - 1))); 
            }
             
             
            template
            <class elemType> 
            class Sum
            public
                elemType a[MAXN], c[MAXN], ret; 
                
            int n; 
             
                
            void init(int i) 
                    memset(a, 
            0sizeof(a)); 
                    memset(c, 
            0sizeof(c)); 
                    n 
            = i; 
                }
             
             
                
            void update(int i, elemType v) 
                    v 
            -= a[i]; 
                    a[i] 
            += v; 
                    
            for (i++; i <= n; i += lowbit(i)) 
                        c[i 
            - 1+= v; 
                    }
             
                }
             
                 elemType query(
            int i) 
                    
            for (ret = 0; i; i ^= lowbit(i)) 
                        ret 
            += c[i-1]; 
                    }
             
                    
            return ret; 
                }
             
            }
            ;
            Sum
            <int>sum; 

            int Sort(int l,int r,int x)
            {
                
            if(l>=r-1)
                   
            return l;
                
            int pos = (l+r)/2;
                
            if (pos==1)
                  
            return pos;
                
            int p1 = sum.query(pos);
                
            int p2 = sum.query(pos-1);
                
            if(x>p1&&x<=p2)
                  
            return pos;
                
            int ans;
                
            if(x>p2)
                  ans 
            = Sort(pos,r,x);
                
            else ans = Sort(l,pos,x);
                 
            return ans;
            }

            int main()
            {
                
            int n;
                
            while(scanf("%d",&n)!=EOF)
                
            {
                sum.init(n);
                
            for (int i =0; i<n; i++)
                
            {
                    
            int a;
                    scanf(
            "%d",&a);
                    sum.update(i,a);
                }

                
            int m;
                scanf(
            "%d",&m);
                
            for (int i =0; i<m; i++)
                
            {
                    
            char c[20];
                    scanf(
            "%s",c);
                    
            if (c[0]=='p')
                    
            {
                        
            int a,b;
                        scanf(
            "%d%d",&a,&b);
                        sum.update(a
            -1,b);
                    }

                    
            else
                    
            {
                        
            int x;
                        scanf(
            "%d",&x);
                        
            int ans = Sort(1,n+1,x);
                        printf(
            "%d\n",ans);
                    }

                }

                }

            }
            posted on 2010-01-03 11:07 forestkeeper 閱讀(1284) 評論(0)  編輯 收藏 引用
            亚洲欧美日韩中文久久| 国产婷婷成人久久Av免费高清| 亚洲嫩草影院久久精品| 国内精品久久久久久中文字幕| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | 无码伊人66久久大杳蕉网站谷歌 | 国产亚洲色婷婷久久99精品| 国产精品99久久99久久久| 精品免费久久久久国产一区| 2021国内精品久久久久久影院| 久久精品中文字幕无码绿巨人| 亚洲精品国产成人99久久| 久久久久亚洲AV成人网人人网站 | 久久精品夜色噜噜亚洲A∨| 久久人妻无码中文字幕| 99久久精品免费看国产| 无码精品久久久天天影视| 久久久久免费视频| 蜜臀久久99精品久久久久久小说| 国内精品久久久久久久涩爱| 久久久久亚洲Av无码专| 欧美日韩精品久久久免费观看| 国产精品久久网| 人妻精品久久久久中文字幕69 | 久久久久18| 久久久综合九色合综国产| 日韩精品久久无码人妻中文字幕| 久久精品亚洲男人的天堂| 国产精品99久久精品爆乳| 99久久精品费精品国产| 狠狠色噜噜狠狠狠狠狠色综合久久| 精品熟女少妇AV免费久久| 久久婷婷人人澡人人| 久久久久免费视频| 无码乱码观看精品久久| 欧美午夜A∨大片久久| 青青久久精品国产免费看| 久久99精品免费一区二区| 国产精品伊人久久伊人电影| 国产精品美女久久久网AV| 精品久久久久久国产免费了|