bzoj 3226 [Sdoi2008]校门外的区间

Description

　　受校门外的树这道经典问题的启发，A君根据基本的离散数学的知识，抽象出5种运算维护集合S(S初始为空)并最终输出S。现在，请你完成这道校门外的树之难度增强版——校门外的区间。

Input

　　输入共M行。
　　每行的格式为X T，用一个空格隔开，X表示运算的种类，T为一个区间(区间用(a,b), (a,b], [a,b), [a,b]表示)。

Output

　　共一行，即集合S，每个区间后面带一个空格。若S为空则输出”empty set”。

Sample Input

U [1,5]

D [3,3]

S [2,4]

C (1,5)

I (2,3]

Sample Output

(2,3)

HINT

对于 100% 的数据，0≤a≤b≤65535，1≤M≤70000

题解

这是非常明显的线段树。

把每一个区间里插上一个数表示开区间的情况。

U 区间涂1
I 两侧区间涂0
D 区间涂0
C 两侧涂0,中间取反
S 区间取反

但是昨天写线段树要写吐了。那就写写分块吧。

好像跑得飞快？

#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
int n=131070;
const int maxn = 65536*2-1+10000;
int m,num,mod,q,belong[maxn],block,l[maxn],r[maxn],a[maxn],mark[maxn],rev[maxn];
char s1[10],cl,cr;
int inline read()
{
    int x=0,f=1;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();}
    cr=ch;
    return x*f;
}
void build()
{
    block=200;
    num=n/block;if (n%block) num++;
    for (int i=1;i<=num;i++)
        l[i]=(i-1)*block+1,r[i]=i*block;
    for (int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    for (int i=1;i<=num;i++)
        mark[i]=-1;
}
void pushdown(int x)
{
    if (mark[x]!=-1)
    {
        for (int i=l[x];i<=r[x];i++)
            a[i]=mark[x];
        mark[x]=-1;
    }
    else if (rev[x])
    {
        for (int i=l[x];i<=r[x];i++)
            a[i]^=1;
        rev[x]=0;
    }
}
void cover(int L,int R,int x)
{
    int bl=belong[L],br=belong[R];
    pushdown(bl);pushdown(br);
    if (bl==br)
    {
        if (x!=-1)
            for (int i=L;i<=R;i++)
                a[i]=x;
        else
            for (int i=L;i<=R;i++)
                a[i]^=1;
        return;
    }
    if (x!=-1)
        for (int i=L;i<=r[bl];i++)
            a[i]=x;
    else
        for (int i=L;i<=r[bl];i++)
            a[i]^=1;
    if (x!=-1)
        for (int i=l[br];i<=R;i++)
            a[i]=x;
    else
        for (int i=l[br];i<=R;i++)
            a[i]^=1;
    if (x!=-1)
        for (int i=bl+1;i<br;i++)
            rev[i]=0,mark[i]=x;
    else
        for (int i=bl+1;i<br;i++)
            if (mark[i]==-1)
                rev[i]^=1;
            else
                mark[i]^=1;
}
int pro(int v,char c)
{
    if(c=='['||c==']') return (v<<1);
    else if(c=='(') return (v<<1)+1;
    else return (v<<1)-1;
}
main()
{
    memset(mark,-1,sizeof mark);
    int len=0,l,r,x,y;

    build();
    while(~scanf("%s",s1))
    {
        cl=getchar();
        while (cl!='[' && cl!='(') cl=getchar();
        x=read(),y=read();
        if(s1[0]=='U') cover(pro(x,cl),pro(y,cr),1);
        else if(s1[0]=='I')
        {
            if(x) cover(0,pro(x,cl)-1,0);
            if(y!=65535) cover(pro(y,cr)+1,65535<<1,0);
        }
        else if(s1[0]=='D') cover(pro(x,cl),pro(y,cr),0);
        else if(s1[0]=='C')
        {
            cover(pro(x,cl),pro(y,cr),-1);
            if(x) cover(0,pro(x,cl)-1,0);
            if(y!=65535) cover(pro(y,cr)+1,65535<<1,0);
        }
        else cover(pro(x,cl),pro(y,cr),-1);
    }
    for (int i=1;i<=num;i++)
        pushdown(i);
    int head=0,goal=0;
    for(int i=0;i<=n;++i)
    {
        if(((!i) && a[i]) || (a[i] && (!a[i-1]))) head=i;
        if((i==n && a[i]) || (a[i] && (!a[i+1])))
        {
            goal=1;
            if(head&1) putchar('(');
            else putchar('[');
            printf("%d,",head>>1);
            if(i&1) {printf("%d",i+1>>1); putchar(')');}
            else {printf("%d",i>>1); putchar(']');}
            putchar(' ');
        }
    }
    if(!goal) puts("empty set");
}

扔个生产器

#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <sstream>
#define random(a,b) ((a)+rand()%((b)-(a)+1))
using namespace std;

stringstream ss;

int main(int a1,char *a2[])
{
    int seed=time(0);
    if (a1)
    {
        ss.clear();
        ss<<a2[1];
        ss>>seed;
    }
    srand(seed);

    int n=random(5,10),m=random(1,3);

    for (int i=1;i<=m;i++)
    {
        int com=random(1,5);
        char ch;
        if (com==1)
            ch='U';
        if (com==2)
            ch='I';
        if (com==3)
            ch='D';
        if (com==4)
            ch='C';
        if (com==5)
            ch='S';
        int x=random(1,n-2),y=random(x+1,n);
        int l=random(0,1),r=random(0,1);
        printf("%c ",ch);
        if (l) printf("["); else printf("(");
        printf("%d,%d",x,y);
        if (r) printf("]\n"); else printf(")\n");
    }
}