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;
}