自动搬运

查看原文

来自洛谷，原作者为

	Diamiko 此人已退役，不用留言了，看不见

搬运于2025-08-24 22:12:04，当前版本为作者最后更新于2021-11-02 19:49:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

珂朵莉树

还以为会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$即可。

$T$为空集我们就可以直接跳过这一步了。

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$不为空集时，我们要取只属于$T$而不属于$S$的部分，显然对于$T$左边和右边的区间我们都可以直接推平。

$T$内的部分只要原本为$1$，就是属于$S$的，我们令其为$0$，因为它不属于我们的答案；原本为$0$，就是原本也不属于$S$，我们令其为$1$，因为它属于$T$和$S$的差集。

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$不为空集时，我们要取只属于$T$或$S$且不属于另一者的元素。

那么在$T$之外的所有属于$S$的元素我们都需要，在$T$之内我们只需要属于$T$的元素。

那么在$T$之内，原本为$0$我们令其为$1$，原本为$1$我们令其为$0$；在$T$之外我们不变。

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$，我们可以合并为一个节点，详见代码。

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.完整代码

#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;
}