超级恶心的一道题目。。。
查错查了一个小时。。。。
1,要用C++,用G++会wa。
2，注意检查边界。
3，注意标记的下放方式。
#include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define maxn 200000 #define mem(a,b) (memset(a),b,sizeof(a)) #define lmin 0 #define rmax n #define lson l,(l+r)/2,rt<<1 #define rson (l+r)/2+1,r,rt<<1|1 #define root lmin,rmax,1 #define now l,r,rt #define int_now int l,int r,int rt #define INF 99999999 #define LL __int64 #define mod 10007 #define eps 1e-6 #define zero(x) (fabs(x) r||rr =r) { val[rt]=x; rev[rt]=0; return; } push_down(now); updata(ll,rr,x,lson); updata(ll,rr,x,rson); } void fan(int ll,int rr,int_now) { if(ll>r||rr =r) { if(val[rt]!=-1)val[rt]^=1; else rev[rt]^=1; return; } push_down(now); fan(ll,rr,lson); fan(ll,rr,rson); } void query(int_now) { if(l==r) { if(val[rt]==1)ans[l]=1; return; } push_down(now); query(lson); query(rson); } int main() { int n=65537*2; char ch[100]; char le,ri; int l,r; while(scanf("%s%*c%c%d,%d%c%*c",ch,&le,&l,&r,&ri)!=EOF) { if(ch[0]=='e')break; l=l*2; r=r*2; if(le=='(')l=l+1; if(ri==')')r=r-1; if(ch[0]=='U') { updata(l,r,1,root); } if(ch[0]=='I') { if(l-1>=0)updata(0,l-1,0,root); updata(r+1,n,0,root); } if(ch[0]=='D') { updata(l,r,0,root); } if(ch[0]=='C') { if(l-1>=0)updata(0,l-1,0,root); updata(r+1,n,0,root); fan(l,r,root); } if(ch[0]=='S') { fan(l,r,root); } } query(root); int flag=0; l=r=-1; for(int i=0;i<=n;i++) { if(ans[i]) { if(l==-1) { l=i; if(flag)printf(" "); if(l%2)printf("(%d",l/2); else printf("%[%d",l/2); flag++; } } else { if(l!=-1) { r=i-1; if(r%2)printf(",%d)",r/2+1); else printf(",%d]",r/2); flag++; l=r=-1; } } } if(flag==0) { printf("empty set"); } puts(""); return 0; }