• <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++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
              1 隨筆 :: 52 文章 :: 17 評論 :: 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    //按區間右端從大到小排序,再按左端從小到大排
             13    //將左端依序插入線段樹,即將區間將大先放入,就能得出包含關系
             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;                //記錄區間的左端個數
             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            //處理區間相等的情況,插入操作還是照做,結果就為等價
            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 閱讀(239) 評論(0)  編輯 收藏 引用 所屬分類: 數據結構
            伊人久久五月天| 久久国产高清一区二区三区| 久久久网中文字幕| 久久精品国产只有精品66 | 天堂无码久久综合东京热| 久久性生大片免费观看性| 久久久久亚洲国产| 国产欧美一区二区久久| 久久久久无码精品国产app| 亚洲欧美伊人久久综合一区二区 | 影音先锋女人AV鲁色资源网久久 | 综合人妻久久一区二区精品| 久久久婷婷五月亚洲97号色| 日本一区精品久久久久影院| 无码八A片人妻少妇久久| 久久99精品综合国产首页| 久久久久久曰本AV免费免费| 国产999精品久久久久久| 久久人人爽爽爽人久久久| 大香网伊人久久综合网2020| 亚洲精品午夜国产VA久久成人| 国产精品久久久久aaaa| 成人久久免费网站| 久久综合色之久久综合| 久久美女网站免费| 国产一区二区精品久久| 亚洲∧v久久久无码精品| 色播久久人人爽人人爽人人片AV| 91久久九九无码成人网站| 亚洲精品无码久久一线| 亚洲人成电影网站久久| 日日狠狠久久偷偷色综合96蜜桃 | 久久久久亚洲AV综合波多野结衣 | 国产精品对白刺激久久久| 久久人人爽人人爽人人爽 | 国产精品久久久久久影院| 久久亚洲AV无码精品色午夜麻豆 | 国内精品久久久久影院薰衣草| 欧美无乱码久久久免费午夜一区二区三区中文字幕 | 亚洲国产成人乱码精品女人久久久不卡 | 国产精品久久久久…|