[关闭]
@LinKArftc 2015-10-06T02:40:07.000000Z 字数 8877 阅读 1055

线段树

数据结构

一张图说明什么事线段树
线段树通常配合离散化，解决 RMQ 问题，这是一种很神奇的数据结构 = =||。。。

poj 2299

题意：

线段树求逆序对个数

  1. /*
  2. ID: LinKArftc
  3. PROG: 2299.cpp
  4. LANG: C++
  5. */
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. using namespace std;
  12. #define MAXN 500010
  14. int num[MAXN], arr[MAXN], tree[MAXN << 2];
  16. int query(int val, int l, int r, int rt) {
  17.     if (l == r) {
  18.         tree[rt] ++;
  19.         return 0;
  20.     }
  21.     int mid = (l + r) >> 1;
  22.     int ret = 0;
  23.     if (val <= arr[mid]) ret = query(val, l, mid, rt << 1) + tree[rt << 1 | 1];
  24.     else ret = query(val, mid + 1, r, rt << 1 | 1);
  25.     tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
  26.     return ret;
  27. }
  29. int main() {
  30. //    freopen("input.txt", "r", stdin);
  31.     int n;
  32.     while (~scanf("%d", &n) && n) {
  33.         for (int i = 1; i <= n; i ++) {
  34.             scanf("%d", &num[i]);
  35.             arr[i] = num[i];
  36.         }
  37.         sort(arr + 1, arr + n + 1);
  38.         int tol = 1;
  39.         for (int i = 2; i <= n; i ++) {
  40.             if (arr[i] != arr[tol]) arr[++ tol] = arr[i];
  41.         }
  42.         memset(tree, 0, sizeof(tree));
  43.         long long ans = 0;
  44.         for (int i = 1; i <= n; i ++) ans += query(num[i], 1, tol, 1);
  45.         printf("%lld\n", ans);
  46.     }
  48.     return 0;
  49. }

poj 2352

题目大意：给你星星的坐标（y递增，若y相等，x递增），每个星星都有一个等级，规定它的等级就是在它左下方的星星的个数。输入所有星星后，依次输出等级为0到n-1的星星的个数。

  1. /*
  2. ID: LinKArftc
  3. PROG: 2352.cpp
  4. LANG: C++
  5. */
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. using namespace std;
  12. #define N 15010
  13. #define M 32010
  15. int tree[M << 2], cnt[N];
  17. int query(int rt, int l, int r, int L, int R) {
  18.     int mid = (l + r) >> 1;
  19.     if (L <= l && R >= r) return tree[rt];
  20.     int ret = 0;
  21.     if (L <= mid) ret += query(rt << 1, l, mid, L, R);
  22.     if (R > mid) ret += query(rt << 1 | 1, mid + 1, r, L, R);
  23.     return ret;
  24. }
  26. void update(int rt, int l, int r, int x) {
  27.     if (l == r) {
  28.         tree[rt] ++;
  29.         return;
  30.     }
  31.     int mid = (l + r) >> 1;
  32.     if (x <= mid) update(rt << 1, l, mid, x);
  33.     else update(rt << 1 | 1, mid + 1, r, x);
  34.     tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
  35. }
  37. int main() {
  38. //    freopen("input.txt", "r", stdin);
  40.     int n;
  41.     int x, y;
  42.     while (~scanf("%d", &n)) {
  43.         memset(cnt, 0, sizeof(cnt));
  44.         memset(tree, 0, sizeof(tree));
  45.         for (int i = 1; i <= n; i ++) {
  46.             scanf("%d %d", &x, &y);
  47.             x ++;
  48.             cnt[query(1, 1, M - 5, 1, x)] ++;
  49.             update(1, 1, M - 5, x);
  50.         }
  51.         for (int i = 0; i < n; i ++) {
  52.             printf("%d\n", cnt[i]);
  53.         }
  54.     }
  56.     return 0;
  57. }

poj 2528

区间覆盖
很经典的一道题，不知道哪里写挫了导致 RE，最近写线段树写死了，不想碰了，以后再改。
已经改好了，其实很简单，之前怎么就那么傻逼。。。= =（详见后文）

  1. /*
  2. ID: LinKArftc
  3. PROG: 2528.cpp
  4. LANG: C++
  5. */
  6. ////// RE
  7. //
  8. #include <cstdio>
  9. #include <iostream>
  10. #include <cstring>
  11. #include <algorithm>
  12. using namespace std;
  13. const int maxn = 10010;
  15. struct Node {
  16.     int l, r, id;
  17. } post[maxn];
  19. int vis[maxn], ans;
  20. int ll[maxn], rr[maxn];
  22. bool cmp_l(Node a, Node b) { return a.l < b.l; }
  23. bool cmp_r(Node a, Node b) { return a.r < b.r; }
  24. bool cmp_id(Node a, Node b) { return a.id < b.id; }
  26. struct Post {
  27.     bool isCover;
  28.     int l, r;
  29. } tree[maxn << 2];
  31. void build(int rt, int l, int r) {
  32.     tree[rt].isCover = 0;
  33.     tree[rt].l = l;
  34.     tree[rt].r = r;
  35.     int mid = (l + r) >> 1;
  36.     if (l == r) return ;
  37.     else {
  38.         build(rt << 1, l, mid);
  39.         build(rt << 1 | 1, mid + 1, r);
  40.     }
  41. }
  43. bool check(int rt, int l, int r) {
  44.     if (tree[rt].isCover == true) return false;
  45.     if (tree[rt].l == l && tree[rt].r == r) {
  46.         tree[rt].isCover = 1;
  47.         return true;
  48.     }
  49.     bool rec;
  50.     int mid = (tree[rt].l + tree[rt].r) >> 1;
  51.     if (r <= mid) rec = check(rt << 1, l, r);
  52.     else if (l > mid) rec = check(rt << 1 | 1, l, r);
  53.     else {
  54.         bool r1 = check(rt << 1, l, mid);
  55.         bool r2 = check(rt << 1 | 1, mid + 1, r);
  56.         rec = r1 || r2;
  57.     }
  58.     if (tree[rt << 1].isCover && tree[rt << 1 | 1].isCover) tree[rt].isCover = true;
  59.     return rec;
  60. }
  62. int main() {
  63.     freopen("input.txt", "r", stdin);
  64.     int T;
  65.     scanf("%d", &T);
  66.     while (T --) {
  67.         int n;
  68.         scanf("%d", &n);
  69.         for (int i = 1; i <= n; i ++) {
  70.             scanf("%d %d", &post[i].l, &post[i].r);
  71.             post[i].id = i;
  72.             ll[i] = post[i].l;
  73.             rr[i] = post[i].r;
  74.         }
  75.         sort(post + 1, post + n + 1, cmp_l);
  76.         int cur = 1;
  77.         ll[1] = 1;
  78.         for (int i = 2; i <= n; i ++) {
  79.             if (post[i].l == post[i-1].l) ll[i] = cur;
  80.             else ll[i] = ++ cur;
  81.         }
  82.         for (int i = 1; i <= n; i ++) {
  83.             post[i].l = ll[i];
  84.         }
  85.         sort(post + 1, post + n + 1, cmp_r);
  86.         cur = 1;
  87.         rr[1] = 1;
  88.         for (int i = 2; i <= n; i ++) {
  89.             if (post[i].r == post[i-1].r) {
  90.                 rr[i] = cur;
  91.             }
  92.             else rr[i] = ++ cur;
  93.         }
  94.         for (int i = 1; i <= n; i ++) {
  95.             post[i].r = rr[i];
  96.         }
  97.         sort(post + 1, post + n + 1, cmp_id);
  98.         build(1, 1, n);
  99.         for (int i = n; i >= 1; i --) {
  100.             if (check(1, post[i].l, post[i].r)) {
  101.                 ans ++;
  102.             }
  103.         }
  104.         printf("%d\n", ans);
  105.     }
  107.     return 0;
  108. }
  1. /*
  2. ID: LinKArftc
  3. PROG: setment_tree.cpp
  4. LANG: C++
  5. */
  6. /*
  7.  *矩形覆盖为连续型线段树，注意和离散型线段树的区别
  8.  */
  10. typedef long long ll;
  12. const int maxn = 200010;
  14. int tree[maxn << 2];
  15. int num[maxn];
  16. int n, len;
  18. map <int, int> mp;
  19. set <int> st;
  20. set <int> ans;
  22. struct Node {
  23.     int a, b;
  24.     int id;
  25. } post[maxn];
  27. void update(int rt, int l, int r, int L, int R, int id) {
  28.     if (tree[rt]) {
  29.         tree[rt << 1] = tree[rt];
  30.         tree[rt << 1 | 1] = tree[rt];
  31.         tree[rt] = 0;
  32.     }
  33.     if (L <= l && R >= r) {
  34.         tree[rt] = id;
  35.         return;
  36.     }
  37.     int mid = (l + r) >> 1;
  38.     if (R <= mid) update(rt << 1, l, mid, L, R, id);
  39.     else if (L >= mid) update(rt << 1 | 1, mid, r, L, R, id);
  40.     else {
  41.         update(rt << 1, l, mid, L, R, id);
  42.         update(rt << 1 | 1, mid, r, L, R, id);
  43.     }
  44. }
  46. void query(int rt, int l, int r) {
  47.     if (tree[rt]) {
  48.         ans.insert(tree[rt]);
  49.         return;
  50.     }
  51.     if (r - l <= 1) return;
  52.     int mid = (l + r) >> 1;
  53.     query(rt << 1, l, mid);
  54.     query(rt << 1 | 1, mid, r);
  55. }
  57. int main() {
  59.     //input;
  60.     memset(tree, 0, sizeof(tree));
  61.     scanf("%d %d", &n, &len);
  62.     for (int i = 1; i <= n; i ++) {
  63.         scanf("%d %d", &post[i].a, &post[i].b);
  64.         post[i].id = i;
  65.         st.insert(post[i].a);
  66.         st.insert(post[i].b);
  67.     }
  68.     int cur = 1;
  69.     while (!st.empty()) {
  70.         mp[*st.begin()] = cur ++;
  71.         st.erase(st.begin());
  72.     }
  73.     for (int i = 1; i <= n; i ++) {
  74.         post[i].a = mp[post[i].a];
  75.         post[i].b = mp[post[i].b];
  76.     }
  77.     for (int i = 1; i <= n; i ++) {
  78.         update(1, 1, n << 1, post[i].a, post[i].b, post[i].id);
  79.     }
  80.     query(1, 1, n << 1);
  81.     printf("%d\n", ans.size());
  83.     return 0;
  84. }

poj 3264

求区间最大值最小值
裸线段树，配合离散化

  1. /*
  2. ID: LinKArftc
  3. PROG: 3264.cpp
  4. LANG: C++
  5. */
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. using namespace std;
  12. #define N 50005
  14. int num[N], arr[N];
  15. struct Node {
  16.     int ma, mi;
  17. } tree[N << 2];
  19. void build(int rt, int l, int r) {
  20.     if (l == r) {
  21.         tree[rt].ma = num[l];
  22.         tree[rt].mi = num[l];
  23.         return;
  24.     }
  25.     int mid = (l + r) / 2;
  26.     build(rt << 1, l, mid);
  27.     build(rt << 1 | 1, mid + 1, r);
  28.     tree[rt].ma = max(tree[rt << 1].ma, tree[rt << 1 | 1].ma);
  29.     tree[rt].mi = min(tree[rt << 1].mi, tree[rt << 1 | 1].mi);
  30. }
  32. int query_ma(int rt, int l, int r, int L, int R) {
  33.     if (L <= l && R >= r) return tree[rt].ma;
  34.     int mid = (l + r) / 2;
  35.     if (R <= mid) return query_ma(rt << 1, l, mid, L, R);
  36.     if (L > mid) return query_ma(rt << 1 | 1, mid + 1, r, L, R);
  37.     return max(query_ma(rt << 1, l, mid, L, R), query_ma(rt << 1 | 1, mid + 1, r, L, R));
  38. }
  40. int query_mi(int rt, int l, int r, int L, int R) {
  41.     if (L <= l && R >= r) return tree[rt].mi;
  42.     int mid = (l + r) / 2;
  43.     if (R <= mid) return query_mi(rt << 1, l, mid, L, R);
  44.     if (L > mid) return query_mi(rt << 1 | 1, mid + 1, r, L, R);
  45.     return min(query_mi(rt << 1, l, mid, L, R), query_mi(rt << 1 | 1, mid + 1, r, L, R));
  46. }
  49. int main() {
  50. //    freopen("input.txt", "r", stdin);
  51.     int n, q;
  52.     scanf("%d %d", &n, &q);
  53.     for (int i = 1; i <= n; i ++) scanf("%d", &num[i]);
  54.     build(1, 1, n);
  55.     for (int i = 1; i <= q; i ++) {
  56.         int a, b;
  57.         scanf("%d %d", &a, &b);
  58.         int ma = query_ma(1, 1, n, a, b);
  59.         int mi = query_mi(1, 1, n, a, b);
  60.         printf("%d\n", ma - mi);
  61.     }
  63.     return 0;
  64. }

poj 3468

区间更新，区间求和
思路：裸线段树，要用 lazy 标记 add，否则肯定会超时

  1. /*
  2. ID: LinKArftc
  3. PROG: 3468.cpp
  4. LANG: C++
  5. */
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. using namespace std;
  12. #define N 100010
  14. int n, q;
  15. long long num[N];
  17. struct Node {
  18.     long long sum, add;
  19.     Node() { sum = 0; add = 0; }
  20. } tree[N << 2];
  22. void build(int rt, int l, int r) {
  23.     if (l == r) {
  24.         tree[rt].sum = num[l];
  25.         return;
  26.     }
  27.     int mid = (l + r) / 2;
  28.     build(rt << 1, l, mid);
  29.     build(rt << 1 | 1, mid + 1, r);
  30.     tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
  31. }
  33. long long query(int rt, int l, int r, int L, int R) {
  34.     if (L <= l && R >= r) return tree[rt].sum + tree[rt].add * (r - l + 1);
  35.     if (tree[rt].add != 0) {
  36.         tree[rt].sum += tree[rt].add * (r - l + 1);
  37.         tree[rt << 1].add += tree[rt].add;
  38.         tree[rt << 1 | 1].add += tree[rt].add;
  39.         tree[rt].add = 0;
  40.     }
  41.     int mid = (l + r) >> 1;
  42.     if (R <= mid) return query(rt << 1, l, mid, L, R);
  43.     if (L > mid) return query(rt << 1 | 1, mid + 1, r, L, R);
  44.     return query(rt << 1, l, mid, L, mid) + query(rt << 1 | 1, mid + 1, r, L, R);
  45. }
  47. void update(int rt, int l, int r, int L, int R, long long c) {
  48.     if (L <= l && R >= r) {
  49.         tree[rt].add += c;
  50.         return ;
  51.     }
  52.     tree[rt].sum += c * (min(R, r) - max(L, l) + 1);
  53.     int mid = (l + r) >> 1;
  54.     if (R <= mid) {
  55.         update(rt << 1, l, mid, L, R, c);
  56.         return ;
  57.     }
  58.     if (L > mid) {
  59.         update(rt << 1 | 1, mid + 1, r, L, R, c);
  60.         return ;
  61.     }
  62.     update(rt << 1, l, mid, L, mid, c);
  63.     update(rt << 1 | 1, mid + 1, r, L, R, c);
  64.     return ;
  65. }
  67. int main() {
  68. //    freopen("input.txt", "r", stdin);
  69.     while (~scanf("%d %d", &n, &q)) {
  70.         for (int i = 1; i <= n; i ++) scanf("%lld", &num[i]);
  71.         build(1, 1, n);
  72.         char sel;
  73.         int a, b;
  74.         long long c;
  75.         for (int i = 1; i <= q; i ++) {
  76.             scanf(" %c", &sel);
  77.             if (sel == 'Q') {
  78.                 scanf("%d %d", &a, &b);
  79.                 printf("%lld\n", query(1, 1, n, a, b));
  80.             } else {
  81.                 scanf("%d %d %lld", &a, &b, &c);
  82.                 update(1, 1, n, a, b, c);
  83.             }
  84.         }
  85.     }
  87.     return 0;
  88. }

poj 2991

题意: 起重机的机械臂, 由n段组成, 对某一些连接点进行旋转, 询问每次操作后的末端坐标.
思路：这一题相当恶心。。。因为后面的杆子是跟着动的，所以他们整体上的变化的角度都是一样的，这就变成了区间更新的线段树了，查询很简单，就是顶点的坐标。
线段树节点保存该区间（即第 i 到第 j 条杆子的整体，从起点到终点）的一个向量，存了 x 和 y 坐标（这是向量，不是实际在坐标系中的坐标！）。
add 数组就是 lazy 标记。因为一个向量 (x, y) 逆时针转角度 a 以后，向量变成(cos(a) * x - sin(a) * y, sin(a) * x + cos(a) * y)，所以，我们在 add 中记录当前区间逆时针转的角度。
用一个 angle 数组存相邻线段之间的角度，通过这个值和到时候要修改成的角度a来换算出逆时针转过的角度

  1. /*
  2. ID: LinKArftc
  3. PROG: 2991.cpp
  4. LANG: C++
  5. */
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. #include <cmath>
  12. const double pi = acos(-1.0);
  13. const double eps = 1e-9;
  14. const int maxn = 10010;
  16. struct Node {
  17.     double x, y;
  18.     int add;
  19.     Node(int _x, int _y, int _add) : x(_x), y(_y), add(_add) {}
  20.     Node() { add = 0; }
  21. } tree[maxn << 2];
  23. int angle[maxn];
  25. void rotate(int rt, int a) {
  26.     double x = tree[rt].x;
  27.     double y = tree[rt].y;
  28.     double ang = pi / 180 * a;
  29.     tree[rt].x = cos(ang) * x - sin(ang) * y;
  30.     tree[rt].y = sin(ang) * x + cos(ang) * y;
  31. }
  33. void build(int rt, int l, int r) {
  34.     if (l == r) {
  35.         scanf("%lf", &tree[rt].y);
  36.         tree[rt].x = 0;
  37.         return;
  38.     }
  39.     int mid = (l + r) >> 1;
  40.     build(rt << 1, l, mid);
  41.     build(rt << 1 | 1, mid + 1, r);
  42.     tree[rt].x = tree[rt << 1].x + tree[rt << 1 | 1].x;
  43.     tree[rt].y = tree[rt << 1].y + tree[rt << 1 | 1].y;
  44. }
  46. void update(int rt, int l, int r, int L, int R, int a) {
  47.     if(L <= l && R >= r) {
  48.         tree[rt].add += a;
  49.         rotate(rt, a);
  50.         return;
  51.     }
  52.     if(tree[rt].add) {
  53.         rotate(rt << 1, tree[rt].add);
  54.         rotate(rt << 1 | 1, tree[rt].add);
  55.         tree[rt << 1].add += tree[rt].add;
  56.         tree[rt << 1 | 1].add += tree[rt].add;
  57.         tree[rt].add = 0;
  58.     }
  59.     int mid = (r + l) >> 1;
  60.     if (L <= mid) update(rt << 1, l, mid, L, R, a);
  61.     if (R > mid) update(rt << 1 | 1, mid + 1, r, L, R, a);
  62.     tree[rt].x = tree[rt << 1].x + tree[rt << 1 | 1].x;
  63.     tree[rt].y = tree[rt << 1].y + tree[rt << 1 | 1].y;
  64. }
  66. int main() {
  67. //    freopen("input.txt", "r", stdin);
  68.     int n, m;
  69.     int cnt = 0;
  70.     while (~scanf("%d%d", &n, &m)) {
  71.         memset(tree, 0, sizeof(tree));
  72.         if(cnt ++) printf("\n");
  73.         build(1, 1, n);
  74.         for (int i = 1; i <= n; i ++) angle[i] = 180;
  75.         while (m --) {
  76.             int s, a;
  77.             scanf("%d%d",&s, &a);
  78.             int x = (a - angle[s] + 360) % 360;
  79.             update(1, 1, n, s + 1, n, x);
  80.             angle[s] = a;
  81.             printf("%.2lf %.2lf\n",tree[1].x + eps, tree[1].y + eps);
  82.         }
  83.     }
  84.     return 0;
  85. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注