1 /* 2 poj 2528 Mayor's posters 3 線段樹 + 離散化 4 5 離散化的理解： 6 給你一系列的正整數， 例如 1， 4 ， 100， 1000000000， 如果利用線段樹求解的話，很明顯 7 會導致內存的耗盡。所以我們做一個映射關系，將范圍很大的數據映射到范圍很小的數據上 8 1---->1 4----->2 100----->3 1000000000----->4 9 這樣就會減少內存一些不必要的消耗 10 建立好映射關系了，接著就是利用線段樹求解 11 */ 12 #include<iostream> 13 #include<cstdio> 14 #include<queue> 15 #include<cstring> 16 #include<algorithm> 17 #define N 10000010 18 #define M 10005 19 using namespace std; 20 class EDGE{ 21 public: 22 int ld, rd; 23 }; 24 int tree[M*16];//一共有M*2個端點,一個線段映射到四個點，左右端點， 左端點-1， 右端點+1， 數組的大小是線段樹最底層數據個數的4倍 25 EDGE edge[M]; 26 int p[M*4]; 27 int hash[N]; 28 int n; 29 30 int insert(int p, int lr, int rr, int ld, int rd){ 31 32 if(tree[p] && lr<=ld && rd<=rr)//如果當前的區間[ld, rd]被包含在[lr, rr]中，而且[lr, rr]的區間已經被覆蓋 33 return 1; 34 else if(lr==ld && rr==rd){ 35 tree[p]=1; 36 return 0; 37 } 38 else{ 39 int mid=(lr+rr)>>1; 40 int f1, f2, f3, f4; 41 if(mid>=rd) 42 f1=insert(p<<1, lr, mid, ld, rd); 43 else if(mid<ld) 44 f2=insert(p<<1|1, mid+1, rr, ld, rd); 45 else{ 46 f3=insert(p<<1, lr, mid, ld, mid); 47 f4=insert(p<<1|1, mid+1, rr, mid+1, rd); 48 } 49 tree[p]=tree[p<<1] && tree[p<<1|1];//兩個子樹都被覆蓋的時候父類才會被覆蓋 50 if(mid>=rd) 51 return f1; 52 else if(mid<ld) 53 return f2; 54 else return f3 && f4; 55 } 56 } 57 /* 58 3 59 1 10 60 1 3 61 6 10 62 如果將一個線段離散化成兩個點，輸出地結果是2 63 如果是四個節點，輸出的結果就是3 64 而正確的結果就是3 65 */ 66 67 int main(){ 68 int t, i, nm; 69 scanf("%d", &t); 70 while(t--){ 71 int maxR=0; 72 scanf("%d", &n); 73 for(i=0; i<n; ++i){ 74 scanf("%d%d", &edge[i].ld, &edge[i].rd); 75 p[maxR++]=edge[i].ld-1; 76 p[maxR++]=edge[i].ld; 77 p[maxR++]=edge[i].rd; 78 p[maxR++]=edge[i].rd+1; 79 } 80 sort(p, p+maxR); 81 maxR=unique(p, p+maxR)-p;//元素去重 82 for(i=0, nm=0; i<maxR; ++i){ 83 hash[p[i]]=++nm; 84 } 85 memset(tree, 0, sizeof(tree));//初始值是所有的點都沒有被覆蓋 86 int ans=0; 87 for(i=n-1; i>=0; --i){//由外向里看真是個不錯的主意 88 if(!insert(1, 1, nm, hash[edge[i].ld], hash[edge[i].rd])) 89 ++ans; 90 } 91 printf("%d\n", ans); 92 } 93 return 0; 94 }
?
)
的自動補全規則？)
