• <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>
            #include? < iostream >

            using ? namespace ?std;

            int ?n,?m;
            #define ?N??200010
            #define ?lowbit(x)??(?(x)&(-(x))?)

            struct ?TArray{
            ????
            int ?cnt[N];
            ????TArray(){?init();?}
            ????
            void ?update(? int ?p,? int ?v?){
            ????????
            for (? int ?x = ?p;?x <= ?n;?cnt[x] += ?v,?x += ?lowbit(x)?);?}
            ????
            int ??sum(? int ?p?){
            ????????
            int ?x = ?p,?s = ? 0 ;
            ????????
            for (?;?x;?s += ?cnt[x],?x -= ?lowbit(x)?);
            ????????
            return ?s;?}
            ????
            int ??rank(? int ?k?){
            ????????k
            = ?sum(n) + ? 1 - ?k;
            ????????
            int ?left = ? 1 ,?right = ?n;
            ????????
            while (?left + ? 1 < ?right?){
            ????????????
            int ?m = ?(left + ?right) >> ? 1 ;
            ????????????
            int ?s = ?sum(m);
            ????????????
            if (?s >= ?k?)?right = ?m;
            ????????????
            else ????????left = ?m;
            ????????}
            ????????
            if (?sum(left) >= ?k?)? return ?left;
            ????????
            return ?right;
            ????}
            ????
            void ?init(){?? for ( int ?i = ? 0 ;?i <= ?n;? ++ i?)?cnt[i] = ? 0 ;?}
            };

            TArray?tay;
            struct ?U_find{
            ????
            int ?find[N],?num[N];
            ????U_find(){?clear();}
            ????
            int ?parent(? int ?t?){?
            ????????
            int ?u = ?t,?v;??? while (?u != ?find[u]?)?u = ?find[u];
            ????????
            while (?t != ?u?)?{?v = ?find[t];?find[t] = ?u;?t = ?find[v];?}
            ????????
            return ?u;??}
            ????
            bool ?is_friend(? int ?u,? int ?v?){? return ?parent(u) == ?parent(v);?}
            ????
            void ?set_friend(? int ?u,? int ?v?){
            ????????
            int ?a = ?parent(u),?b = ?parent(v);
            ????????
            if (?a == ?b?)? return ;
            ????????
            if (?num[a] > ?num[b]?)?{?
            ????????????find[b]
            = ?a;??
            ????????????tay.update(?num[b],?
            - 1 ?);
            ????????????tay.update(?num[a],?
            - 1 ?);
            ????????????num[a]
            += ?num[b];
            ????????????tay.update(?num[a],?
            1 ?);
            ????????}
            ????????
            else ?{
            ????????????find[a]
            = ?b;
            ????????????tay.update(??num[a],?
            - 1 ?);
            ????????????tay.update(??num[b],?
            - 1 ?);
            ????????????num[b]
            += ?num[a];
            ????????????tay.update(?num[b],?
            1 ?);
            ????????}
            ????}
            ????
            void ?clear(){? for (? int ?i = ? 0 ;?i < ?N;? ++ i?)?find[i] = ?i,?num[i] = ? 1 ;?}
            };

            U_find?uf;

            int ?main(){
            ????scanf(
            " %d%d " , & n, & m?);
            ????tay.update(?
            1 ,?n?);
            ????
            ????
            while (?m -- ?){
            ????????
            int ?t,?u,?v,?k;
            ????????scanf(
            " %d " , & t?);
            ????????
            if (?t == ? 0 ?){
            ????????????scanf(
            " %d%d " , & u, & v?);
            ????????????uf.set_friend(?u,?v??);
            ????????}
            ????????
            else {
            ????????????scanf(
            " %d " , & k?);
            ????????????printf(
            " %d\n " ,?tay.rank(k)?);
            ????????}
            ????}
            ????
            return ? 0 ;
            }
            posted on 2009-07-14 13:31 Darren 閱讀(311) 評論(0)  編輯 收藏 引用 所屬分類: 數據結構
            久久久91人妻无码精品蜜桃HD| 久久强奷乱码老熟女网站| 亚洲中文字幕无码久久综合网| 久久九九青青国产精品| 婷婷久久五月天| A级毛片无码久久精品免费| 久久综合给合久久狠狠狠97色69| 久久久99精品一区二区| 国产成人久久精品一区二区三区| 久久精品免费观看| 久久天天躁狠狠躁夜夜网站| 国产69精品久久久久99| 久久精品亚洲精品国产色婷| 久久久噜噜噜久久中文字幕色伊伊| 99久久综合国产精品二区| 亚洲午夜无码久久久久| 欧美伊人久久大香线蕉综合69| 99久久免费国产精品| 久久午夜电影网| 久久婷婷五月综合国产尤物app| 99久久精品免费国产大片| 亚洲成色WWW久久网站| 欧洲成人午夜精品无码区久久| 久久精品女人天堂AV麻| 国产高潮国产高潮久久久91 | 久久综合中文字幕| 久久亚洲精品成人无码网站 | 亚洲成色999久久网站| 久久精品99久久香蕉国产色戒 | 国产精久久一区二区三区| 国产69精品久久久久777| 国产精品久久网| 亚洲成色WWW久久网站| 婷婷久久久亚洲欧洲日产国码AV| 99久久夜色精品国产网站| 久久久亚洲裙底偷窥综合| 久久久亚洲AV波多野结衣| 久久久久久亚洲AV无码专区| 久久精品无码午夜福利理论片| 久久99精品久久久久久久不卡| 久久精品国产一区二区三区|