POJ 3225 Help with Intervals

发表于 | 分类于 ，

题意：完成5种集合操作，输出最终的集合。

若把集合S用0\1序列来表示，则集合操作可转化为对连续子序列（区间）的操作。

\(T^C\)表示\(T\)的补集

\(S \cup T\) \(T\)区间置1
\(S \cap T\) \(T^C\)区间置0
\(S - T\) \(T\)区间置0
\(T - S\) \(S\)取反，\(T^C\)区间置0
\(S \oplus T\) \(T\)区间取反

区间操作有两种，置0\1和取反。置0\1可以用线段树打lazy tag来实现，取反也可以用打标记来实现。这里只用了一个标记，标记的种类有无标记、0、1、取反四种，打0\1标记时不需要考虑之前标记的类型，打取反标记时，若之前为0\1，则标记变为1\0，若之前为取反，则变为无标记，若之前为无标记，则变为取反标记。

最后，在完成所有操作后，下传所有标记。

开区间、闭区间的处理：把集合序列扩充为原来的3倍，对于数a：

\(3a\) )
\(3a+1\) ]or[
\(3a+2\) (

这样，(a,b)包含在[a,b]中，集合取补操作也比较直观。

这篇博客对开闭区间的处理为扩充序列为原来的2倍，对于数a：

\(2a-1\) )
\(2a\) ]or[
\(2a+1\) (

\(2a-1\)既表示a)，也表示(a-1。

坑：第一次见用开闭区间表示实数集合，开始还以为区间表示的是整数集合，看着样例输出(2,3)一脸懵…

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int M = (65535 + 1) * 3;
const int ST_SIZE = 1 << 19;

int S[M];
int tag[ST_SIZE];

void print() {
  int i, j;
  for (i = 0; i < M && S[i] == 0; i++);
  if (i >= M) {
    printf("empty set\n");
  } else {
    bool first = true;
    while (i < M) {
      for (j = i; j + 1 < M && S[j + 1] == 1; j++);
      if (first) {
        first = false;
        printf("%c%d,%d%c", i % 3 == 2 ? '(' : '[', i / 3, j / 3, j % 3 == 0 ? ')' : ']');
      } else {
        printf(" %c%d,%d%c", i % 3 == 2 ? '(' : '[', i / 3, j / 3, j % 3 == 0 ? ')' : ']');
      }
      for (i = j + 1; i < M && S[i] == 0; i++);
    }
  }
  printf("\n");
}

void set_tag(int k, int x) {
  if (x == 0 || x == 1) {
    tag[k] = x;
  } else {
    if (tag[k] == -1) tag[k] = x;
    else if (tag[k] == 0 || tag[k] == 1) tag[k] ^= 1;
    else tag[k] = -1;
  }
}

void push_down(int k, int lc, int rc) {
  if (tag[k] != -1) {
    set_tag(lc, tag[k]);
    set_tag(rc, tag[k]);
    tag[k] = -1;
  }
}

void update(int k, int l, int r, int a, int b, int x) {
  if (b <= l || r <= a) {
    return;
  } else if (a <= l && r <= b) {
    set_tag(k, x);
  } else {
    int lc = 2 * k + 1, rc = 2 * k + 2;
    int m = (l + r) / 2;
    push_down(k, lc, rc);
    update(lc, l, m, a, b, x);
    update(rc, m, r, a, b, x);
  }
}

void down(int k, int l, int r) {
  if (l == r - 1) {
    if (tag[k] == 0 || tag[k] == -1) {
      S[l] = 0;
    } else {
      S[l] = 1;
    }
  } else {
    int lc = 2 * k + 1, rc = 2 * k + 2;
    int m = (l + r) / 2;
    push_down(k, lc, rc);
    down(lc, l, m);
    down(rc, m, r);
  }
}

int main() {
  memset(S, 0, sizeof(S));
  memset(tag, -1, sizeof(tag));
  char X, lb, rb;
  int a, b;
  while (scanf(" %c %c%d%*c%d %c", &X, &lb, &a, &b, &rb) != EOF) {
    a = lb == '(' ? 3 * a + 2 : 3 * a + 1;
    b = rb == ')' ? 3 * b : 3 * b + 1;
    b++; // [a, b)
    if (X == 'U') {
      update(0, 0, M, a, b, 1);
//      for (int i = a; i < b; i++) 
//        S[i] = 1;
    } else if (X == 'I') {
      update(0, 0, M, 0, a, 0);
      update(0, 0, M, b, M, 0);
//      for (int i = 0; i < a; i++) 
//        S[i] = 0;
//      for (int i = b; i < M; i++) 
//        S[i] = 0;
    } else if (X == 'D') {
      update(0, 0, M, a, b, 0);
//      for (int i = a; i < b; i++)
//        S[i] = 0;
    } else if (X == 'C') {
      update(0, 0, M, 0, M, 2);
      update(0, 0, M, 0, a, 0);
      update(0, 0, M, b, M, 0);
//      for (int i = 0; i < M; i++)
//        S[i] ^= 1;
//      for (int i = 0; i < a; i++) 
//        S[i] = 0;
//      for (int i = b; i < M; i++) 
//        S[i] = 0;
    } else {
      update(0, 0, M, a, b, 2);
//      for (int i = a; i < b; i++)
//        S[i] ^= 1;
    }
  }
  down(0, 0, M);

  int i, j;
  for (i = 0; i < M && S[i] == 0; i++);
  if (i >= M) {
    printf("empty set\n");
  } else {
    bool first = true;
    while (i < M) {
      for (j = i; j + 1 < M && S[j + 1] == 1; j++);
      if (first) {
        first = false;
        printf("%c%d,%d%c", i % 3 == 2 ? '(' : '[', i / 3, j / 3, j % 3 == 0 ? ')' : ']');
      } else {
        printf(" %c%d,%d%c", i % 3 == 2 ? '(' : '[', i / 3, j / 3, j % 3 == 0 ? ')' : ']');
      }
      for (i = j + 1; i < M && S[i] == 0; i++);
    }
  }
  return 0;
}