Skip to content

Segment Tree 2

  • K-th Number

    • 不用离散化,给定区间大小就可以建树。离散化本身也是O(n)的!
    • 手动归并排序(pushup)。
    • [4], upper_bound(4) -> 1, lower_bound(4) -> 0.
    • Binary Search !!!
    #define  _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <vector>
    #define lc 2*rt+1
    #define rc 2*rt+2
    using namespace std;
    
    const int maxn = 100005;
    int N, M, a, b, c;
    
    int arr[maxn];
    
    struct node {
      int l, r;
      vector<int> v;
    } t[maxn << 2];
    
    void merge(vector<int>&a, vector<int>&b, vector<int>&c) {
      int la = a.size();
      int lb = b.size();
      int i = 0, j = 0;
      while (i < la && j < lb) {
          if (a[i] <= b[j]) c.push_back(a[i++]);
          else c.push_back(b[j++]);
      }
      while (i < la) c.push_back(a[i++]);
      while (j < lb) c.push_back(b[j++]);
    }
    
    void build(int rt, int l, int r) {
      t[rt].l = l;
      t[rt].r = r;
      if (l == r) {
          t[rt].v.push_back(arr[l]);
          return;
      }
      build(lc, l, (l + r) / 2);
      build(rc, (l + r) / 2 + 1, r);
      merge(t[lc].v, t[rc].v, t[rt].v);
    }
    
    int lt(int rt, int l, int r, int v) {
      if (t[rt].l == l && t[rt].r == r) {
          int num = upper_bound(t[rt].v.begin(), t[rt].v.end(), v) - t[rt].v.begin();
          return num;
      }
      int mid = (t[rt].l + t[rt].r) / 2;
      if (r <= mid) return lt(lc, l, r, v);
      else if (l > mid) return lt(rc, l, r, v);
      else return lt(lc, l, mid, v) + lt(rc, mid + 1, r, v);
    }
    
    int query(int l, int r, int K) {
      //binary search
      int L = -1e9 - 1, R = 1e9 + 1;  // max+1, min-1
      while (L + 1 < R) {
          int M = (L + R) / 2;
          int n = lt(0, l, r, M);
          if (n < K) L = M;
          else R = M;
      }
      return R;
    }
    
    int main() {
      scanf("%d%d", &N, &M);
      for (int i = 0; i < N; i++) scanf("%d", arr + i);
      build(0, 0, N - 1);
      for (int i = 0; i < M; i++) {
          scanf("%d%d%d", &a, &b, &c);
          int res = query(a - 1, b - 1, c);
          cout << res << endl;
      }
    }
    
  • Atlantis

    • 暴力离散标记法
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define maxn 510
    using namespace std;
    
    int n;
    double x2,y2,x1,y1;
    bool flag[maxn][maxn];
    double X[maxn],Y[maxn];
    struct node
    {
        double x1,y1,x2,y2;
    } p[maxn];
    
    int bsearch(double *a,int l,int r,double target)
    {
        int low=l,high=r;
        while(low<=high)
        {
            int mid=(low+high)>>1;
            if(a[mid]==target)
            {
                return mid;
            }
            if(a[mid]>target)
                high=mid-1;
            else
                low=mid+1;
        }
    }
    
    int main()
    {
        int case1=0;
        while(scanf("%d",&n)!=EOF)
        {
            memset(flag,false,sizeof(flag));
            memset(X,0,sizeof(X));
            memset(Y,0,sizeof(Y));
            case1++;
            if(n==0) break;
            int t1=0,t2=0;
            for(int i=0; i<n; i++)
            {
                scanf("%lf%lf%lf%lf",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2);
                X[t1++]=p[i].x1;X[t1++]=p[i].x2;
                Y[t2++]=p[i].y1;Y[t2++]=p[i].y2;
            }
            sort(X,X+2*n);
            sort(Y,Y+2*n);
            for(int i=0; i<n; i++)
            {
                int xpos=bsearch(X,0,t1-1,p[i].x1);
                int ypos=bsearch(Y,0,t2-1,p[i].y1);
                int xpos1=bsearch(X,0,t1-1,p[i].x2);
                int ypos1=bsearch(Y,0,t2-1,p[i].y2);
                for(int i=xpos; i<xpos1; i++)
                {
                    for(int j=ypos; j<ypos1; j++)
                    {
                        flag[i][j]=true;
                    }
                }
            }
            double sum=0;
            for(int i=0; i<t1; i++)
            {
                for(int j=0; j<t2; j++)
                {
                    if(flag[i][j])
                        sum+=((X[i+1]-X[i])*(Y[j+1]-Y[j]));
                }
            }
            printf("Test case #%d\n",case1);
            printf("Total explored area: %.2lf\n",sum);
            printf("\n");
        }
        return 0;
    }
    
    • 线段树扫描线

      十分烦人的做法。。。

    #define  _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <string>
    #include <cstring>
    #include <stack>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #define ll long long
    #define lc 2*rt+1
    #define rc 2*rt+2
    using namespace std;
    
    const int maxn = 105;
    int N;
    double ans;
    double X1, Y1, X2, Y2;
    
    struct node {
      int l, r;
      double len;
      int cover;
    } T[maxn << 3];
    
    struct line {
      double x, y1, y2;
      int flag;  // is_left
      bool operator< (const line& b) const { return x < b.x; }
    } L[maxn << 1];
    
    int ycnt = 0;
    double ys[maxn << 1];
    
    void build(int rt, int l, int r) {
      T[rt].l = l;
      T[rt].r = r;
      if (l + 1 == r) return;
      build(lc, l, (l + r) / 2);
      build(rc, (l + r) / 2, r);
    }
    
    int cnt = 0;
    void add_line() {
      L[cnt].x = X1;
      L[cnt].y1 = Y1;
      L[cnt].y2 = Y2;
      L[cnt++].flag = 1;
      L[cnt].x = X2;
      L[cnt].y1 = Y1;
      L[cnt].y2 = Y2;
      L[cnt++].flag = -1;
    }
    
    void getlen(int rt) {
      if (T[rt].cover) T[rt].len = ys[T[rt].r] - ys[T[rt].l]; 
      else if (T[rt].l + 1 == T[rt].r) T[rt].len = 0;  // required!
      else T[rt].len = T[lc].len + T[rc].len;
    }
    
    void update(int rt, line& ln) {
      if (ys[T[rt].l] >= ln.y1 && ys[T[rt].r] <= ln.y2) {  // node's region is covered by line
          T[rt].cover += ln.flag;  // left right
          getlen(rt); 
          return;
      }
      if (T[rt].l + 1 == T[rt].r) return;
      int mid = (T[rt].r + T[rt].l) / 2;
      if (ln.y1 <= ys[mid]) update(lc, ln);
      if (ln.y2 > ys[mid]) update(rc, ln);
      getlen(rt);
    }
    
    
    int main() {
      int cas = 0;
      while (cin >> N) {
          if (cas) puts("");
          if (N == 0) break;
          cnt = 0, ycnt = 0;
          for (int i = 0; i < N; i++) {
              scanf("%lf%lf%lf%lf", &X1, &Y1, &X2, &Y2);
              add_line();
              ys[ycnt++] = Y1;
              ys[ycnt++] = Y2;
          }
          sort(L, L + cnt);
          sort(ys, ys + ycnt);
          ycnt = unique(ys, ys + ycnt) - ys;
          build(0, 0, cnt - 1); // tree for x
          ans = 0;
          update(0, L[0]);
          for (int i = 1; i < 2 * N; i++) {
              double tmp = (L[i].x - L[i - 1].x) * T[0].len;
              //cout << "add "<<L[i].x - L[i-1].x<<"*"<<T[0].len<<"=" << tmp << endl;;
              ans += tmp;
              update(0, L[i]);
          }
          printf("Test case #%d\n", ++cas);
          printf("Total explored area: %.2f\n", ans);
      }
    }
    
  • Picture

    边排序,相同x时入边在前。

    保证边重合的情况,两边不都算。

    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    #define lc 2*rt+1
    #define rc 2*rt+2
    using namespace std;
    
    const int maxn = 10005;
    int N;
    int ans;
    int X1, Y1, X2, Y2;
    
    struct LINE {
      int x, y1, y2, flag;
      LINE(int x, int y1, int y2, int f) :x(x), y1(y1), y2(y2), flag(f) {}
      bool operator< (const LINE& b) const { 
          // this line wasted me 4 hours.
          if (x == b.x) return flag>b.flag;
          return x < b.x;
      }
    };
    
    vector<LINE> xline;
    vector<int> ys;
    
    void addline() {
      xline.push_back(LINE(X1, Y1, Y2, 1));
      xline.push_back(LINE(X2, Y1, Y2, -1));
      ys.push_back(Y1);
      ys.push_back(Y2);
    }
    
    struct node {
      int l, r;
      int cover;
      int count;
      int len;
      bool ll, rr;
    } t[maxn * 10];
    
    
    void build(int rt, int l, int r) {
      t[rt].l = l;
      t[rt].r = r;
      t[rt].count = 0;
      t[rt].cover = 0;
      t[rt].len = 0;
      t[rt].ll = false;
      t[rt].rr = false;
      if (l + 1 == r) return;
      build(lc, l, (l + r) / 2);
      build(rc, (l + r) / 2, r);
    }
    
    void getlen(int rt) {
      if (t[rt].cover > 0) {
          t[rt].len = ys[t[rt].r] - ys[t[rt].l];
          t[rt].count = 1;
          t[rt].ll = t[rt].rr = true;
      }
      else if (t[rt].l + 1 == t[rt].r) {  // leaves, and not covered.
          t[rt].len = 0;
          t[rt].count = 0;
          t[rt].ll = t[rt].rr = false;
      }
      else {
          t[rt].len = t[lc].len + t[rc].len;
          t[rt].count = t[lc].count + t[rc].count + ((t[lc].rr && t[rc].ll) ? -1 : 0);
          t[rt].ll = t[lc].ll;
          t[rt].rr = t[rc].rr;
      }
    }
    
    void update(int rt, LINE& ln) {
      if (ys[t[rt].l] >= ln.y1 && ys[t[rt].r] <= ln.y2) {
          t[rt].cover += ln.flag;
          getlen(rt);
          return;
      }
      int mid = (t[rt].l + t[rt].r) / 2;
      if (ln.y2 > ys[mid]) update(rc, ln);
      if (ln.y1 < ys[mid]) update(lc, ln);
      getlen(rt);
    }
    
    int main() {
      while (cin >> N) {
          if (N == 0) {
              cout << 0 << endl;
              continue;
          }
    
          xline.clear();
          ys.clear();
    
          for (int i = 0; i < N; i++) {
              cin >> X1 >> Y1 >> X2 >> Y2;
              addline();
          }
          sort(xline.begin(), xline.end());
          sort(ys.begin(), ys.end());
          ys.erase(unique(ys.begin(), ys.end()), ys.end());
    
          build(0, 0, ys.size() - 1);
          int len = xline.size();
    
          ans = 0;
          int last = 0;
          int segs = 0;
          for (int i = 0; i < len; i++) {
              update(0, xline[i]);
              if (i) {
                  ans += (xline[i].x - xline[i - 1].x) * 2 * segs;
              }
              ans += abs(t[0].len - last);
              last = t[0].len;
              segs = t[0].count;
          }
    
          cout << ans << endl;
      }
    }
    

二维线段树

  • Matrix

    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include<cstdio>
    #include<string.h>
    #define maxn 1010
    #define m ((l+r)>>1)
    #define ls (now<<1)
    #define rs (ls|1)
    using namespace std;
    
    int N;
    int tree[maxn << 2][maxn << 2];
    char op[10];
    int xl, yl, xr, yr, x, y;
    int ans;
    
    void UpDateY(int xnow, int l, int r, int now){
      cout << "UpdateY: " <<xnow <<" "<< l << "-" << r << " " << now << endl;
      if (yl <= l && r <= yr)
      {
          cout << "change " << xnow << "," << now << endl;
          tree[xnow][now] ^= 1;
          return;
      }
      if (yl <= m) UpDateY(xnow, l, m, ls);
      if (yr > m) UpDateY(xnow, m + 1, r, rs);
    }
    
    void UpDateX(int l, int r, int now){
      cout << "UpdateX: " << l << "-" << r << " " << now << endl;
      if (xl <= l && r <= xr)
      {
          UpDateY(now, 1, N, 1);
          return;
      }
      if (xl <= m) UpDateX(l, m, ls);
      if (xr > m) UpDateX(m + 1, r, rs);
    }
    
    void QueryY(int xnow, int l, int r, int now)
    {
      ans ^= tree[xnow][now];
      if (l == r) return;
      if (y <= m) QueryY(xnow, l, m, ls);
      if (y > m) QueryY(xnow, m + 1, r, rs);
    }
    
    void QueryX(int l, int r, int now)
    {
      QueryY(now, 1, N, 1);
      if (l == r) return;
      if (x <= m) QueryX(l, m, ls);
      if (x > m) QueryX(m + 1, r, rs);
    }
    
    int main() {
      int cas;
      scanf("%d", &cas);
      while (cas--)
      {
          memset(tree, 0, sizeof(tree));
          int T;
          scanf("%d %d", &N, &T);
          while (T--)
          {
              scanf("%s", op);
              if (op[0] == 'C')
              {
                  scanf("%d %d %d %d", &xl, &yl, &xr, &yr);
                  UpDateX(1, N, 1);
              }
              else
              {
                  scanf("%d %d", &x, &y);
                  ans = 0;
                  QueryX(1, N, 1);
                  printf("%d\n", ans);
              }
          }
          if (cas) puts("");
      }
      return 0;
    }