http://www.notonlysuccess.com/index.php/segment-tree-complete/

hdu1698

#include <iostream> #include <stdio.h>using namespace std;const int maxn = 111111; int a[maxn]; int tree[maxn<<2];//線段樹的每一個葉子節點就是a中的元素，還有其他的非葉子節點，應該需要2*maxn+1個元素 int col[maxn<<2];//如果當前節點有標記，就要先更新當前節點，并把標記傳給孩子void pushUp(int ind) {tree[ind] = tree[2*ind] + tree[2*ind+1]; }void pushDown(int ind, int m) {if(col[ind]) {col[2*ind] = col[2*ind + 1] = col[ind];tree[2*ind] = col[ind] * (m - m/2);tree[2*ind + 1] = col[ind] * m/2;col[ind] = 0;} }void buildTree(int left, int right, int ind) {//找到葉子節點相應的位置, ind是這個節點的編號//left 和 right是這個節點所對應的范圍if (left == right) {tree[ind] = 1;col[ind] = 0;return;}int mid = (left + right)/2;buildTree(left, mid, 2*ind);buildTree(mid+1, right, 2*ind + 1);pushUp(ind);}void update(int beg,int end ,int value, int left, int right, int ind) {if(beg <=left && end >= right) {//因為pushDown會更新孩子節點，所以到達這個節點后，已經是最新的值了，不需要再更新了col[ind] = value;tree[ind] = value*(right - left + 1);return;}pushDown(ind, right - left + 1);//把標記傳給孩子節點，并更新孩子節點的值int mid = (left + right) / 2;if (mid >=beg)update(beg,end, value, left, mid, 2*ind);if (mid < end)update(beg,end,value, mid + 1, right, 2*ind+1);pushUp(ind); }int main() {int t,n, m;scanf("%d", &t);for (int i = 0; i < t ; ++i){scanf("%d%d", &n, &m);buildTree(1,n, 1);while(m--) {int a, b, c;scanf("%d%d%d", &a, &b, &c);update(a,b,c,1,n,1);}printf("Case %d: The total value of the hook is %d.\n",t+1 , tree[1]);} }

poj2528

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1const int maxn = 11111; bool hash[maxn]; int li[maxn] , ri[maxn]; int X[maxn*3]; int col[maxn<<4]; int cnt;void PushDown(int rt) {if (col[rt] != -1) {col[rt<<1] = col[rt<<1|1] = col[rt];col[rt] = -1;} } void update(int L,int R,int c,int l,int r,int rt) {if (L <= l && r <= R) {col[rt] = c;return ;}PushDown(rt);//對當前節點要往下傳遞int m = (l + r) >> 1;if (L <= m) update(L , R , c , lson);if (m < R) update(L , R , c , rson); } void query(int l,int r,int rt) {if (col[rt] != -1) {if (!hash[col[rt]]) cnt ++;hash[ col[rt] ] = true;return ;}if (l == r) return ;int m = (l + r) >> 1;query(lson);query(rson); } int Bin(int key,int n,int X[]) {int l = 0 , r = n - 1;while (l <= r) {int m = (l + r) >> 1;if (X[m] == key) return m;if (X[m] < key) l = m + 1;else r = m - 1;}return -1; } int main() {//求得有多少海報露在外面，不一定要完全露int T , n;scanf("%d",&T);while (T --) {scanf("%d",&n);int nn = 0;for (int i = 0 ; i < n ; i ++) {scanf("%d%d",&li[i] , &ri[i]);X[nn++] = li[i];X[nn++] = ri[i];}sort(X , X + nn);int m = 1;for (int i = 1 ; i < nn; i ++) {//去除重復的if (X[i] != X[i-1]) X[m ++] = X[i];}for (int i = m - 1 ; i > 0 ; i --) {//添加中間的值if (X[i] != X[i-1] + 1) X[m ++] = X[i-1] + 1;}sort(X , X + m);memset(col , -1 , sizeof(col));for (int i = 0 ; i < n ; i ++) {int l = Bin(li[i] , m , X);//二分查找，用次序替代大數int r = Bin(ri[i] , m , X);update(l , r , i , 0 , m , 1);}cnt = 0;memset(hash , false , sizeof(hash));query(0 , m , 1);printf("%d\n",cnt);}return 0; }

2）在所有不大于30000的自然數范圍內討論一個問題：已知n條線段，把端點依次輸入給你，然后有m（≤30000）個詢問，每個詢問輸入一個點，要求這個點在多少條線段上出現過。

[問題分析]

在這個問題中，我們可以直接對問題處理的區間建立線段樹，在線段樹上維護區間被覆蓋的次數。將n條線段插入線段樹，然后對于詢問的每個點，直接查詢被覆蓋的次數即可。

但是我們在這里用這道題目，更希望能夠說明一個問題，那就是這道題目完全可以不用線段樹。我們將每個線段拆成(L,+1)，(R+1,-1)的兩個事件點，每個詢問點也在對應坐標處加上一個詢問的事件點，排序之后掃描就可以完成題目的詢問。我們這里討論的問題是一個離線的問題，因此我們也設計出了一個很簡單的離線算法。線段樹在處理在線問題的時候會更加有效，因為它維護了一個實時的信息。

http://dongxicheng.org/structure/segment-tree/

總結

以上是生活随笔為你收集整理的hdu1698的全部內容，希望文章能夠幫你解決所遇到的問題。

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