POJ 3225 Help with Intervals 线段树

本文主要是介绍POJ 3225 Help with Intervals 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这是道比较经典的线段树    详情可以参考http://www.notonlysuccess.com/index.php/segment-tree-complete/ sha崽大神的bolg

但需要注意的就是区间到点的转化了。 要保证转化后的区间满足集合的基本性质，比如删除一些区间后相应的点被删除，有可能会点删除完了，区间却还有，这就不符合了。

所以就要把每个点乘以二之类的，还有一些细节，注意一下

/*
ID: sdj22251
PROG: inflate
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 66666*2
#define INF 1000000000
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
bool used[MAXN + 5];
struct node
{int left, right, mid;int Xor, Cover;
}tree[4 * MAXN];
void make_tree(int s, int e, int C)
{tree[C].left = s;tree[C].right = e;tree[C].mid = (s + e) >> 1;tree[C].Xor = tree[C].Cover = 0;if(s == e) return;make_tree(s, tree[C].mid, L(C));make_tree(tree[C].mid + 1, e, R(C));
}
void fun_xor(int C)
{if(tree[C].Cover != -1) tree[C].Cover ^= 1;else tree[C].Xor ^= 1;
}
void down(int C)
{if(tree[C].Cover != -1){tree[L(C)].Cover = tree[R(C)].Cover = tree[C].Cover;tree[L(C)].Xor = tree[R(C)].Xor = 0;tree[C].Cover = -1;}if(tree[C].Xor){fun_xor(L(C));fun_xor(R(C));tree[C].Xor = 0;}
}
void update(int s, int e, int C, char op)
{if(tree[C].left >= s && tree[C].right <= e){if(op == 'U'){tree[C].Cover = 1;tree[C].Xor = 0;}else if(op == 'D')tree[C].Xor = tree[C].Cover = 0;else if(op == 'C' || op == 'S')fun_xor(C);return;}down(C);if(tree[C].mid >= s) update(s, e, L(C), op);else if(op == 'I' || op == 'C') tree[L(C)].Xor = tree[L(C)].Cover = 0;if(tree[C].mid < e) update(s, e, R(C), op);else if(op == 'I' || op == 'C') tree[R(C)].Xor = tree[R(C)].Cover = 0;
}
void query(int C)
{if(tree[C].Cover == 1){for(int i = tree[C].left; i <= tree[C].right; i++)used[i] = 1;return;}else if(tree[C].Cover == 0) return;if(tree[C].left == tree[C].right) return;down(C);query(L(C));query(R(C));
}
void solve(int l, int r, char lc, char rc, char op)
{int ll = 2 * l, rr = 2 * r;if(lc == '(') ll++;if(rc == ')') rr--;if(ll > rr){if(op == 'C' || op == 'I')tree[1].Cover = tree[1].Xor = 0;}else update(ll, rr, 1, op);
}
int main()
{char str[5], lc, rc;int l, r;make_tree(0, MAXN, 1);while(scanf("%s %c%d,%d%c", str, &lc, &l, &r, &rc) != EOF){solve(l, r, lc, rc, str[0]);}query(1);int flag = 0;int s = -1, e;for(int i = 0; i <= MAXN; i++){if(used[i]){if(s == -1) s = i;e = i;}else{if(s != -1){if(flag) printf(" ");flag = 1;lc = '[', rc = ')';if(s&1) lc = '(';if(!(e&1)) rc = ']';printf("%c%d,%d%c", lc, s>>1, (e+1)>>1, rc);s = -1;}}}if (!flag) printf("empty set");printf("\n");return 0;
}

这篇关于POJ 3225 Help with Intervals 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---