線段樹5題 poj1151 poj2528 poj3246 poj3468 poj3321

acm

跟教學做的水題
https://github.com/soulmachine/acm-cheat-sheet/blob/master/%E5%8F%82%E8%80%83%E8%B5%84%E6%96%99/%E7%BA%BF%E6%AE%B5%E6%A0%91%E5%92%8C%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84%E2%80%94%E2%80%94%E5%8C%97%E5%A4%A7%E9%83%AD%E7%82%9C.pdf

poj1151

poj1151.cpp
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

#define leftidx (idx<<1)
#define rightidx (idx<<1)|1
// http://blog.csdn.net/scnu_jiechao/article/details/19584715

const int MAXN = 110;

double y[MAXN << 1];

struct Scanline {
  double x, y1, y2;
  bool is_left;

  bool operator < (const Scanline &b) const {
    return x < b.x;
  }
} scanline[MAXN << 1];

struct Node {
  int cover;
  int left, right;
  double len;
} node[MAXN << 3];

int idxOf(double x, int n) {
  return lower_bound(y, y+n, x) - y;
}

void t_build(int idx, int L, int R) {
  node[idx].left = L;
  node[idx].right = R;
  node[idx].len = 0;
  node[idx].cover = 0;
  if(L+1 == R) return;
  int M = (L + R) >> 1;
  t_build(leftidx, L, M);
  t_build(rightidx, M, R);
}

void t_maintain(int idx) {
  if(node[idx].cover > 0) {
      node[idx].len = y[node[idx].right] - y[node[idx].left];
  }
  else if(node[idx].left + 1 == node[idx].right) { // avoid out of bound
      node[idx].len = 0;
  }
  else {
      node[idx].len = node[leftidx].len + node[rightidx].len;
  }
}

void t_updateOne(int idx, int tL, int tR) {
  if(node[idx].left >= tL && node[idx].right <= tR) {
    node[idx].cover++;
    t_maintain(idx);
    return;
  }
  int M = (node[idx].left + node[idx].right) >> 1;
  if(tL < M) t_updateOne(leftidx, tL, tR);
  if(tR > M) t_updateOne(rightidx, tL, tR);
  t_maintain(idx);
}

void t_deleteOne(int idx, int tL, int tR) {
  if(node[idx].left >= tL && node[idx].right <= tR) {
    node[idx].cover--;
    t_maintain(idx);
    return;
  }
  int M = (node[idx].left + node[idx].right) >> 1;
  if(tL < M) t_deleteOne(leftidx, tL, tR);
  if(tR > M) t_deleteOne(rightidx, tL, tR);
  t_maintain(idx);
}

int main() {
  // freopen("input.txt", "r", stdin);
  int n;
  int ncase = 0;
  double x1, y1, x2, y2;
  while(scanf("%d", &n) != EOF && n) {
    for(int idx = 0; idx < n; ++idx) {
      scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
      scanline[leftidx].x = x1;
      scanline[leftidx].y1 = y1;
      scanline[leftidx].y2 = y2;
      scanline[leftidx].is_left = true;
      y[leftidx] = y1;
      scanline[rightidx].x = x2;
      scanline[rightidx].y1 = y1;
      scanline[rightidx].y2 = y2;
      scanline[rightidx].is_left = false;
      y[rightidx] = y2;
    }

    sort(y, y+2*n);
    int count = unique(y, y+2*n) - y;
    sort(scanline, scanline+2*n);
    t_build(1, 0, count-1);
    double area = 0;

    for(int i = 0; i < 2*n-1; ++i) {
      if(scanline[i].is_left) {
        t_updateOne(1, idxOf(scanline[i].y1, count), idxOf(scanline[i].y2, count));
      } else {
        t_deleteOne(1, idxOf(scanline[i].y1, count), idxOf(scanline[i].y2, count));
      }
      area += (scanline[i+1].x - scanline[i].x) * node[1].len;
    }

    printf("Test case #%d\n", ++ncase);
    printf("Total explored area: %.2f\n\n", area);
  }
  return 0;
}

poj2528

poj2528.cpp
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
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> bs;
vector<int> rbs;
vector< pair<int, int> > ininder;

struct Node {
  bool covered;
} node [1000000];

inline int LC(int i) { return (i << 1); }
inline int RC(int i) { return (i << 1) + 1; }
bool sf;

void build() {
  memset(node, 0, sizeof(node));
}

void pushDown(int idx) {
  if(node[idx].covered) {
    node[LC(idx)].covered = node[RC(idx)].covered = node[idx].covered;
  }
}

void update_query(int L, int R, int idx, int tL, int tR) {
  if(tL <= L && R <= tR || node[idx].covered) {
    if(!node[idx].covered) {
      node[idx].covered = true;
      sf = true;
    }
    return;
  }

  pushDown(idx);
  int have_space = false;
  int M = (L + R) >> 1;
  if (tL <= M) update_query(L, M, LC(idx), tL, tR);
  if (tR > M) update_query(M+1, R, RC(idx), tL, tR);

  node[idx].covered = node[LC(idx)].covered && node[RC(idx)].covered;
}

void build_bs() {
  sort( bs.begin(), bs.end() );
  bs.erase( unique( bs.begin(), bs.end() ), bs.end() );
  int bn = bs.size();
  for(int i = 0; i < bn - 1; ++i) {
    rbs.push_back(bs[i]);
    if(bs[i+1] - bs[i] > 1)
      rbs.push_back(bs[i]+1);
  }
  rbs.push_back(bs[bn - 1]);
}

void solve(int n) {
  ininder.clear();
  bs.clear();
  rbs.clear();
  build();

  int s, e, countss = 0;
  int low_idx, high_idx;
  for(int i = 0; i < n; ++i) {
    scanf("%d%d", &s, &e);
    ininder.push_back(make_pair(s, e));
    bs.push_back(s);
    bs.push_back(e);
  }
  build_bs();
  int as = rbs.size();
  for(int i = n-1; i >= 0; --i) {
    sf = false;
    low_idx = find(rbs.begin(), rbs.end(), ininder[i].first) - rbs.begin();
    high_idx = find(rbs.begin(), rbs.end(), ininder[i].second) - rbs.begin();
    update_query(1, as, 1, low_idx+1, high_idx+1);
    if(sf) countss++;
  }
  printf("%d\n", countss);
}

int main () {
  // freopen("input.txt", "r", stdin);
  int ncase, n;
  scanf("%d", &ncase);
  for(;ncase-- > 0;) {
    scanf("%d", &n);
    solve(n);
  }
  return 0;
}

poj3246

poj3246.cpp
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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int arr[200005];

struct Node {
  int minv, maxv;
} node [400100];

int LC(int i) { return (i << 1); }
int RC(int i) { return (i << 1) + 1; }

void build() {
  memset(node, 0, sizeof(node));
}

void update(int L, int R, int idx, int pos, int value) {
  if(L == R) {
    node[idx].minv = node[idx].maxv = value;
    return;
  }
  int M = (L + R) >> 1;
  if(pos <= M) update(L, M, LC(idx), pos, value);
  if(pos > M) update(M+1, R, RC(idx), pos, value);

  node[idx].minv = min(node[LC(idx)].minv, node[RC(idx)].minv);
  node[idx].maxv = max(node[LC(idx)].maxv, node[RC(idx)].maxv);
}

int queryMin(int L, int R, int idx, int tL, int tR) {
  if(tL <= L && R <= tR) {
    return node[idx].minv;
  }
  int minv = 1 << 20;
  int M = (L + R) >> 1;
  if (tL <= M) minv = min(minv, queryMin(L, M, LC(idx), tL, tR));
  if (tR > M) minv = min(minv, queryMin(M+1, R, RC(idx), tL, tR));
  return minv;
}

int queryMax(int L, int R, int idx, int tL, int tR) {
  if(tL <= L && R <= tR) {
    return node[idx].maxv;
  }
  int maxv = -1;
  int M = (L + R) >> 1;
  if (tL <= M) maxv = max(maxv, queryMax(L, M, LC(idx), tL, tR));
  if (tR > M) maxv = max(maxv, queryMax(M+1, R, RC(idx), tL, tR));
  return maxv;
}

int main () {
  int N, Q, v, x, y;
  while(scanf("%d%d", &N, &Q) != EOF) {
    build();
    for(int i = 1; i <= N; ++i) {
      scanf("%d", &v);
      update(1, N, 1, i, v);
    }
    for(int i = 0; i < Q; ++i) {
      scanf("%d%d", &x, &y);
      printf("%d\n", queryMax(1, N, 1, x, y) - queryMin(1, N, 1, x, y));
    }
  }
  return 0;
}

poj3468

poj3468.cpp
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
#include <cstdio>
#include <cstring>

typedef long long LL;

LL arr[200005];

struct Node {
  LL sum, inc;
} node [400100];

int LC(LL i) { return (i << 1); }
int RC(LL i) { return (i << 1) + 1; }

void build(int L, int R, int idx) {
  if(L == R) {
    node[idx].sum = arr[L];
    return;
  }
  int M = (L + R) >> 1;
  build(L, M, LC(idx));
  build(M+1, R, RC(idx));
  node[idx].sum = node[LC(idx)].sum + node[RC(idx)].sum;
}

void pushDown(int idx, int L, int R) {
  int m = R-L+1;
  LL &inc = node[idx].inc;
  if(inc != 0) {
    node[LC(idx)].inc += inc;
    node[RC(idx)].inc += inc;
    node[LC(idx)].sum += inc * (m-(m>>1));
    node[RC(idx)].sum += inc * (m >> 1);
    inc = 0;
  }
}

void update(int L, int R, int idx, int tL, int tR, LL value) {
  if(tL <= L && R <= tR) {
    node[idx].sum += value*(R-L+1);
    node[idx].inc += value;
    return;
  }
  pushDown(idx, L, R);
  int M = (L + R) >> 1;
  if (tL <= M) update(L, M, LC(idx), tL, tR, value);
  if(tR > M) update(M+1, R, RC(idx), tL, tR, value);

  node[idx].sum = node[LC(idx)].sum + node[RC(idx)].sum;
}

LL query(int L, int R, int idx, int tL, int tR) {
  if(tL <= L && R <= tR) {
    return node[idx].sum;
  }
  LL total = 0;
  pushDown(idx, L, R);
  int M = (L + R) >> 1;
  if (tL <= M) total += query(L, M, LC(idx), tL, tR);
  if (tR > M) total += query(M+1, R, RC(idx), tL, tR);
  return total;
}

int main() {
  // freopen("input.txt", "r", stdin);
  int N, Q, a, b;
  LL c;
  char s[2];
  LL i;
  memset(node, 0, sizeof(node));
  scanf("%d%d", &N, &Q);
  for(int i = 1; i <= N; ++i) {
    scanf("%lld", &arr[i]);
  }
  build(1, N, 1);
  for(int i = 0; i < Q; ++i) {
    scanf("%s",s);
    if(s[0] == 'Q') {
      scanf("%d%d\n", &a, &b);
      printf("%lld\n", query(1, N, 1, a, b));
    } else {
      scanf("%d%d%lld\n", &a, &b, &c);
      update(1, N, 1, a, b, c);
    }
  }

  return 0;
}

poj3321

poj3321.cpp
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
#include <cstdio>
#include <cstring>

const int MAXN = 200000;
struct Edge {
  int val, next;
} edge[(MAXN << 1) + 100];
int edgeHead[MAXN + 100];

struct TreeNode {
  int low, high, sum;
} tnode[MAXN + 100];
int cidx = 0;
bool pick[MAXN + 100];
bool visited[MAXN + 100]; // avoid it give repeat edge in different direction
int n;

inline int lowbit(int x) {
  return x & (-x);
}

void dfs(int root) {
  tnode[root].low = ++cidx;
  visited[root] = true;
  for(int i = edgeHead[root]; i; i = edge[i].next)
    if(!visited[edge[i].val])
      dfs(edge[i].val);
  tnode[root].high = cidx;
}

// from bottom to top
void addToTree(int i, int v) {
  while(i <= n) {
    tnode[i].sum += v;
    i += lowbit(i);
  }
}

// from top to bottom
int sumFromTree(int i) {
  int sum = 0;
  while(i > 0) {
    sum += tnode[i].sum;
    i -= lowbit(i);
  }
  return sum;
}

void buildTree() {
  for(int i = 1; i <= n; ++i)
    addToTree(i, 1);
}

int main() {
  int a, b;
  scanf("%d", &n);
  buildTree();
  for(int i = 1; i < n; ++i) {
    scanf("%d%d", &a, &b);
    edge[i].val = b;
    edge[i].next = edgeHead[a];
    edgeHead[a] = i;
  }
  dfs(1);
  char s[3];
  int t, v;
  scanf("%d", &t);
  for(int i = 0; i < t; ++i) {
      scanf("%s%d", s, &v);
      if(s[0] == 'C') {
        if(pick[v]) {
          addToTree(tnode[v].low, 1);
          pick[v] = false;
        } else {
          addToTree(tnode[v].low, -1);
          pick[v] = true;
        }
      } else {
        printf("%d\n", sumFromTree(tnode[v].high) - sumFromTree(tnode[v].low - 1));
      }
  }
  return 0;
}