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

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            gzwzm06
            
				
            
			            		
		
            
	
            

            

            
	
            
		
            
			
 
C++博客 ::
首頁(yè) ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				1 
				隨筆 ::
				52 文章
				::
				17 評(píng)論
				::
				0 Trackbacks
			
		
            
	
            

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		
              1#include <cstdio>
              2#include <algorithm>
              3using namespace std;
              4
              5const int SIZE = 100001;
              6
              7struct RANGE
              8{
              9    int m_S, m_E;
             10    int m_p;
             11
             12    //按區(qū)間右端從大到小排序，再按左端從小到大排
             13    //將左端依序插入線段樹，即將區(qū)間將大先放入，就能得出包含關(guān)系
             14    bool operator < (const RANGE& other)
             15    {
             16        if ( m_E != other.m_E )
             17            return (m_E > other.m_E);
             18        
             19        return (m_S < other.m_S);
             20    }
             21}            cow[SIZE];
             22
             23//線段樹
             24struct STREE
             25{
             26    int m_leftPos, m_rightPos;
             27    int m_left, m_right;
             28    int m_ItNum;                //記錄區(qū)間的左端個(gè)數(shù)
             29}            tree[SIZE * 2];
             30
             31int N, result[SIZE];
             32
             33void BuildSTree(int& index, const int& l, const int& r)
             34{
             35    int id = index;
             36    tree[id].m_left = l, tree[id].m_right = r;
             37    tree[id].m_ItNum = 0;
             38    if ( l == r )
             39    {
             40        tree[id].m_leftPos = tree[id].m_rightPos = -1;
             41        return ;
             42    }
             43
             44    int mid = (l + r) >> 1;
             45
             46    tree[id].m_leftPos = ++index;
             47    BuildSTree( index, l, mid );
             48    tree[id].m_rightPos = ++index;
             49    BuildSTree( index, mid + 1, r );
             50}
             51
             52int Insert(const int& id, const int& s)
             53{
             54    int num = 0;
             55    if ( tree[id].m_left == s && tree[id].m_right == s )
             56    {
             57        tree[id].m_ItNum++;
             58        return (tree[id].m_ItNum - 1);
             59    }
             60
             61    int mid = (tree[id].m_left + tree[id].m_right) >> 1;
             62
             63    if ( s <= mid ) {
             64        tree[id].m_ItNum++;
             65        num += Insert(tree[id].m_leftPos, s);
             66    }
             67    else {
             68        num = tree[id].m_ItNum;
             69        num += Insert(tree[id].m_rightPos, s);
             70    }
             71
             72    return num;
             73}
             74
             75int main()
             76{
             77    freopen("1.txt", "r", stdin);
             78    int i, t, maxN;
             79
             80    while ( true )
             81    {
             82        scanf("%d", &N);
             83        if ( N == 0 )
             84            break;
             85        
             86        maxN = 0;
             87        for ( i = 0; i < N; ++i )
             88        {
             89            scanf("%d %d", &cow[i].m_S, &cow[i].m_E);
             90            cow[i].m_p = i;
             91            if ( cow[i].m_E > maxN )
             92                maxN = cow[i].m_E;
             93        }
             94        t = 0;
             95        BuildSTree(t, 0, maxN);
             96        sort(cow, cow + N);
             97
             98        result[cow[0].m_p] = Insert(0, cow[0].m_S);
             99        for ( i = 1; i < N; ++i )
            100        {
            101            result[cow[i].m_p] = Insert(0, cow[i].m_S);
            102            //處理區(qū)間相等的情況，插入操作還是照做，結(jié)果就為等價(jià)
            103            if ( cow[i].m_E == cow[i - 1].m_E && cow[i].m_S == cow[i - 1].m_S )
            104                result[cow[i].m_p] = result[cow[i - 1].m_p];
            105        }
            106
            107        for ( i = 0; i < N - 1; ++i )
            108        {
            109            printf("%d ", result[i]);
            110        }
            111        printf("%d\n", result[i]);
            112    }
            113    return 0;
            114}
            

	
            
	
	
            
		posted on 2009-04-11 16:15 巫 閱讀(237) 評(píng)論(0)  編輯 收藏 引用  所屬分類: 數(shù)據(jù)結(jié)構(gòu) 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



久久er99热精品一区二区|
久久综合中文字幕|
囯产精品久久久久久久久蜜桃|
欧美精品国产综合久久|
色欲综合久久躁天天躁蜜桃|
久久er国产精品免费观看2|
久久久久一级精品亚洲国产成人综合AV区|
亚洲国产成人精品女人久久久|
日本强好片久久久久久AAA|
97久久精品国产精品青草|
久久亚洲AV永久无码精品|
精品久久久噜噜噜久久久|
久久强奷乱码老熟女|
亚洲AV无一区二区三区久久
|
精品久久久久久无码国产|
色欲综合久久躁天天躁|
91久久婷婷国产综合精品青草|
亚洲欧洲中文日韩久久AV乱码|
成人久久精品一区二区三区|
久久久久青草线蕉综合超碰|
精品久久人人做人人爽综合|
久久婷婷五月综合色奶水99啪
|
97精品国产97久久久久久免费|
亚洲一本综合久久|
久久精品九九亚洲精品|
国产激情久久久久久熟女老人|
热综合一本伊人久久精品|
日韩一区二区久久久久久|
粉嫩小泬无遮挡久久久久久|
中文字幕乱码久久午夜|
伊人情人综合成人久久网小说|
国产精品欧美亚洲韩国日本久久|
久久综合久久综合久久|
久久国产精品99久久久久久老狼|
丰满少妇人妻久久久久久|
久久亚洲精品无码AV红樱桃|
亚洲色婷婷综合久久|
伊人久久大香线蕉综合Av
|
中文字幕无码久久精品青草|
婷婷久久精品国产|
久久久久se色偷偷亚洲精品av|