其實很早就在白書上的常用技巧上 看到離散化的操作，但是之前一直沒遇到過需要離散化的題目(應該是我太菜的緣故)，所以一直也沒怎么重視，下面說說這道題目的考點，也就是離散化。

什么是離散化呢？請先自行百度理解了，一定先了解后再往下看。

?

那么該如何進行操作呢？

?

舉個例子

假如 我們有5個數

?36? ?63431? 986357? 850159901? ? 2147483640?

很明顯? 它們的大小關系為? ?36 <?63431 <?986357??<?850159901?< 2147483640

?

但是，我們并不需要知道 36? ?63431? 986357? 850159901? ? 2147483640 它們實際的大小，只需要知道它們的相對大小就可以了

?

所以我們可以把? 36轉化為 1　　63431轉化為2　　986357轉化為3　　850159901轉化為4　　2147483640轉化為5

?

這樣我們得到了新的5個數 也就是 1 2 3 4 5

同時，它們的相對大小還是一樣的? 1<2<3<4<5?

?

再用題目中的數據來舉個例子

1 5 1 4 2 6 8 10 3 4 7 10

?

我們得到了5個范圍，也就是1~4, 2~6, 8~10, 3~4, 7~10.

同樣的，我們并不需要知道它們的實際范圍，只需要知道它們的相對范圍就可以了

我們把它們每個點都整合起來? 所以就是? ?1 2 3 4 4 6 7 8 10 10

然后去掉重復的點 剩下 1 2 3 4 6 7 8 10

離散化得到新的范圍 1~4,? 2~5, 7~8, 3~4, 6~8

畫個圖會發現，新的范圍 和 舊的范圍? 的? 相對范圍，其實是一樣的.

?

下面是這道題的思路：

　　線段樹方面是常規操作，關鍵是這個離散化就有點特殊了

　　首先我們測試下這個數據

　　1
　　3
　　1 10
　　1 4
　　6?10

　　會發現常規的離散化會覆蓋點5這個點，而得到答案2，但是應該是3才對

　　這時候我們需要把每個點的右邊的數加入? 離散化的操作中來保證 連續性

　　(但是這個題目的數據太弱，導致錯誤的離散化也可以AC)

#include <algorithm> #include <iostream> #include<sstream> #include<iterator> #include<cstring> #include<string> #include<cstdio> #include<cctype> #include<vector> #include<deque> #include<map> #include<set>#define M 100005 #define inf 0x3f3f3f3f typedef long long ll; using namespace std;int T, n; int x, y, z; set<int>ans; vector<int>num;struct Data {int l, r, val, lazy; }tree[8*M];struct Data_x {int u, v; }loc_[M], loc[M];//loc_c是最初的數據，loc是離散后的數據void built(int l, int r, int k) {tree[k].l = l, tree[k].r = r;tree[k].val = tree[k].lazy = 0;if (l == r)return;int mid = (l + r) / 2;built(l, mid, k << 1);built(mid + 1, r, (k << 1) | 1); }void down(int k) {tree[k << 1].val = tree[k << 1].lazy = tree[k].lazy;tree[(k << 1) | 1].val = tree[(k << 1) | 1].lazy = tree[k].lazy;tree[k].lazy = 0; }void change(int k) {if (tree[k].l >= x && tree[k].r <= y) {tree[k].val = z;tree[k].lazy = z;return;}if (tree[k].lazy)down(k);int mid = (tree[k].l + tree[k].r) / 2;if (x <= mid)change(k << 1);if (y > mid)change((k << 1) | 1);if (tree[k << 1].val == tree[(k << 1) | 1].val) tree[k].val = tree[k << 1].val;else tree[k].val = -1; }void cal(int k) {if (tree[k].val>0) {ans.insert(tree[k].val);return;}if (!tree[k].val) return;cal(k << 1);cal((k << 1) | 1); }int main() {cin >> T;while (T--) {cin >> n;ans.clear();num.clear();for (int i = 1; i <= n; i++) {scanf("%d%d", &loc_[i].u, &loc_[i].v);//讀入最初的數據、//把所有的點整合在一起 num.push_back(loc_[i].u);num.push_back(loc_[i].v);//保證連續性num.push_back(loc_[i].u + 1);num.push_back(loc_[i].v + 1);}sort(num.begin(), num.end());vector<int>::iterator iter = unique(num.begin(), num.end());//去重//得到新的范圍for (int i = 1; i <= n; i++) {loc[i].u = lower_bound(num.begin(), iter,loc_[i].u) - num.begin();loc[i].v = lower_bound(num.begin(), iter, loc_[i].v) - num.begin();loc[i].u++;loc[i].v++;}built(1, M, 1);for (int i = 1; i <= n; i++) {x = loc[i].u, y = loc[i].v, z = i;change(1);}cal(1);cout << ans.size() << endl;}return 0; }

?

轉載于:https://www.cnblogs.com/caibingxu/p/10805640.html

總結

以上是生活随笔為你收集整理的POJ - 2528 线段树+离散化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。