「BZOJ3226」[Sdoi2008]校门外的区间

题目

首先是开闭区间的处理，我们把(1.5)这种数加进来，用([1.5,6])来表示((2,6])

根据离散数学的基本知识，尝试把五个操作转化成人话

1. 把([x,y])变成(1)

2. 把([0,x-1])和([y+1,inf])变成(0)

3. 把([x,y])变成(0)

4. 把([x,y])取反，之后来一个二操作

5. 把([x,y])取反

于是线段树维护一下区间覆盖就好了

记得覆盖标记和取反标记只能同时存在一个就好了

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define LL long long
#define re register
#define maxn 150005
inline 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 opt[3];
int rev[maxn<<2],tag[maxn<<2];
int d[maxn<<2],l[maxn<<2],r[maxn<<2];
void build(int x,int y,int i) {
    l[i]=x,r[i]=y;tag[i]=-1;
    if(x==y) return;
    int mid=x+y>>1;
    build(x,mid,i<<1),build(mid+1,y,i<<1|1);
}
inline void pushdown(int i) {
    if(tag[i]!=-1) {
        rev[i<<1]=rev[i<<1|1]=0;
        tag[i<<1]=tag[i<<1|1]=tag[i];
        d[i<<1]=d[i<<1|1]=tag[i];
        tag[i]=-1;
    }
    if(rev[i]) {
        d[i<<1|1]^=1,d[i<<1]^=1;
        if(tag[i<<1]!=-1) tag[i<<1]^=1;
            else rev[i<<1]^=1;
        if(tag[i<<1|1]!=-1) tag[i<<1|1]^=1;
            else rev[i<<1|1]^=1;
        rev[i]=0;
    }
}
void change(int x,int y,int val,int i) {
    if(x<=l[i]&&y>=r[i]) {
        d[i]=val;tag[i]=val;
        if(rev[i]) rev[i]=0;
        return;
    }
    pushdown(i);
    int mid=l[i]+r[i]>>1;
    if(x<=mid) change(x,y,val,i<<1);
    if(y>=mid+1) change(x,y,val,i<<1|1);
}
void solve(int x,int y,int i) {
    if(x<=l[i]&&y>=r[i]) {
        d[i]^=1;
        if(tag[i]!=-1) tag[i]^=1;
            else rev[i]^=1;
        return;
    }
    pushdown(i);
    int mid=l[i]+r[i]>>1;
    if(x<=mid) solve(x,y,i<<1);
    if(y>=mid+1) solve(x,y,i<<1|1);
}
int query(int pos,int i) {
    if(l[i]==r[i]) return d[i];
    pushdown(i);
    int mid=l[i]+r[i]>>1;
    if(pos<=mid) return query(pos,i<<1);
    return query(pos,i<<1|1);
}
int main() {
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    build(1,150000,1);
    while(scanf("%s",opt)!=EOF) {
        int x=read()+2,y=read()+2;
        if(opt[0]=='U') change(x,y,1,1);
        if(opt[0]=='I') change(1,x-1,0,1),change(y+1,150000,0,1);
        if(opt[0]=='D') change(x,y,0,1);
        if(opt[0]=='C') change(1,x-1,0,1),change(y+1,150000,0,1),solve(x,y,1);
        if(opt[0]=='S') solve(x,y,1);
        //if(opt[0]=='I') break;
    }
    int st=-1,lst=-1,flag=0;
    for(re int i=1;i<=150000;i++) {
        if(query(i,1))  {
            if(st==-1) st=i;
            lst=i;
        }
        else {
            if(st!=-1) {
                if(flag) putchar(' ');
                    else flag=1;
                if(st&1) putchar('(');
                    else putchar('[');
                printf("%d",st/2-1);
                putchar(',');
                printf("%d",(lst+1)/2-1);
                if(lst&1) putchar(')');
                    else putchar(']');
            }
            lst=st=-1;
        }
    }
    if(!flag) puts("empty set");
    return 0;
}