POJ 3225 Help with Intervals BZOJ 3226 校门外的区间 解题报告


从时间看，POJ首先收录了此题，BZOJ（lydsy）于次年收录此题。POJ的题目背景清晰自然，输入格式描述清晰（提到了EOF），题目来源明确，PKU Local 2007 (POJ Monthly--2007.04.28)；而BZOJ的题目背景显得生搬硬套，对几种运算的描述也甚为含糊，尤其是将“∈”写成“Δ，对输入格式的描述亦不甚全面，来源不够明确，虽标明Sdoi2008，但语言严谨性与省队选拔赛不符。因此，如果此题存在版权争议，侵权方应该为BZOJ。
POJ：
Help with Intervals
Time Limit: 6000MS
Memory Limit: 131072K
Case Time Limit: 2000MS
Description
LogLoader, Inc. is a company specialized in providing products for analyzing logs. While Ikki is working on graduation design, he is also engaged in an internship at LogLoader. Among his tasks, one is to write a module for manipulating time intervals, which have confused him a lot. Now he badly needs your help.
In discrete mathematics, you have studied several basic set operations, namely union, intersection, relative complementation and symmetric difference, which naturally apply to the specialization of sets as intervals.. For your quick reference they are summarized in the table below:
Operation
Notation
Definition
Union
A∪B
{x: x∈A or x∈B}
Intersection
A∩B
{x: x∈A and x∈B}
Relative complementation
A−B
{x: x∈A but x∉B}
Symmetric difference
A⊕B
(A−B)∪(B−A)
Ikki has abstracted the interval operations emerging from his job as a tiny programming language. He wants you to implement an interpreter for him. The language maintains a set S, which starts out empty and is modified as specified by the following commands:
Command
Semantics
U T
S ← S∪T
I T
S ← S∩T
D T
S ← S−T
C T
S ← T−S
S T
S ← S⊕T
Input
The input contains exactly one test case, which consists of between 0 and 65,535 (inclusive) commands of the language. Each command occupies a single line and appears like
X T
where X is one of ‘U’, ‘I’, ‘D’, ‘C’ and ‘S’ and T is an interval in one of the forms (a,b), (a,b], [a,b) and [a,b] (a, b ∈ Z, 0 ≤ a ≤ b ≤ 65,535), which take their usual meanings. The commands are executed in the order they appear in the input.
End of file (EOF) indicates the end of input.
Output
Output the set S as it is after the last command is executed as the union of a minimal collection of disjoint intervals. The intervals should be printed on one line separated by single spaces and appear in increasing order of their endpoints. If S is empty, just print “empty set” and nothing else.
Sample Input
U [1,5]
D [3,3]
S [2,4]
C (1,5)
I (2,3]
Sample Output
(2,3)

BZOJ：

3226: [Sdoi2008]校门外的区间

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

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

　　5种运算如下：
U T
S∪T
I T
S∩T
D T
S－T
C T
T－S
S T
S⊕T
　　基本集合运算如下：
A∪B
{x : xÎA or xÎB}
A∩B
{x : xÎA and xÎB}
A－B
{x : xÎA and xÏB}
A⊕B
(A－B)∪(B－A)

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

解析

我们首先可以想到应该将区间离散化，然后用线段树解决此题。为了区分开区间和闭区间，我们将区间长度乘3，这样区间(a,b)对应[3a+1,3b-1]，区间[a,b]对应[3a,3b]。[0,b)的补集是[b,65535]，对应的乘3后的区间为[0,3b-1)和[3b,196605]，可以看出，将区间长度乘3巧妙地解决了开区间的补集是闭区间的问题。
接着我们思考五种集合操作的实现。
U操作：最容易实现，将区间T设为1即可。
I操作：也比较容易，将区间T的补集设为0即可。
D操作：稍微分析后便会发现，将区间T设为0即可。
C操作：首先，区间T的补集应该被设为0；而对应区间T内的部分，假如某个点属于S集合，显然这个点应该被设为0，而假如某个点不属于S集合，这个点应该被设为1；这意味着需要将区间T取反。
S操作：S操作的结果应该是D、C操作的并，也就是将区间T取反。
为了实现这五种集合操作，我们需要实现两种线段树操作——区间修改和区间取反。维护两个懒标记，flag和but，flag表示子区间将被修改成某个值，flag=-1则失效，but表示区间是否被取反。pushdown函数的实现：
public: void pushdown(int now)
{
    if (tree[now].but)
    {
        tree[now << 1].but ^= 1;
        tree[now << 1 | 1].but ^= 1;
        if (tree[now << 1].flag != -1)tree[now << 1].flag ^= 1;
        if (tree[now << 1 | 1].flag != -1)tree[now << 1 | 1].flag ^= 1;
        tree[now].but = false;
    }
    if (tree[now].flag == -1) return;
    tree[now << 1].flag = tree[now << 1 | 1].flag = tree[now].flag;
}
可以看到，我们首先处理了but标记，这和区间加与区间覆盖的关系有些像，在下文中，你将看到它们之间的转换。
区间赋值和区间取反的写法类似，用最朴素的区间修改的写法即可。
最后还剩下输入和输出。
输入时需要注意区间的数字和括号间没有空格，为了解决这一点，可以令读入优化返回ch。
输出时可以从0开始遍历一遍线段树，比较容易，具体实现见参考程序。

参考程序

#include <iostream>
#include <stdio.h>

namespace solution
{
    using namespace std;

    const int MAXSIZE = 196609;

    inline char read(int &x)
    {
        x = 0; char ch = getchar(); bool f = 0;
        while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }
        while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
        if (f)x = -x;
        return ch;
    }

    inline void read(char &x)
    {
        x = getchar();
        while (x <= ' ')x = getchar();
    }

    class program
    {
    public: struct
    {
        //-1:different 0:all zero 1:all one
        int l, r, flag;
        //表示一个区间的子区间是否需要取反
        bool but;
    }tree[1048576];

    public: void build(int l, int r, int now = 1)
    {
        tree[now].l = l; tree[now].r = r;
        tree[now].flag = 0; tree[now].but = 0;
        if (l == r)return;
        int mid = l + r >> 1;
        build(l, mid, now << 1);
        build(mid + 1, r, now << 1 | 1);
    }

    public: void pushdown(int now)
    {
        if (tree[now].but)
        {
            tree[now << 1].but ^= 1;
            tree[now << 1 | 1].but ^= 1;
            if (tree[now << 1].flag != -1)tree[now << 1].flag ^= 1;
            if (tree[now << 1 | 1].flag != -1)tree[now << 1 | 1].flag ^= 1;
            tree[now].but = false;
        }
        if (tree[now].flag == -1) return;
        tree[now << 1].flag = tree[now << 1 | 1].flag = tree[now].flag;
    }

    public: bool query(int p, int now = 1)
    {
        if (tree[now].flag != -1)
        {
            return tree[now].flag;
        }
        int mid = tree[now].l + tree[now].r >> 1;
        pushdown(now);
        if (p <= mid)return query(p, now << 1);
        else return query(p, now << 1 | 1);
    }

    public: void updata(int l, int r, int x, int now = 1)
    {
        if (r<l)return;
        if (tree[now].l == l&&tree[now].r == r)
        {
            tree[now].flag = x;
            tree[now].but = false;
            return;
        }
        int mid = tree[now].l + tree[now].r >> 1;
        pushdown(now);
        if (r <= mid)
        {
            updata(l, r, x, now << 1);
        }
        else if (mid<l)
        {
            updata(l, r, x, now << 1 | 1);
        }
        else
        {
            updata(l, mid, x, now << 1);
            updata(mid + 1, r, x, now << 1 | 1);
        }
        if (tree[now << 1].flag == tree[now << 1 | 1].flag)tree[now].flag = tree[now << 1].flag;
        else tree[now].flag = -1;
    }

    //取反
    public: void notnum(int l, int r, int now = 1)
    {
        if (r<l)return;
        if (tree[now].l == l&&tree[now].r == r)
        {
            tree[now].but ^= 1;
            if (tree[now].flag != -1) tree[now].flag ^= 1;
            return;
        }
        int mid = tree[now].l + tree[now].r >> 1;
        pushdown(now);
        if (r <= mid)
        {
            notnum(l, r, now << 1);
        }
        else if (mid<l)
        {
            notnum(l, r, now << 1 | 1);
        }
        else
        {
            notnum(l, mid, now << 1);
            notnum(mid + 1, r, now << 1 | 1);
        }
        if (tree[now << 1].flag == tree[now << 1 | 1].flag)tree[now].flag = tree[now << 1].flag;
        else tree[now].flag = -1;
    }

    public: void opeu(int from, int to)
    {
        updata(from, to, 1);
    }

    public: void opei(int from, int to)
    {
        updata(0, from - 1, 0);
        updata(to + 1, MAXSIZE, 0);
    }

    public: void oped(int from, int to)
    {
        updata(from, to, 0);
    }

    public: void opec(int from, int to)
    {
        updata(0, from - 1, 0);
        notnum(from, to);
        updata(to + 1, MAXSIZE, 0);
    }

    public: void opes(int from, int to)
    {
        notnum(from, to);
    }

    public: int main(int argc, char **argv)
    {
        char ope, left, right;
        int from, to;
        build(0, MAXSIZE);
        while (cin >> ope)
        {
            read(left); read(from); right = read(to);;
            //cout<<left<<from<<","<<to<<right<<endl;
            from *= 3; to *= 3;
            if (left == '(') from++;
            if (right == ')') to--;
            switch (ope)
            {
            case 'U':opeu(from, to); break;
            case 'I':opei(from, to); break;
            case 'D':oped(from, to); break;
            case 'C':opec(from, to); break;
            default:opes(from, to);
            }
        }
        bool isempty = true;
        bool last = query(0);
        if (last)
        {
            printf("[0");
            isempty = false;
        }
        for (int i = 1; i <= MAXSIZE; i++)
        {
            int tmp = query(i);
            if (tmp)
            {
                if (!last)
                {
                   if (i % 3) putchar('(');
                   else putchar('[');
                   printf("%d", i / 3);
                   isempty = false;
                }
            }
            else
            {
                if (last)
                {
                   printf(",%d", i / 3);
                   if ((i - 1) % 3) putchar(')');
                   else putchar(']');
                   putchar(' ');
                }
            }
            last = tmp;
        }
        if (isempty) puts("empty set");
        return 0;
    }
    };
}

solution::program theApp;

int main(int argc, char **argv)
{
    return theApp.main(argc, argv);
}

反思

其实我们还可以通过巧妙的转换将区间取反转化为熟悉的区间加，我们可以将偶数看作0，奇数看作1，这样加1便相当于取反。这种方法交给读者自己实现。

时间：
标签： , ,

没有评论:

发表评论

订阅： 博文评论 (Atom)