当前位置:编程学习 > C/C++ >>

POJ 3225

U:把区间[l,r]覆盖成1
I:把[-∞,l)(r,∞]覆盖成0
D:把区间[l,r]覆盖成0
C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换
S:[l,r]区间0/1互换
刚刚做的时候没有理解,后来才知道(2,3)区间也是可以的,不是一个点,而是区间,因为输入都是整数,所以,(2,3)扩大为(4,6),这样[5,5],就可以来取代(2,3)这种情况
继续写实验报告吧,3周没课了,天天睡懒觉,美好的早上总被我浪费掉,拖出去,树上吊起来吧,课程设计实验报告一大堆,还有一天就要上课了,加油!!
#include<iostream>
using namespace std;

const int MAX=65536<<1;//65535<<1;改成65600<<1就不对了

struct T
{
    int col;//表示颜色
    int cnt;//表示取反的次数
    int l,r,m;
}tree[MAX*3];

struct N
{
    int x,y;
}node[MAX];//这里改成node[MAX*2]就不对了
int size=0;

void Build_tree(int root,int l,int r)//创建树
{
    tree[root].l=l;
    tree[root].r=r;
    tree[root].m=(l+r)>>1;
    tree[root].cnt=0;
    if (l==r)
    {
        tree[root].col=0;
        return;
    }
    tree[root].col=-1;
    Build_tree(root<<1,l,tree[root].m);
    Build_tree(root<<1|1,tree[root].m+1,r);
};

void Updata(int root,int l,int r,int k)
{
    if(tree[root].l==l&&tree[root].r==r)
    {
        if(k==-1) tree[root].cnt++;
        else
        {
            tree[root].col=k;
            tree[root].cnt=0;
        }
        return ;
    }
    if(tree[root].col!=-1)
    {
        if (tree[root].cnt%2)
            tree[root].col=!tree[root].col;
        tree[root<<1].col=tree[root<<1|1].col=tree[root].col;
        tree[root<<1].cnt=tree[root<<1|1].cnt=tree[root].cnt=0;
        tree[root].col=-1;
    }
    if (tree[root].cnt%2)
    {
        tree[root<<1].cnt++;
        tree[root<<1|1].cnt++;
        tree[root].cnt=0;
    }
    if (r<=tree[root].m)//左子树
        Updata(root<<1,l,r,k);
    else if (l>tree[root].m)
        Updata(root<<1|1,l,r,k);
    else
    {
        Updata(root<<1,l,tree[root].m,k);
        Updata(root<<1|1,tree[root].m+1,r,k);
    }
}


void Query(int root)
{
    if (tree[root].col!=-1)
    {
        if(tree[root].cnt%2)
            tree[root].col=!tree[root].col;
        if (tree[root].col)
        {
            node[size].x=tree[root].l;
            node[size++].y=tree[root].r;
        }
        return ;
    }
    if(tree[root].cnt%2)
    {
        tree[root<<1].cnt++;
        tree[root<<1|1].cnt++;
        tree[root].cnt=0;
    }
    Query(root<<1);
    Query(root<<1|1);
}

int main()
{
    Build_tree(1,0,MAX);
    char ch[4],ci,cj;
    int a,b;
    while(scanf("%s %c%d,%d%c",ch,&ci,&a,&b,&cj)!=EOF)
    {
        a=2*a;
        b=2*b;
        if (ci=='(')
            a+=1;
        if (cj==')')
            b-=1;//这里[a,b]闭区间
        switch(ch[0])
        {
        case 'U'://[a,b]全部变1(并)
            if(a <= b)//过滤空集
                Updata(1,a,b,1);
            break;
        case 'I'://(交)
            if(a>0)
                Updata(1,0,a-1,0);
            Updata(1,b+1,MAX,0);
            break;
        case 'D'://(S-T)
            if(a <= b)//过滤空集
                Updata(1,a,b,0);
            break;
        case 'C':// (T-S)
            if(a>0)
                Updata(1,0,a-1,0);
            Updata(1,b+1,MAX,0);
            if(a<=b)//过滤空集
                Updata(1,a,b,-1);//取反
            break;
        case 'S':
            if(a<=b)//过滤空集
                Updata(1,a,b,-1);//取反
            break;
        }
    }
    Query(1);

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,