P5568 [SDOI2008] 校门外的区间 题解
Diamiko
·
·
题解
珂朵莉树
还以为会T飞，没想到喜提最优解第四
仔细分析一下题目，我们就不难想出一种题目的转化，那就是把区间操作看作数轴上无数的01序列的操作。
我们把要维护的集合S看作一个数轴，如果数轴上的某个点数值为0，那么代表该点表示的位置不属于S；如果为1，则属于S.
另外仍需考虑的一点，是怎么处理区间端点的开闭。
这里我们采用一种转化方式，把(l,r)转化为(l+0.5,r-0.5)，这样我们就取不到l和r了。但是我们珂朵莉树维护的是整数的端点值，考虑把端点值乘2。
我们会发现
[l,r]->[2l,2r]
(l,r)->(2l+1,2r-1)
端点值具有了唯一整数性，对于前开后闭或前闭后开区间也同理。
这个题目是有坑的，输入的区间可能存在\emptyset，需要额外注意。
1.建立集合
开始的时候 S=\emptyset，我们插入一个极小值到极大值的0点。
s.insert(Node(-65535*2,65535<<1,0));
（注意，以下函数代码均暂不考虑T为空集的情况）
2.S=S∪T
取并集
显然无论S的情况如何，对于T的范围内所有数我们都使其属于S，直接推平为1即可。
```cpp
inline void U(int l,int r)
{
assign(l,r,1);
}
```
## 3.$S=S∩T
取交集
在T=\emptyset时，S为任何集合交集都为\emptyset.
在T≠\emptyset时，交集为两集合重合的部分。那么我们把集合T左边的都变成0，右边的也变成0，因为它们不是我们需要的答案。现在我们已经剔除了不属于T的部分，我们还要剔除属于T但不属于S的部分。那么我们遍历T集合，原本为1的元素属于S，我们取；而原本为0的不属于S，我们舍弃，答案就出来了。
但是仔细想想，T集合内原本1的我们还是让它1，原本0的我们也让它0，所以我们相当于没有改变，也不用遍历了。
inline void I(int l,int r)
{
assign(-65535*2,l-1,0);
assign(r+1,65535<<1,0);
}
4.S=S-T
取S与T的差集
显然T为空集时我们可以直接跳过，以为任何集合与空集的集合都为原集合。
而T不为空集时，我们就是在S中把T的部分去掉，可以直接推平T。
inline void D(int l,int r)
{
assign(l,r,0);
}
5.S=T-S
取T与S的差集
显然T为空集时，T与任何S的差集都为空集。
$T$内的部分只要原本为$1$，就是属于$S$的，我们令其为$0$，因为它不属于我们的答案；原本为$0$，就是原本也不属于$S$，我们令其为$1$，因为它属于$T$和$S$的差集。
```cpp
inline void C(int l,int r)
{
for(SIT itr=split(r+1),itl=split(l);itl!=itr;itl++)
{
itl->v^=1;
}
assign(-6553*2,l-1,0);
assign(r+1,65535<<1,0);
}
```
## 6.$S=S⊕T
取S和T的对称差
显然T为空集时，我们可以直接跳过这一步，因为任何集合与空集的对称差为原集合。
那么在$T$之外的所有属于$S$的元素我们都需要，在$T$之内我们只需要属于$T$的元素。
那么在$T$之内，原本为$0$我们令其为$1$，原本为$1$我们令其为$0$；在$T$之外我们不变。
```cpp
inline void S(int l,int r)
{
for(SIT itr=split(r+1),itl=split(l);itl!=itr;itl++)
{
itl->v^=1;
}
}
```
## 7.细节处理
### ① 空集的判别
利用高中必修一学习的集合知识我们知道，不会有一个数同时大于$x$又小于$x$，推广一下，空集的情况只有一下几种：
$$(x,x)$$
$$(x,x]$$
$$[x,x)$$
以及$l>r$的情况。
### ② 集合的合并
因为珂朵莉树我们要多次进行$split$操作，所以有些区间会分裂开来，而输出时我们要把可以合并的区间合并起来。
比如我们使$S=[1,5]$与$T=[2,3]$取交集，输出的答案会是$[1,2)\space[2,3]\space(3,5]$，这显然不合常理，我们要将其合并。
相邻的节点，如果同为$1$或同为$0$，我们可以合并为一个节点，详见代码。
```cpp
inline void Merge()
{
auto it1=s.begin(),it2=it1;
it2++;//使it2为it1后面一个
while(it2!=s.end()&&s.size())
{
if(it1->v==it2->v)
{
int l=it1->l,r=it2->r,v=it1->v;
it2++;
it2=s.erase(it1,it2);
//erase返回的是删除的元素后面那一个的迭代器
//并且删除的是[it1,it2)，所以要提前把it2++
it1=s.insert(Node(l,r,v)).first;
//insert返回的pair的第一关键字是插入元素的迭代器
}
else
{
it1++;
it2++;
}
}
}
```
### ③ 输入及输出的处理
输入就不赘述了，一个简单的字符串处理，提取数字的原理你会写快读自然就明白。一个细节是我们在处理的时候同时把这个区间是否合法也一块处理了。
输出的时候，如果这个区间的端点是一个奇数，说明是开端点；是偶数，说明这个端点是闭端点，输出的时候端点值要除以二。
## 8.完整代码
```cpp
#include<bits/stdc++.h>
#define SIT set<Node>::iterator
using namespace std;
struct Node
{
int l,r;
mutable bool v;
Node(int L,int R=-1,int V=0):l(L),r(R),v(V){}
bool operator <(const Node &x)const
{
return l<x.l;
}
};
set<Node>s;
char opt[2],range[15];
int l,r;
bool init(int &l,int &r)//注意引用
{
char flagl,flagr;
flagl=range[0],flagr=range[strlen(range)-1];
int num=0;
for(int i=1;i<(int)strlen(range)-1;i++)
{
if(range[i]==',')
{
l=num;
num=0;
continue;
}
num=num*10+range[i]-'0';
}
r=num;
if(l>r)return false;
if(l==r&&((flagl=='('&&flagr==']')||(flagl=='['&&flagr==')')||(flagl=='('&&flagr==')')))return false;
if(flagl=='(')l=l*2+1;
else l<<=1;
if(flagr==')')r=r*2-1;
else r<<=1;
return true;
}
inline SIT split(int pos)
{
SIT it=s.lower_bound(Node(pos));
if(it!=s.end()&&it->l==pos)return it;
it--;
int l=it->l,r=it->r,v=it->v;
s.erase(it);
s.insert(Node(l,pos-1,v));
return s.insert(Node(pos,r,v)).first;
}
inline void assign(int l,int r,bool v)
{
SIT itr=split(r+1),itl=split(l);
s.erase(itl,itr);
s.insert(Node(l,r,v));
}
inline void U(int l,int r)
{
assign(l,r,1);
}
inline void I(int l,int r)
{
assign(-65535*2,l-1,0);
assign(r+1,65535<<1,0);
}
inline void D(int l,int r)
{
assign(l,r,0);
}
inline void C(int l,int r)
{
for(SIT itr=split(r+1),itl=split(l);itl!=itr;itl++)
{
itl->v^=1;
}
assign(-6553*2,l-1,0);
assign(r+1,65535<<1,0);
}
inline void S(int l,int r)
{
for(SIT itr=split(r+1),itl=split(l);itl!=itr;itl++)
{
itl->v^=1;
}
}
inline void Merge()
{
auto it1=s.begin(),it2=it1;
it2++;
while(it2!=s.end()&&s.size())
{
if(it1->v==it2->v)
{
int l=it1->l,r=it2->r,v=it1->v;
it2++;
it2=s.erase(it1,it2);
it1=s.insert(Node(l,r,v)).first;
}
else
{
it1++;
it2++;
}
}
}
inline void contain()
{
bool flag=0;
for(Node x:s)
{
if(x.v)
{
flag=1;
printf("%c%d,%d%c ",(x.l)&1?'(':'[',x.l>>1,x.r+1>>1,(x.r&1)?')':']');
}
}
if(!flag)puts("empty set");
}
int main()
{
s.insert(Node(-65535*2,65535<<1,0));
while(~scanf("%s %s",opt,range))//多组输入
{
bool empty=!init(l,r);
if(!strcmp(opt,"U"))
{
if(empty) continue;
U(l,r);
}
else if(!strcmp(opt,"I"))
{
if(empty)
{
s.clear();
s.insert(Node(-65535*2,65535<<1,0));
continue;
}
I(l,r);
}
else if(!strcmp(opt,"D"))
{
if(empty) continue;
D(l,r);
}
else if(!strcmp(opt,"C"))
{
if(empty)
{
s.clear();
s.insert(Node(-65535*2,65535<<1,0));
continue;
}
C(l,r);
}
else
{
if(empty) continue;
S(l,r);
}
}
Merge();
contain();
return 0;
}
```