P5568 [SDOI2008]校门外的区间 题解

· · 题解

原题link

题意

对于一个集合 S ,它可以和另外一个集合 T 做以下五种运算：

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

集合的基本运算操作定义如下：

$A∩B$：得到在 $A$ 集合中，且在 $B$ 集合中的元素。 $A−B$：得到在 $A$ 集合中，但不在 $B$ 集合中的元素。 $A⊕B$：$(A-B)∪(B-A)

初始区间 S 为空，输入 M 条计算指令，请你输出计算后的 S (用多个区间表示)。如果集合 S 最终为空，输出 empty set 。

思路

用一个线段树维护每个整数值是否存在，需要记录区间被什么覆盖（记为 tag , -1 表示无覆盖， 0/1 表示被覆盖）和区间是否反转(记为 rev , 1 表示区间被反转) 。 五种操作分别对应如下:

$I$ : $T$ 以外的区间覆盖为 $0$ 。 $D$ : $T$ 对应的区间覆盖为 $0$ 。 $C$ : $T$ 对应的区间反转， $T$ 以外的区间覆盖为 $0$ 。 $S$ : $T$ 对应的区间反转。 pushdown 的时候注意优先级，覆盖的优先级始终高于反转。 对于开区间，可以如下处理： 对于闭区间 $[a,b]$ 替换成 $[2a,2b]$ ，对于开区间 $(a,b)$ 替换成 $[2a+1,2b-1]$ ，如此可以按照纯闭区间处理。 答案输出：先查询每个叶子区间是否取 $1$ ，并记录成一个一维数组，最后扫描一遍整个数组输出答案。 # 代码讲解 ```cpp #include <bits/stdc++.h> using namespace std; const int N = 2*65535+10; const int M = 2*65535; int m,tag[N<<2],ans[N],rev[N<<2]; ``` $tag[u]=-1$ 未被覆盖 $tag[u]=0$ 被 $0$ 覆盖 $tag[u]=1$ 被 $1$ 覆盖 $rev[u]=0$ 未取反 $rev[u]=1$ 被取反 ```cpp inline int lc(int u) { return u<<1; } inline int rc(int u) { return u<<1|1; } ``` 线段树标配，分别表示左右儿子，使用位运算更快。 ```cpp inline void pushdown(int u) { if(tag[u] != -1) { tag[lc(u)] = tag[rc(u)] = tag[u]; rev[lc(u)] = rev[rc(u)] = 0; tag[u] = -1; } if(rev[u]) { if(tag[lc(u)] == -1) { rev[lc(u)] = 1 - rev[lc(u)]; } if(tag[lc(u)] != -1) { tag[lc(u)] = 1 - tag[lc(u)]; } if(tag[rc(u)] == -1) { rev[rc(u)] = 1 - rev[rc(u)]; } if(tag[rc(u)] != -1) { tag[rc(u)] = 1 - tag[rc(u)]; } rev[u] = 0; } } ``` 当节点 $u$ 被覆盖的时候，因为覆盖的优先级大于取反，所以左右儿子继承父亲的 $tag$ ，并设置成没有取反，且把 $tag_u$ 改回 $-1$ 。如果 $u$ 被取反了，则：如果一个儿子未被覆盖，则把其取反情况翻转一下；如果被覆盖了，就把覆盖的值翻转一下。最后把父亲调回未翻转状态。 ```cpp void modify_cover(int u,int l,int r,int x,int y,int k) { if(x <= l && y >= r) { tag[u] = k; rev[u] = 0; } else { int mid = (l+r)>>1; pushdown(u); if(x <= mid) modify_cover(lc(u),l,mid,x,y,k); if(y > mid) modify_cover(rc(u),mid+1,r,x,y,k); } } ``` 覆盖操作时， ```else``` 部分不讲，讲一下 ```if``` 。因为覆盖的优先级大于取反，所以此时把 $tag_u$ 改成应该赋的值（ $0$ 或 $1$ ），取反调成 $0$ 。 ```cpp void modify_opposite(int u,int l,int r,int x,int y) { if(x <= l && y >= r) { if(tag[u] != -1) tag[u] = 1 - tag[u]; if(tag[u] == -1) rev[u] = 1 - rev[u]; } else { int mid = (l+r)>>1; pushdown(u); if(x <= mid) modify_opposite(lc(u),l,mid,x,y); if(y > mid) modify_opposite(rc(u),mid+1,r,x,y); } } ``` 只讲 ```if``` 。如果该节点 $u$ 未被覆盖，则把它的取反值翻转一下；如果被覆盖了，就只翻转一下它的覆盖值。 ```cpp void query(int u,int l,int r) { if(l == r) { if(tag[u] != -1) { ans[l] = tag[u]; } if(tag[u] == -1) { ans[l] = rev[u]; } } else { int mid = (l+r)>>1; pushdown(u); query(lc(u),l,mid); query(rc(u),mid+1,r); } } ``` 这一步是遍历线段树的叶子节点。找到时，如果该节点未被覆盖，则取其取反值（未被取反则 $0$ ，被取反则 $1$ ）；如果被覆盖了，就直接取它的 $tag$ 值，因为此时它的 $rev$ 一定为 $0$ ，在 ```pushdown``` 操作的时候就搞定了。 ```cpp memset(tag,-1,sizeof(tag)); ``` 初始化 $tag$ 。 ```cpp for(int i = 1; i <= m; i++) { char cal,pre,suf,tmp; int lef,rig; cin>>cal>>pre>>lef>>tmp>>rig>>suf; lef <<= 1;rig <<= 1; if(pre == '(') lef += 1; if(suf == ')') rig -= 1; if(cal == 'U') { modify_cover(1,0,M,lef,rig,1); } if(cal == 'I') { if(lef-1 >= 0) modify_cover(1,0,M,1,lef-1,0); if(rig+1 <= M) modify_cover(1,0,M,rig+1,M,0); } if(cal == 'D') { modify_cover(1,0,M,lef,rig,0); } if(cal == 'C') { if(lef-1 >= 0) modify_cover(1,0,M,1,lef-1,0); if(rig+1 <= M) modify_cover(1,0,M,rig+1,M,0); modify_opposite(1,0,M,lef,rig); } if(cal == 'S') { modify_opposite(1,0,M,lef,rig); } } query(1,0,M); ``` 输入时改左右端点遵循“对于闭区间 $[a,b]$ 替换成 $[2a,2b]$ ，对于开区间 $(a,b)$ 替换成 $[2a+1,2b-1]$ ，如此可以按照纯闭区间处理”的原则。 ```cpp bool temp = 0, now = 0; for(int i = 0; i <= N; i++) { if(ans[i]) { temp = 1; if(now == 1) continue; if(!(i&1)) { printf("[%d,",i>>1); now = 1; } if(i&1) { printf("(%d,",i>>1); now = 1; } } if(!ans[i]) { int las = i-1; if(now == 0) continue; if(!(las&1)) { printf("%d] ",las>>1); } if(las&1) { printf("%d) ",(las+1)>>1); } now = 0; } } if(!temp) puts("empty set"); return 0; ``` 扫一遍，实现方法不唯一。 btw ，在我写 ```if(!ans[i])``` 中的 ```las&1``` 的时候，因为是取 $i$ 的开区间，所以 ```las``` 要 ```+1``` 。 $O(m \log n)