这题目完全就是一个标记下传思想，通过这道题目，自己也对这思想了解的更为透彻了，异或标记和覆盖标记，-1表示区间可能在子区间覆盖，0表示没有，1表示有，异或标记覆盖区间要下传，通过fxor下传。然后开区间，闭区间就是用乘以2，因为开区间要-1或则+1表示，奇数表示开，偶数表示闭，看了解题报告，还写了那么久
#include<cstdio>
int c[1600000],x[1600000];
int hash[140000];
const int N=140000;
void fxor(int i)//异或标记下传
{
if(c[i]!=-1)
{
c[i]^=1;
}
else
x[i]^=1;
}
void down(int i)
{
if(c[i]!=-1)
{
c[2*i+1]=c[2*i]=c[i];
c[i]=-1;
x[2*i+1]=x[2*i]=0;
}
if(x[i])
{
fxor(2*i);
fxor(2*i+1);
x[i]=0;
}
}
void ud(char t,int i,int l,int r,int L,int R)
{
if(l==L&&r==R)
{
if(t=='U')
{
c[i]=1;
x[i]=0;
}
if(t=='D')
{
c[i]=0;
x[i]=0;
}
else
if(t=='C'||t=='S')
fxor(i);
return;
}
down(i);
int mid=(L+R)>>1;
if(mid>=r)
{
ud(t,2*i,l,r,L,mid);
if(t=='I'||t=='C')
x[2*i+1]=c[2*i+1]=0;
}
else
if(mid<l)
{
ud(t,2*i+1,l,r,mid+1,R);
if(t=='I'||t=='C')
x[2*i]=c[2*i]=0;
}
else
{
ud(t,2*i,l,mid,L,mid);
ud(t,2*i+1,mid+1,r,mid+1,R);
}
}
void dfs(int i,int l,int r)
{
if(c[i]==0)
return;
if(c[i]==1)
{
for(int i=l;i<=r;i++)
hash[i]=1;
return;
}
if(l==r)
return;
down(i);
int m=(l+r)>>1;
dfs(2*i,l,m);
dfs(2*i+1,m+1,r);
return;
}
int main()
{
char t,le,re;
int a,b;
x[1]=0;
c[1]=0;
while ( ~scanf("%c %c%d,%d%c\n",&t , &le , &a , &b , &re) ) {//发现以前自己读入数据方式太土了.
a <<= 1 , b <<= 1;
if (le == '(') a ++;
if (re == ')') b --;
if (a > b) {
if (t == 'C' || t == 'I') {
c[1] = x[1] = 0;
}
} else ud(t ,1, a , b , 0 , N);
}
dfs(1,0,N);
int s=-1,flag=0,e;
for(int i=0;i<N;i++)
{
if(hash[i])
{
if(s==-1)s=i;
e=i;
}
else
{
if(s!=-1)
{
if(flag)
printf(" ");
printf("%c%d,%d%c",s&1?'(':'[' , s>>1 , (e+1)>>1 , e&1?')':']');
flag=1;
s=-1;
}
}
}
if (!flag) printf("empty set");
puts("");
return 0;
}
，搓死了。。