这题很裸,只要维护单点1,0就行了、、
不同运算表示 :
u : 全1
d : 全0
i : 以外全0
c : 取反,以外取0
s :取反
线段树标记记得下传时当前点标记清零 ,然后就没了
犯的错误: 1、 标记忘清零、
2、 小数时的括号
3、特判!!!0!!! 0!!!!0 !!!!
码:
#include<iostream> #include<cstdio> using namespace std; #define zuo l,mid,o<<1 #define you mid+1,r,o<<1|1 #define N 131075 int quan1[N<<2],quan0[N<<2],rev[N<<2],a,b,op,la,lb,i,lin; char ch,zkh,ykh,douhao; bool yes,lianxu,jieshu,yici=1; void down(int o) { if(quan0[o]==1) { quan0[o<<1]=1; quan1[o<<1]=0; rev[o<<1]=0; quan0[o<<1|1]=1; quan1[o<<1|1]=0; rev[o<<1|1]=0; } if(quan1[o]==1) { quan0[o<<1]=0; quan1[o<<1]=1; rev[o<<1]=0; quan0[o<<1|1]=0; quan1[o<<1|1]=1; rev[o<<1|1]=0; } if(rev[o]==1) { rev[o<<1]^=1; rev[o<<1|1]^=1; } rev[o]=0; quan0[o]=0; quan1[o]=0; } void gai(int l,int r,int o) { if(l!=r)down(o); if(a<=l&&r<=b) { if(op==1) { rev[o]=0; quan1[o]=1; quan0[o]=0; } if(op==2) { rev[o]=0; quan1[o]=0; quan0[o]=1; } if(op==3) { rev[o]^=1; } if(l!=r)down(o); return; } int mid=(l+r)>>1; if(a<=mid)gai(zuo); if(b>=mid+1)gai(you); } void zhao(int l,int r,int o) {if(l!=r)down(o); if(l==r) { lin=0; if(quan0[o])lin=0; if(quan1[o])lin=1; if(rev[o])lin^=1; return ; } int mid=(l+r)>>1; if(a<=mid)zhao(zuo); if(a>=mid+1)zhao(you); } int main() { while(1) { if(scanf("%c",&ch)==EOF)break; while((ch==' '||ch=='\n'||ch=='\r'))if(scanf("%c",&ch)==EOF){jieshu=1;break;} if(jieshu)break; scanf("%c",&zkh);scanf("%c",&zkh); scanf("%d",&a); scanf("%c",&douhao); scanf("%d",&b); scanf("%c",&ykh); a*=2; b*=2; if(zkh=='(')a++; if(ykh==')')b--; if(ch=='U') { op=1; gai(1,N,1); } if(ch=='I') { op=2; la=a; lb=b; a=1; b=la-1; if(b>=a)gai(1,N,1); a=lb+1; b=N; if(b>=a)gai(1,N,1); } if(ch=='D') { op=2; if(b>=a)gai(1,N,1); } if(ch=='C') { op=3; gai(1,N,1); op=2; la=a; lb=b; a=1; b=la-1; if(b>=a)gai(1,N,1); a=lb+1; b=N; if(b>=a)gai(1,N,1); } if(ch=='S') { op=3; if(b>=a)gai(1,N,1); } } for(i=0;i<=131071;i++) { a=i;lin=0; zhao(1,N,1); if(lin==1) { yes=1; if(lianxu==1) { continue; } if(lianxu==0) { lianxu=1; if(a%2==1) { if(!yici)printf(" (%d,",a/2); else {yici=0;printf("(%d,",a/2); } } else if(!yici)printf(" [%d,",a/2); else {yici=0;printf("[%d,",a/2); } } }else { if(lianxu==0) { continue; } if(lianxu==1) { lianxu=0; if(a%2==1) { printf("%d]",a/2); } else printf("%d)",a/2); } } } if(yes==0) { cout<<"empty set"; } }