线段树六题

线段树（Segment Tree）是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。 对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2,b]。因此线段树是满二叉树，最后的子节点数目为N，即整个线段区间的长度 使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。——维基百科
其实按照我的理解，线段树不是二叉搜索树，也不是完全二叉树，只不过是按照完全二叉树存储而已，而且这样存储空间复杂度(4N)。 上星期在练线段树（五个晚上+1整天才做了6题T_T），下面就把这6题的解题报告贴出来。

  1. PKU3264

这题作为线段树入门题目再合适不过了，这题就是求区间最小/最大值之差，用RMQ比方说ST算法也可以过，不过貌似线段树更快点。此题不涉及修改，练习从数组构建线段树和线段树的查询。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

{$inline on}
var n,q,a,b,i,mina,maxa:longint;
    Amin,Amax:array[1..50000*4]of longint;
    x:array[1..50000]of longint;
function min(const a,b:longint):longint;inline;begin if(a<b)then exit(a)else exit(b)end;
function max(const a,b:longint):longint;inline;begin if(a>b)then exit(a)else exit(b)end;
procedure build(const p,left,right:longint);
  var mid:longint;
  begin
    if left=right then begin
      Amin[p]:=x[left];
      Amax[p]:=x[left];
      exit;
    end;
    mid:=(left+right)shr 1;
    build(p shl 1,left,mid);
    build(p shl 1+1,mid+1,right);
    Amin[p]:=min(Amin[p shl 1],Amin[p shl 1+1]);
    Amax[p]:=max(Amax[p shl 1],Amax[p shl 1+1]);
  end;
procedure query(const p,left,right:longint);
  var mid:longint;
  begin
    if (a<=left)and(right<=b) then begin
      mina:=min(mina,Amin[p]);
      maxa:=max(maxa,Amax[p]);
      exit;
    end;
    mid:=(left+right)shr 1;
    if a<=mid then query(p shl 1,left,mid);
    if mid+1<=b then query(p shl 1+1,mid+1,right);
  end;
begin
  Amin[1]:=maxlongint;
  Amax[1]:=0;
  readln(n,q);
  for i:=1 to n do readln(x[i]);
  build(1,1,n);
  for i:=1 to q do begin
    readln(a,b);
    mina:=maxlongint;
    maxa:=0;
    query(1,1,n);
    writeln(maxa-mina);
  end;
end.

  1. PKU2777

这题就是统计颜色数量。由于颜色数较少（<=30），所以可以用二进制压缩，在线段树中直接存储每一段的颜色集合。每次查询/修改的时候，如果发现当前线段树处理区间[l,r]如果包含在查询/修改区间[st,ed]内的话，就直接返回值/修改，不再进行递归，这样就能做到节省时间的目的。不过这样要注意一个问题，就是某一段只剩下一种颜色的时候，也就是s[p] == s[p]&-s[p]的时候，必须对其孩子进行遗传，因为上一次覆盖操作时并未对孩子的信息进行修改，此时若不进行修改，那么孩子的信息就仍然是错误的。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

var l,t,o,st,ed,x:longint;
    c:char;
    a:array[1..100000*4]of longint;
function count(x:longint):longint;
  begin
    x:=(x and $55555555) + ((x shr 1) and $55555555);
    x:=(x and $33333333) + ((x shr 2) and $33333333);
    x:=(x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F);
    x:=(x and $00FF00FF) + ((x shr 8) and $00FF00FF);
    x:=(x and $0000FFFF) + ((x shr 16) and $0000FFFF);
    exit(x);
  end;
procedure change(const p,left,right:longint);
  var mid:longint;
  begin
    if (st<=left)and(right<=ed) then begin
      a[p]:=1 shl (x-1);
      exit;
    end;
    if a[p]=a[p]and-a[p] then begin
      a[p shl 1]:=a[p];
      a[p shl 1+1]:=a[p];
    end;
    mid:=(left+right)shr 1;
    if st<=mid then change(p shl 1,left,mid);
    if mid+1<=ed then change(p shl 1+1,mid+1,right);
    a[p]:=a[p shl 1] or a[p shl 1+1];
  end;
function query(const p,left,right:longint):longint;
  var mid:longint;
  begin
    if (st<=left)and(right<=ed) then exit(a[p]);
    if a[p]=a[p]and-a[p] then begin
      a[p shl 1]:=a[p];
      a[p shl 1+1]:=a[p];
    end;
    mid:=(left+right)shr 1;
    query:=0;
    if st<=mid then query:=query or query(p shl 1,left,mid);
    if mid+1<=ed then query:=query or query(p shl 1+1,mid+1,right);
  end;
begin
  readln(l,t,o);
  a[1]:=1;
  while o>0 do begin
    dec(o);
    read(c,st,ed);
    if st>ed then begin
      t:=st;st:=ed;ed:=t;
    end;
    if c='C' then begin
      readln(x);
      change(1,1,l);
    end else begin
      readln;
      writeln(count(query(1,1,l)));
    end;
  end;
end.

  1. PKU2528

这题和上面那题很类似，一样求的是颜色数。不过和上一题不一样的是颜色特别多，这就意味着我们不能够用一个长整型来保存颜色集合。仔细看题目，可以发现这题有一个特点：只有一次询问！

所以我们要换一种思路。如果一整段只有一种颜色，那么线段树里面保存的就是这个唯一颜色的编号；如果一段有多种颜色，那么我们就在线段树中用一个特殊值-1保存，表示这里有多个颜色。修改的时候显然线段树处理区间[l,r]如果包含在修改区间[st,ed]中，那么直接把颜色标记成待修改的颜色，不递归处理。查询的时候，先把一个布尔数组清空，然后处理线段树，如果颜色为-1，就递归处理；否则把那个颜色加进布尔数组中。

遗传的时候还要注意，如果当前颜色不是-1，那么必须马上对左右孩子遗传。

另外此题还得离散化，一个比较土的方法就是排序后二分查找，这样保证预处理时间为O(nlogn)，查询时间为O(logn)。离散化的时候要注意一个问题：比方说一个长度为10的墙，按顺序贴上如下海报：[1,10],[1,3],[6,10]，一共可以看到3张海报。如果在离散化的时候只把每张海报的左右两边加进数组的那么离散完后的结果是：[1,4],[1,2],[3,4]，只能够看到2张海报。所以有个处理的土方法，就是把所有区间+1 -1的点一起离散化了，这样虽然需要O(6n)的空间，但是保证了正确性和简单性！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

struct range {
  int l, r;
} a[10000];
int st, ed, n, L, T, s[40000*4], b[60000], B[60000];
bool exist[10001];
int binary(const int x) {
  int l = 0, r = L-1;
  while (r != l) {
    int mid = (l+r)>>1;
    if (B[mid] == x)
      return mid+1;
    else if (B[mid] > x)
      r = mid-1;
    else
      l = mid+1;
  }
  return l+1;
}
void modify(const int p, const int left, const int right, const int x) {
  if (st <= left && right <= ed) {
    s[p] = x;
    return;
  }
  if (s[p] != -1) s[p*2] = s[p*2+1] = s[p];
  int mid = (left+right)>>1;
  if (st <= mid) modify(p*2, left, mid, x);
  if (mid+1 <= ed) modify(p*2+1, mid+1, right, x);
  if (s[p*2] != s[p*2+1] || s[p*2] == -1 || s[p*2+1] == -1)
    s[p] = -1;
  else
    s[p] = x;
}
void query(const int p, const int left, const int right) {
  if (s[p] != -1) {
    s[p*2] = s[p*2+1] = s[p];
    exist[s[p]] = true;
    return;
  }
  int mid = (left+right)>>1;
  query(p*2, left, mid);
  query(p*2+1, mid+1, right);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> T;
  while (T--) {
    memset(exist, 0, sizeof(exist));

    cin >> n;
    for (int i = 0; i < n; ++i) {
      cin >> a[i].l >> a[i].r;
      b[i*6] = a[i].l, b[i*6+1] = a[i].r,
      b[i*6+2] = a[i].l+1, b[i*6+3] = a[i].l-1,
      b[i*6+4] = a[i].r+1, b[i*6+5] = a[i].r-1;
    }
    sort(b, b+6*n-1);
    L = -1;
    B[++L] = b[1];
    for (int i = 1; i < 6*n-1; ++i)
      if (b[i] != b[i-1]) B[++L] = b[i];

    s[1] = 0;
    for (int i = 0; i < n; ++i) {
      st = binary(a[i].l), ed = binary(a[i].r);
      modify(1, 1, L, i+1);
    }

    st = 1, ed = L;
    query(1, 1, L);
    int ans = 0;
    for (int i = 1; i <= n; ++i)
      if (exist[i]) ++ans;
    cout << ans << endl;
  }
}

  1. PKU3468

这题就是修改和求区间和，可以用树状数组做。用线段树的话，可以用一种叫做lazy-tag的方法来优化：在线段树中存两个值(sum, tag)，sum表示这段区间的和，tag表示自己以及自己的孩子每个数都可以加上tag。每一次更新前先clear tag：sum+=tag*(right-left+1); sons’ tag+=tag; tag=0。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#include <iostream>
using namespace std;

int n, Q, st, ed;
long long a[100000], x;
struct SegmentTree
{
  long long sum, tag;
} s[100000*4];
void clear(const int p, const int left, const int right)
{
  if (s[p].tag)
  {
    s[p].sum += s[p].tag*(right-left+1);
    if (left != right)
    {
      s[2*p].tag += s[p].tag;
      s[2*p+1].tag += s[p].tag;
    }
    s[p].tag = 0;
  }
}
void build(const int p, const int left, const int right)
{
  if (left == right)
  {
    s[p].sum = a[left-1];
    s[p].tag = 0;
    return;
  }
  int mid = (left+right)>>1;
  build(p*2, left, mid);
  build(p*2+1, mid+1, right);
  s[p].sum = s[p*2].sum+s[p*2+1].sum;
  s[p].tag = 0;
}
long long query(const int p, const int left, const int right)
{
  clear(p, left, right);
  if (st <= left && right <= ed) return s[p].sum;
  int mid = (left+right)>>1;
  long long res = 0;
  if (st <= mid) res += query(2*p, left, mid);
  if (mid+1 <= ed) res += query(2*p+1, mid+1, right);
  clear(2*p, left, mid);
  clear(2*p+1, mid+1, right);
  return res;
}
void modify(const int p, const int left, const int right)
{
  clear(p, left, right);
  if (st <= left && right <= ed)
  {
    s[p].tag += x;
    return;
  }
  int mid = (left+right)>>1;
  if (st <= mid) modify(2*p, left, mid);
  if (mid+1 <= ed) modify(2*p+1, mid+1, right);
  clear(2*p, left, mid);
  clear(2*p+1, mid+1, right);
  s[p].sum = s[2*p].sum+s[2*p+1].sum;
}
int main()
{
  ios::sync_with_stdio(false);
  cin >> n >> Q;
  for (int i = 0; i < n; ++i) cin >> a[i];
  build(1, 1, n);
  while (Q--)
  {
    char o;
    cin >> o >> st >> ed;
    if (o == 'Q')
      cout << query(1, 1, n) << endl;
    else
    {
      cin >> x;
      modify(1, 1, n);
    }
  }
}

  1. BZOJ1230

这题其实跟上一题是一样样的，所谓把[l,r]取反，也就是count=(r-l+1)-count。一样用lazy-tag控制遗传，只不过tag只要用一个bool保存就好了，决定是否要进行翻转。值得注意的是，翻转两次等于不翻转。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <iostream>
using namespace std;

int n, Q, st, ed;
int a[100000], x;
struct SegmentTree
{
  int count;
  bool reverse;
} s[100000*4];
void clear(const int p, const int left, const int right)
{
  if (s[p].reverse)
  {
    s[p].count = right-left+1-s[p].count;
    if (left != right)
    {
      s[2*p].reverse = !s[2*p].reverse;
      s[2*p+1].reverse = !s[2*p+1].reverse;
    }
    s[p].reverse = false;
  }
}
int query(const int p, const int left, const int right)
{
  clear(p, left, right);
  if (st <= left && right <= ed) return s[p].count;
  int mid = (left+right)>>1, res = 0;
  if (st <= mid) res += query(2*p, left, mid);
  if (mid+1 <= ed) res += query(2*p+1, mid+1, right);
  clear(2*p, left, mid);
  clear(2*p+1, mid+1, right);
  return res;
}
void modify(const int p, const int left, const int right)
{
  clear(p, left, right);
  if (st <= left && right <= ed)
  {
    s[p].reverse = !s[p].reverse;
    return;
  }
  int mid = (left+right)>>1;
  if (st <= mid) modify(2*p, left, mid);
  if (mid+1 <= ed) modify(2*p+1, mid+1, right);
  clear(2*p, left, mid);
  clear(2*p+1, mid+1, right);
  s[p].count = s[2*p].count+s[2*p+1].count;
}
int main()
{
  ios::sync_with_stdio(false);
  cin >> n >> Q;
  while (Q--)
  {
    int o;
    cin >> o >> st >> ed;
    if (o)
      cout << query(1, 1, n) << endl;
    else
      modify(1, 1, n);
  }
}

  1. PKU1151

这题可以理解为矩形切割，计算每一个小矩形的面积。考虑每个矩形的上下两条边（如果看作直角坐标系，也就是两个y坐标），把这些平行于x轴的线段所在的直线按照坐标从小到大排序，每次我们取出相邻的两端，这个时候已经能够算出两条线段之间的间距了，我们只需要知道另一个方向的长度就能够w*h算出矩形的面积。 现在真正要考虑每一个矩形的上下边界。我们把下面那条边作为一个进入事件——在线段树上覆盖区间，把上面那条边作为一个退出事件——在线段树上删除区间。每一次扫描上下相邻两条扫描线的时候，找出符合上下边界在线上的线段，更新线段树。 更新线段树的时候，要几下每一段中覆盖的长度length和被覆盖的次数count。当count=0时，length=sigma(two sons’ length)；当count!=0时，length=right-left。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;

const double eps = 1e-9;
class Line
{
public:
  double left, right, y;
  bool ToDelete;
  Line(const double _left = .0, const double _right = .0, const double _y = .0, const bool _ToDelete = false):
    left(_left), right(_right), y(_y), ToDelete(_ToDelete) { }
  bool operator< (const Line& rhs) const
  {
    return y < rhs.y;
  }
} line[202];
struct SegmentTree
{
  double length;
  int count;
} s[202*8];
int n, T, ny, nl, nx, st ,ed, x;
double yy[202], xx[202];
inline bool EqualOfFloats(const double &a, const double &b)
{
    return fabs(a-b) < eps;
}
int Find(const double x)
{
  int left = 0, right = nx-1;
  while (left != right)
  {
    int mid = (left+right)>>1;
    if (xx[mid] == x)
      return mid+1;
    else if (xx[mid] < x)
      left = mid+1;
    else
      right = mid-1;
  }
  return left+1;
}
void Modify(const int p, const int left, const int right)
{
  if (st <= left && right <= ed)
  {
    if (s[p].count+x == 0)
      s[p].length = s[2*p].length+s[2*p+1].length;
    else if (s[p].count+x == 1)
      s[p].length = xx[right-1]-xx[left-1];
    s[p].count += x;
    return;
  }
  if (right-left <= 1) return;
  int mid = (left+right)>>1;
  if (st <= mid) Modify(p*2, left, mid);
  if (mid <= ed) Modify(p*2+1, mid, right);
  if (!s[p].count) s[p].length = s[2*p].length+s[2*p+1].length;
}
int main()
{
  ios::sync_with_stdio(false);
  while (cin >> n, n)
  {
    ny = nl = nx = 0;
    for (int i = 0; i < n; ++i)
    {
      double x1, x2, y1, y2;
      cin>> x1 >> y1 >> x2 >> y2;
      xx[nx++] = x1, xx[nx++] = x2;
      yy[ny++] = y1, yy[ny++] = y2;
      line[nl++] = Line(x1, x2, y1, false);
      line[nl++] = Line(x1, x2, y2, true);
    }
    sort(line, line+nl);
    sort(yy, yy+ny);
    ny = unique(yy, yy+ny, EqualOfFloats)-yy;
    sort(xx, xx+nx);
    nx = unique(xx, xx+nx, EqualOfFloats)-xx;

    memset(s, 0, sizeof(s[0])*8*nx);
    double S = .0;
    int NextLine = 0;
    for (int i = 0; i < ny-1; ++i)
    {
      while (NextLine < nl && line[NextLine].y == yy[i])
      {
        st = Find(line[NextLine].left), ed = Find(line[NextLine].right);
        x = line[NextLine++].ToDelete ? -1 : 1;
        Modify(1, 1, nx);
      }
      S += (yy[i+1]-yy[i])*s[1].length;
    }
    cout << "Test case #" << ++T << endl;
    cout << "Total explored area: " << fixed << setprecision(2) << S << endl << endl;
  }
}

另外，因为这题的数据太小，所以O(n^2)的朴素算法比O(nlogn)的线段树快。大体的思路有点类似，但又有些不一样，具体的可以看程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <cmath>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;

const double eps = 1e-9;
class Line
{
public:
  double top, bottom, x;
  bool ToDelete;
  Line(const double _top = .0, const double _bottom = .0, const double _x = .0, const bool _ToDelete = false):
    top(_top), bottom(_bottom), x(_x), ToDelete(_ToDelete) { }
  bool operator< (const Line& rhs) const
  {
    return x < rhs.x;
  }
} line[202];
int n, T, ny, nl;
double yy[202];
inline bool EqualOfFloats(const double &a, const double &b)
{
    return fabs(a-b) < eps;
}
int main()
{
  ios::sync_with_stdio(false);
  while (cin >> n, n)
  {
    ny = nl = 0;
    for (int i = 0; i < n; ++i)
    {
      double x1, x2, y1, y2;
      cin>> x1 >> y1 >> x2 >> y2;
      yy[ny++] = y1, yy[ny++] = y2;
      line[nl++] = Line(y2, y1, x1, false);
      line[nl++] = Line(y2, y1, x2, true);
    }
    sort(line, line+nl);
    sort(yy, yy+ny);
    ny = unique(yy, yy+ny, EqualOfFloats)-yy;

    double S = .0;
    for (int i = 0; i < ny-1; ++i)
    {
      int count = 0;
      double nowX = .0;
      for (int j = 0; j < nl; ++j)
        if (line[j].bottom <= yy[i] && yy[i+1] <= line[j].top)
        {
          if (!count) nowX = line[j].x;
          if (line[j].ToDelete) --count;
          else ++count;
          if (!count) S += (yy[i+1]-yy[i])*(line[j].x-nowX);
        }
    }
    cout << "Test case #" << ++T << endl;
    cout << "Total explored area: " << fixed << setprecision(2) << S << endl << endl;
  }
}

Comments