首页 > 代码库 > POJ 3225——Help with Intervals（线段树，成段替换+区间异或+hash）

POJ 3225——Help with Intervals（线段树，成段替换+区间异或+hash）

2024-07-21 18:55:54   230人阅读

Help with Intervals
Time Limit: 6000MS Memory Limit: 131072K
Total Submissions: 10444 Accepted: 2551
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:

OperationNotation

Definition

UnionA ∪ B{x : x ∈ A or x ∈ B}
IntersectionA ∩ B{x : x ∈ A and x ∈ B}
Relative complementationA ? B{x : x ∈ A but x ? B}
Symmetric differenceA ⊕ 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:

CommandSemantics
U TS ← S ∪ T
I TS ← S ∩ T
D TS ← S ? T
C TS ← T ? S
S TS ← 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)


——————————————————————分割线————————————————————

题目大意：

就是实现区间的交，并，补，异或操作


思路：

对于区间的开，闭，将区间乘2，开的话，左端点+1，右端点-1.奇数表示开，偶数表示闭

例如(3,6)变成[7,11]，左右端点为奇数，所以左右为开，退回来的时候判断7为奇数，11也为奇数，就是（ 7/2, (11+1)/2 )

覆盖标记0、1，-1  ：0表示不包含，1表示包含，-1表示既有包含也有不包含

异或标记0、1：0表示没有标记，1表示有标记


则：

U L,R将区间L,R覆盖为1

D L,R将区间L,R覆盖为0

I L,R将区间<L和>R覆盖为0

C L,R将区间<L和>R覆盖为0，对区间L,R 0,1进行对换（异或）

S L,R将区间L,R  0,1进行对换（异或）


对于覆盖标记，如果存在异或标记，则将异或标记清0

对于异或标记，优先考虑是否存在覆盖标记，如果存在，则对覆盖标记异或，否则对异或标记异或


PS：还要熟练掌握push_down的内涵才行~~~

#include <iostream>
#include <cstring>
#include <cstdio>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=131071;
using namespace std;
bool hash[maxn+5];
int cover[maxn<<2],Xor[maxn<<2];
void fxor(int rt)
{
    if(cover[rt]!=-1) cover[rt]^=1;
    else Xor[rt]^=1;
}
void push_down(int rt)
{
    if(cover[rt]!=-1){
        cover[rt<<1]=cover[rt<<1|1]=cover[rt];
        cover[rt]=-1;
        Xor[rt]=0;
    }
    if(Xor[rt]){
        fxor(rt<<1);
        fxor(rt<<1|1);
        Xor[rt]=0;
    }
}
void update(char op,int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R){
        if(op=='U'){
            cover[rt]=1;
            Xor[rt]=0;
        }
        if(op=='D'){
            Xor[rt]=cover[rt]=0;
        }
        if(op=='C'||op=='S'){
            fxor(rt);
        }
        return ;
    }
    push_down(rt);
    int m=(l+r)>>1;
    if(L<=m) update(op,L,R,lson);
    else if(op=='I'||op=='C'){
        Xor[rt<<1]=cover[rt<<1]=0;
    }
    if(m<R) update(op,L,R,rson);
    else if(op=='I'||op=='C'){
        Xor[rt<<1|1]=cover[rt<<1|1]=0;
    }

}
void query(int l,int r,int rt)
{
    if(cover[rt]==1){
        for(int it=l;it<=r;++it){
            hash[it]=true;
        }
        return;
    }else if(cover[rt]==0) return;
    push_down(rt);
    int m=(l+r)>>1;
    query(lson);
    query(rson);
}
int main()
{
    char op,l,r;int a,b;
    while(scanf("%c %c%d,%d%c\n",&op,&l,&a,&b,&r)!=EOF){
        a<<=1,b<<=1;
        if(l=='(') a++;
        if(r==')') b--;
        if(a>b){
            if(op=='I'||op=='C'){
                Xor[1]=cover[1]=0;
            }
        }else{
            update(op,a,b,0,maxn,1);
        }
    }
    query(0,maxn,1);
    int s=-1,e;
    bool flag=false;
    for(int i=0;i<=maxn;++i){
        if(hash[i]){
            if(s==-1) s=i;
            e=i;
        }else{
            if(s!=-1){
                if(flag) printf(" ");
                flag=true;
                printf("%c%d,%d%c",s&1?'(':'[',s>>1,(e+1)>>1,e&1?')':']');
                s=-1;
            }
        }
    }
    if(!flag) printf("empty set\n");
    printf("\n");
    return 0;
}



POJ 3225——Help with Intervals（线段树，成段替换+区间异或+hash）


联系
我们