|
|
题目链接：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.cppblog.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]
*/
|