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

            POJ 2528(線段樹+離散化)

            http://acm.pku.edu.cn/JudgeOnline/problem?id=2528
            這是一道經典的線段樹題目,另外加上離散化的方法。
                離散化:由于題目中wall有10000000bytes long,直接線段樹無疑會MLE。所以要對其離散化,基本做法是:先對所有端點坐標進行排序,用相應序號代替端點坐標構造線段樹進行計算。這樣最大的序號也只是2*n。
               在構造線段樹的節點結構體時,添加變量c。c=0時表示c線段沒有貼海報,或者貼了不止一張海報;c>0時表示貼了一張海報,并且c的值表示貼的是第幾張海報。
                線段樹更新的基本原理就是,當我們貼海報i時,如果遇到某一線段區間能夠被當前海報完全覆蓋,那么我們更新到此區間即可,即讓它的變量c更新為海報i,記錄下i的值。如果不能被海報完全覆蓋,則只是這一線段區間的部分區間需要修改,則更改這一區間的子區間即可。
              1 #include<iostream>
              2 #include<cstdio>
              3 #include<algorithm>
              4 #include<string.h>
              5 #define MAX 20001
              6 
              7 using namespace std;
              8 
              9 int c,n,ls[MAX];
             10 struct node{
             11     int l,r;
             12     int c;
             13 }tree[MAX*4];
             14 struct ln{
             15     int li,num;//num表示第幾張海報
             16 }line[MAX];
             17 int set[MAX][2];
             18 bool visit[MAX];
             19 int ans;
             20 
             21 bool cmp(struct ln a,struct ln b){
             22     return a.li<b.li;
             23 }
             24 
             25 void Inittree(int pos,int ll,int rr){
             26     tree[pos].l = ll;
             27     tree[pos].r = rr;
             28     tree[pos].c = 0;
             29     if(ll!=rr){
             30         int mid = (ll+rr)>>1;
             31         Inittree(pos*2,ll,mid);
             32         Inittree(pos*2+1,mid+1,rr);
             33     }
             34 }
             35 
             36 void Insert(int pos,int ll,int rr,int color){
             37     if(tree[pos].l == ll && tree[pos].r == rr){
             38         tree[pos].c = color;
             39         return;
             40     }
             41     if(tree[pos].c > 0 && tree[pos].c != color){
             42         tree[pos*2].c = tree[pos].c;
             43         tree[pos*2+1].c = tree[pos].c;
             44         tree[pos].c = 0;
             45     }
             46     int mid = (tree[pos].l + tree[pos].r)>>1;
             47     if(rr<=mid){
             48         Insert(pos*2,ll,rr,color);
             49     }
             50     else if(ll>mid){
             51         Insert(pos*2+1,ll,rr,color);
             52     }
             53     else{
             54         Insert(pos*2,ll,mid,color);
             55         Insert(pos*2+1,mid+1,rr,color);
             56     }
             57 }
             58 
             59 void Search(int pos){
             60     if(tree[pos].c!=0){
             61         if(!visit[tree[pos].c]){//tree[pos].c
             62             visit[tree[pos].c] = true;
             63             ans++;
             64         }
             65         return ;
             66     }
             67     Search(2*pos);
             68     Search(2*pos+1);
             69 }
             70 
             71 int main()
             72 {
             73     int i;
             74     while(scanf("%d",&c)!=EOF){
             75         while(c--){
             76             scanf("%d",&n);
             77             for(i = 0;i < n;++i){//離散化
             78                 scanf("%d%d",&set[i][0],&set[i][1]);
             79                 line[2*i].li = set[i][0];
             80                 line[2*i].num = -(i+1);//用負數表示 線段起點
             81                 line[2*i+1].li = set[i][1];
             82                 line[2*i+1].num = i+1;
             83             }
             84             sort(line,line+2*n,cmp);
             85             int temp = line[0].li,tp = 1;
             86             for(i = 0;i < 2*n;++i){
             87                 if(line[i].li != temp){
             88                     tp++;
             89                     temp = line[i].li;
             90                 }
             91                 if(line[i].num < 0){
             92                     set[-line[i].num-1][0= tp;
             93                 }
             94                 else{
             95                     set[line[i].num-1][1= tp;
             96                 }
             97             }//離散化
             98         
             99             Inittree(1,1,tp);
            100             for(i = 0;i < n;++i){
            101                 Insert(1,set[i][0],set[i][1],i+1);
            102             }
            103             memset(visit,0,sizeof(visit));
            104             ans = 0;
            105             Search(1);
            106             printf("%d\n",ans);
            107         }
            108     }
            109     return 0;
            110 }
            111 

            posted on 2009-09-16 17:07 Johnnx 閱讀(4140) 評論(2)  編輯 收藏 引用

            評論

            # re: POJ 2528(線段樹+離散化) 2009-10-13 17:03 chhaj5236

            很巧妙,學習了~  回復  更多評論   

            # re: POJ 2528(線段樹+離散化) 2013-08-12 15:11 ;;

            ;'';;';  回復  更多評論   

            導航

            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            伊人色综合久久天天人手人婷 | 国产精品久久久99| 国产精品成人精品久久久| 亚洲国产精品热久久| 久久精品国产亚洲αv忘忧草| 青青青伊人色综合久久| 久久精品一本到99热免费| 久久久无码精品亚洲日韩按摩| 天天影视色香欲综合久久| 一本久久久久久久| 久久综合色区| 久久久久综合国产欧美一区二区| 久久久久久午夜精品| 久久夜色精品国产亚洲av| 无码精品久久久久久人妻中字| 久久综合九色欧美综合狠狠| 色欲久久久天天天综合网| 99久久精品免费国产大片| 中文字幕无码av激情不卡久久| 久久无码精品一区二区三区| 亚洲AV成人无码久久精品老人| 亚洲成色999久久网站| 99精品久久久久久久婷婷 | 国产成人综合久久久久久| 四虎国产精品成人免费久久| 日本精品久久久久影院日本| 国产精品久久久久天天影视| 久久久久亚洲AV无码网站| 色综合久久88色综合天天 | 久久国产精品久久精品国产| 丁香五月网久久综合| 久久久久高潮综合影院| 久久精品国产精品亚洲| 伊人久久无码精品中文字幕| 国产精品va久久久久久久| MM131亚洲国产美女久久| 欧美精品一本久久男人的天堂| 久久亚洲欧美国产精品| 色综合久久无码五十路人妻| 波多野结衣久久一区二区| 亚洲国产成人久久综合区|