poj 2528 Mayor's posters（線段樹+離散化）

/*

poj 2528 Mayor's posters 

線段樹 + 離散化

離散化的了解：

  給你一系列的正整數， 例如 1， 4 ， 100， 1000000000， 如果利用線段樹求解的話，很明顯

  會導緻記憶體的耗盡。是以我們做一個映射關系，将範圍很大的資料映射到範圍很小的資料上

  1---->1  4----->2  100----->3  1000000000----->4

  這樣就會減少記憶體一些不必要的消耗 

  建立好映射關系了，接着就是利用線段樹求解 

*/ 

#include<iostream> 

#include<cstdio>

#include<queue> 

#include<cstring>

#include<algorithm>

#define N 10000010

#define M 10005

using namespace std;

class EDGE{

public: 

   int ld, rd;

};

int tree[M*16];//一共有M*2個端點,一個線段映射到四個點，左右端點， 左端點-1， 右端點+1， 數組的大小是線段樹最底層資料個數的4倍 

EDGE edge[M];

int p[M*4];

int hash[N];

int n;

int insert(int p, int lr, int rr, int ld, int rd){

    if(tree[p] && lr<=ld && rd<=rr)//如果目前的區間[ld, rd]被包含在[lr, rr]中，而且[lr, rr]的區間已經被覆寫 

       return 1;

    else if(lr==ld && rr==rd){

        tree[p]=1;

        return 0;

    }

    else{

        int mid=(lr+rr)>>1;

        int f1, f2, f3, f4;

        if(mid>=rd)

           f1=insert(p<<1, lr, mid, ld, rd);

        else if(mid<ld)

           f2=insert(p<<1|1, mid+1, rr, ld, rd);

        else{

       f3=insert(p<<1, lr, mid, ld, mid);

       f4=insert(p<<1|1, mid+1, rr, mid+1, rd);

        }

    tree[p]=tree[p<<1] && tree[p<<1|1];//兩個子樹都被覆寫的時候父類才會被覆寫 

    if(mid>=rd)

       return f1;

    else if(mid<ld)

       return f2;

    else return f3 && f4;

}

3

1 10

1 3

6 10

如果将一個線段離散化成兩個點，輸出地結果是2

如果是四個節點，輸出的結果就是3

而正确的結果就是3 

int main(){

   int t, i, nm;

   scanf("%d", &t);

   while(t--){

      int maxR=0;

      scanf("%d", &n);

      for(i=0; i<n; ++i){

            scanf("%d%d", &edge[i].ld, &edge[i].rd);

            p[maxR++]=edge[i].ld-1; 

            p[maxR++]=edge[i].ld;

            p[maxR++]=edge[i].rd;

            p[maxR++]=edge[i].rd+1;

      }

      sort(p, p+maxR);

      maxR=unique(p, p+maxR)-p;//元素去重 

      for(i=0, nm=0; i<maxR; ++i){

          hash[p[i]]=++nm;

      memset(tree, 0, sizeof(tree));//初始值是所有的點都沒有被覆寫 

      int ans=0;

      for(i=n-1; i>=0; --i){//由外向裡看真是個不錯的主意 

            if(!insert(1, 1, nm, hash[edge[i].ld], hash[edge[i].rd]))

               ++ans;

      printf("%d\n", ans);

   }

   return 0;

本文轉自 小眼兒 部落格園部落格，原文連結：http://www.cnblogs.com/hujunzheng/p/3819362.html，如需轉載請自行聯系原作者