|
|
題目鏈接：http://poj.org/problem?id=3225
  /**//*
 題意：
剛開始是一個[0, 65535]的集合，要求通過一些集合操作，最后輸出最小的
的集合。如果有多個，按結束坐標最小的依次輸出，集合操作包括：
U T：S = S 并 T
I T：S = S 交 T
D T：S = S - T
C T：S = T - S
S T：S = (S - T) 并 (T - S) （集合的異或）
T為以下(a,b), (a,b], [a,b), [a,b]四種形式之一，初始集合S為空。
解法：
線段樹
思路：
以上的五種操作，其實都可以轉化成線段樹的區間并操作，首先我們建立一
顆線段樹，對應以上的區間，我們注意到這里的區間有開有閉，為了方便處理，
可以將每個區間值乘上2，比如當前讀入的區間時(a,b]，那么實際處理的其實是
[2*a+1, 2*b]這個區間，這樣做的好處是無論開閉都能映射到整點。然后再來看
集合操作如何轉化成線段樹的區間操作，首先要知道這些集合如何和線段樹的區
間一一對應，我的做法是在線段樹的區間上用01來表示當前集合的元素是否存在
。具體的對應如下：
集合的并：S 并 T，要求S中的元素仍就存在，并且引入S中沒有的而且在T中
的元素，我們只要在T區間插入一段連續的1即可。
集合的交：S 交 T，要求在S中不在T中的元素全部剔除，那么其實就是在T的
補區間內插入一段連續的0即可。
集合的差：S - T，這個形式其實可以表示成 S 交 非T，于是可以轉換成第二
種形式，就是在非T的補區間也就是T中插入一段連續的0。
集合的逆差：T - S，這個形式可以表示成 非S 交 T，那么可以先將S中的元
素進行異或，然后再在T的補區間內插入一段連續的0。
集合的對稱集：S 異或 T，如果S和T中都存在那么就將他們去掉，否則只要
有一個存在就留下來。只要在T區間內做一次異或操作即可。
這樣一來完全對應了線段樹的操作，歸根到底只有三種插入操作：插入一段連
續的0，插入一段連續的1，將某段區間的值均和1異或。而查詢操作是最后的依次
詢問。而這三種操作可以參見下面這題的題解：
http://www.shnenglu.com/menjitianya/archive/2011/04/02/143265.html
 */
#include <iostream>
using namespace std;
#define maxn 65535*2
enum Lazy_Tag  {
ZERO = 0,
ONE = 1,
XOR = 2,
TAG_MAX = 3,
};
struct Interval {
char operands;
int left, right;
  Interval() {}
Interval(char op, int l, int r) {
operands = op;
left = l;
right = r;
 }
}I[maxn*5];
char id[] = {'U', 'I', 'D', 'C', 'S'};
int find(char c) {
for(int i = 0; i < 5; i++) {
if(c == id[i])
return i;
}
}
struct Tree {
char lazy[TAG_MAX];
int Sum;
int root, l, r;
void CoverBy(int mode);
void UpdateBy(Tree* ls, Tree* rs);
void TranslateToSon();
void TranslateTo(Tree* ts);
int len() {
return r - l + 1;
}
}T[maxn*4];
int v[maxn+1];
void Build(int root, int l, int r) {
T[root].l = l;
T[root].r = r;
T[root].root = root;
T[root].Sum = 0;
int i;
for(i = 0; i < TAG_MAX; i++)
T[root].lazy[i] = 0;
if(l == r)
return ;
int mid = (l + r) >> 1;
Build(root<<1, l, mid);
Build(root<<1|1, mid+1, r);
}
void Tree::UpdateBy(Tree* ls, Tree* rs) {
Sum = ls->Sum + rs->Sum;
}
void Tree::CoverBy(int mode) {
if(mode == ZERO || mode == ONE) {
Sum = len() * mode;
lazy[mode] = 1;
lazy[mode^1] = lazy[XOR] = 0;
}else {
Sum = len() - Sum;
if(lazy[ONE]) {
lazy[ONE] = 0;
lazy[ZERO] = 1;
}else if(lazy[ZERO]) {
lazy[ZERO] = 0;
lazy[ONE] = 1;
}else
lazy[XOR] ^= 1;
}
}
void Tree::TranslateToSon() {
TranslateTo(&T[root<<1]);
TranslateTo(&T[root<<1|1]);
for(int i = 0; i < TAG_MAX; i++)
lazy[i] = 0;
}
void Tree::TranslateTo(Tree* ts){
for(int i = 0; i < TAG_MAX; i++) {
if(lazy[i]) {
ts->CoverBy(i);
}
}
}
void Insert(int root, int l, int r, int mode) {
if(l > T[root].r || r < T[root].l)
return ;
if(mode != XOR && T[root].lazy[mode]) {
return ;
}
if(l <= T[root].l && T[root].r <= r) {
T[root].CoverBy(mode);
return ;
}
T[root].TranslateToSon();
Insert(root<<1, l, r, mode);
Insert(root<<1|1, l, r, mode);
T[root].UpdateBy(&T[root<<1], &T[root<<1|1]);
}
int Query(int root, int pos) {
if(pos > T[root].r || pos < T[root].l)
return 0;
if(pos <= T[root].l && T[root].r <= pos) {
return T[root].Sum;
}
T[root].TranslateToSon();
return Query(root<<1, pos) + Query(root<<1|1, pos);
}
int main() {
char str[2][100];
int size = 0;
int i, j;
while(scanf("%s %s", str[0], str[1]) != EOF) {
int len = strlen(str[1]);
int a[2] = {0, 0}, top = 0;
for(i = 1; str[1][i]; i++) {
if(str[1][i] >= '0' && str[1][i] <= '9') {
a[top] = a[top] * 10 + (str[1][i] - '0');
}else if(str[1][i] == ',') {
top++;
}
}
a[0] *= 2; a[1] *= 2;
if(str[1][0] == '(') a[0] ++;
if(str[1][len-1] == ')') a[1]--;
I[size++] = Interval(find(str[0][0]), a[0], a[1]);
}
Build(1, 0, maxn);
for(i = 0; i < size; i++) {
if(I[i].operands == 0) {
// 集合并
Insert(1, I[i].left, I[i].right, 1);
}else if(I[i].operands == 1) {
// 集合交
Insert(1, 0, I[i].left - 1, 0);
Insert(1, I[i].right+1, maxn, 0);
}else if(I[i].operands == 2) {
// 集合差
Insert(1, I[i].left, I[i].right, 0);
}else if(I[i].operands == 3) {
// 集合逆差
Insert(1, 0, I[i].left - 1, 0);
Insert(1, I[i].right+1, maxn, 0);
Insert(1, I[i].left, I[i].right, 2);
}else if(I[i].operands == 4) {
// 集合的對稱集
Insert(1, I[i].left, I[i].right, 2);
}
}
int Min = INT_MAX;
size = 0;
for(i = 0; i <= maxn; i++) {
v[i] = Query(1, i);
}
for(i = 0; i <= maxn; i++) {
if(v[i]) {
for(j = i + 1; j <= maxn; j++) {
if(!v[j])
break;
}
I[size++] = Interval(0, i, j-1);
i = j;
}
}
if(size == 0) {
printf("empty set\n");
}else {
for(i = 0; i < size; i++) {
if(i)
printf(" ");
printf("%c%d,%d%c", I[i].left&1?'(':'[', I[i].left/2, (I[i].right+1)/2, I[i].right&1?')':']');
}
puts("");
}
return 0;
}
/**//*
U (1,65535)
D (100,1000]
U (0,65535)
D (10,65535)
D [10,10]
U (65525,65535]
U [0,0]
*/
|