C++(g++ 7.5.0) 解法, 执行用时: 65ms, 内存消耗: 7384K, 提交时间: 2023-07-09 22:59:37

#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
const int M=1e7;
const int mod=998244353;
const int INF=0x3f3f3f3f;
struct Tree{
	int val,lazy1,lazy2;
	//lazy1 赋值 lazy2 翻转
}tree[(N+5)<<2];
string opt,inv;
void build(int x,int l,int r){
	tree[x].lazy1=-1;
	if(l==r)return;
	int mid=(l+r)/2;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
}
void pushup(int x){
	tree[x].val=(tree[x<<1].val+tree[x<<1|1].val);
}
void pushdown(int x,int l,int r){
	int mid=(l+r)/2;
	if(tree[x].lazy1!=-1){
		tree[x<<1].lazy1=tree[x].lazy1;
		tree[x<<1].lazy2=0;
		tree[x<<1|1].lazy1=tree[x].lazy1;
		tree[x<<1|1].lazy2=0;
		tree[x<<1].val=tree[x].lazy1*(mid-l+1);
		tree[x<<1|1].val=tree[x].lazy1*(r-mid);
		tree[x].lazy1=-1;
	}
	if(tree[x].lazy2){
		tree[x<<1].val=(mid-l+1)-tree[x<<1].val;
		tree[x<<1|1].val=(r-mid)-tree[x<<1|1].val;
		tree[x<<1].lazy2=!tree[x<<1].lazy2;
		tree[x<<1|1].lazy2=!tree[x<<1|1].lazy2;
		tree[x].lazy2=0;
	}
}
void update_cov(int x,int l,int r,int L,int R,int val){
	if(L>R)return;
	if(L<=l && r<=R){
		tree[x].val=val*(r-l+1);
		tree[x].lazy1=val;
		tree[x].lazy2=0;
		return;
	}
	pushdown(x,l,r);
	int mid=(l+r)/2;
	if(L<=mid)update_cov(x<<1,l,mid,L,R,val);
	if(R>mid)update_cov(x<<1|1,mid+1,r,L,R,val);
	pushup(x);
}
void update_flip(int x,int l,int r,int L,int R){
	if(L>R)return;
	if(L<=l && r<=R){
		tree[x].val=r-l+1-tree[x].val;
		tree[x].lazy2=!tree[x].lazy2;
		return;
	}
	pushdown(x,l,r);
	int mid=(l+r)/2;
	if(L<=mid)update_flip(x<<1,l,mid,L,R);
	if(R>mid)update_flip(x<<1|1,mid+1,r,L,R);
	pushup(x);
}
int ans[N+5];
void query(int x,int l,int r){
	if(l==r){
		ans[l]=tree[x].val;
		return;
	}
	pushdown(x,l,r);
	int mid=(l+r)/2;
	query(x<<1,l,mid);
	query(x<<1|1,mid+1,r);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	build(1,1,N);
	while(cin>>opt){
		cin>>inv;
		int l=0,r=0,len=(int)inv.size();
		for(int i=1;i<len;i++){
			if(inv[i]==','){
				for(int j=i+1;j<len-1;j++)
					r=r*10+(inv[j]-'0');
				break;
			}
			else l=l*10+(inv[i]-'0');
		}
		if(inv[0]=='(')l=l*2+2;
		else l=l*2+1;
		if(inv[len-1]==')')r=r*2;
		else r=r*2+1;
		if(l>r)continue;
		if(opt[0]=='U')update_cov(1,1,N,l,r,1);
		else if(opt[0]=='I'){
			update_cov(1,1,N,1,l-1,0);
			update_cov(1,1,N,r+1,N,0);
		}
		else if(opt[0]=='D')update_cov(1,1,N,l,r,0);
		else if(opt[0]=='S')update_flip(1,1,N,l,r);
		else{
			update_flip(1,1,N,1,N);
			update_cov(1,1,N,1,l-1,0);
			update_cov(1,1,N,r+1,N,0);
		}
	}
	query(1,1,N);
	if(tree[1].val==0){
		cout<<"empty set";
		return 0;
	}
	int f=0;
	for(int i=1;i<=N;i++){
		if(ans[i] && f==0){
			f=1;
			if(i&1)cout<<'[';
			else cout<<'(';
			cout<<(i-1)/2<<',';
		}
		if(ans[i+1]==0 && f){
			f=0;
			cout<<i/2;
			if(i&1)cout<<']';
			else cout<<')';
			cout<<" ";
		}
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 72ms, 内存消耗: 5732K, 提交时间: 2019-03-16 11:50:10

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define ll long long
#define inf 1000000000
#define n (65536*2+1)
using namespace std;
int read()
{
    int x=0,f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='(')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	if(ch==')')f=1;
    return x*2-f;
}
char ch[5];
struct seg{int l,r,val,tag,rev;}t[4*n];
void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;t[k].tag=-1;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}
void pushdown(int k)
{
	int tag=t[k].tag,rev=t[k].rev;
	t[k].tag=-1;t[k].rev=0;
	if(t[k].l==t[k].r)
	{
		if(tag!=-1)
			t[k].val=tag;
		t[k].val^=rev;;
		return;
	}
	if(tag!=-1)
	{
		t[k<<1].tag=t[k<<1|1].tag=tag;
		t[k<<1].rev=t[k<<1|1].rev=0;
	}
	t[k<<1].rev^=rev;t[k<<1|1].rev^=rev;
}
int query(int k,int x)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r;
	if(l==r)return t[k].val;
	int mid=(l+r)>>1;
	if(x<=mid)return query(k<<1,x);
	else return query(k<<1|1,x);
}
void modify(int k,int x,int y,int val)
{
	if(y<x)return;
	pushdown(k);
	int l=t[k].l,r=t[k].r;
	if(l==x&&y==r)
	{
		if(val==-1)t[k].rev^=1;
		else t[k].tag=val;
		return;
	}
	int mid=(l+r)>>1;
	if(y<=mid)modify(k<<1,x,y,val);
	else if(x>mid)modify(k<<1|1,x,y,val);
	else 
	{
		modify(k<<1,x,mid,val);
		modify(k<<1|1,mid+1,y,val);
	}
}
void rever(int k,int x,int y)
{
    modify(k,x,y,-1);
}
int main()
{
	build(1,1,n);
	while(scanf("%s",ch)!=EOF)
	{
		int a=read(),b=read();
		a+=2;b+=2;
		switch(ch[0])
		{
		case 'U':modify(1,a,b,1);break;
		case 'I':modify(1,1,a-1,0);modify(1,b+1,n,0);break;
		case 'D':modify(1,a,b,0);break;
		case 'C':modify(1,1,a-1,0);modify(1,b+1,n,0);rever(1,a,b);break;
		case 'S':rever(1,a,b);break;
		}
	}
	int start=-1,last=-1,flag=0;
	for(int i=1;i<=n;i++)
		if(query(1,i))
		{
			if(start==-1)start=i;
			last=i;
		}
		else 
		{
			if(start!=-1)
			{
				if(flag)printf(" ");
				else flag=1;
				if(start&1)printf("(");
				else printf("[");
				printf("%d",start/2-1);
				printf(",");
				printf("%d",(last+1)/2-1);
				if(last&1)printf(")");
				else printf("]");
			}
			last=start=-1;
		}
	if(!flag)puts("empty set");
	return 0;
}