洛谷P5568 [SDOI2008] 校门外的区间题解

题目链接：P5568 [SDOI2008] 校门外的区间

题意：

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

五种运算如下：

U T：$S = S \cup T$

I T：$S = S \cap T$

D T：$S = S - T$

C T：$S = T - S$

S T：$S = S \oplus T$

集合的基本运算操作定义如下：

$A \cup B$：$\{x | x \in A \vee x \in B\}$

$A \cap B$：$\{x | x \in A \wedge x \in B\}$

$A - B$：$\{x | x \in A \wedge x \notin B\}$

$A \oplus B$：$(A-B)\cup (B-A)$

输入格式：

输入 $M$ 行。

每行第一个字母描述操作类型，后面给出一个区间，区间用(a,b)，(a,b]，[a,b)，[a,b] 表示。

输出格式：

输出一行若干区间，代表集合 $S$，所有区间按递增顺序输出，相邻两个区间之间以一个空格隔开。

如果区间为空，输出 empty set。

数据范围：

$ 0 \le a,b \le 65535, M \le 70000$

考虑线段树维护。然后题目就变成了一个区间覆盖和翻转的问题。

注意翻转标记和加法标记类似，要在覆盖标记后处理。

然后这题的读入也很麻烦。对于开闭区间，可以把原来的端点乘 $2$ ，这样就变成全是闭区间了。

时间复杂度 $\mathcal{O}(q \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define DDD cout << "line here is " << __LINE__ << '\n';
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(65535 * 2 + 1015))

struct node { int cov,tag; } tr[N * 4];
const int n = 65535 * 2 + 1000; int ans[N]; char s[20];

#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)
void build(int l,int r,int at)
{
    tr[at] = {-1,0}; if(l == r) return;
    int mid = (l + r) >> 1;
    build(l,mid,ls(at)); build(mid+1,r,rs(at));
}
void push_down(int at)
{
    if(tr[at].cov != -1)
    {
        tr[ls(at)].cov = tr[rs(at)].cov = tr[at].cov;
        tr[ls(at)].tag = tr[rs(at)].tag = 0;
        tr[at].cov = -1;
    }
    if(tr[at].tag)
    {
        tr[ls(at)].tag ^= 1; tr[rs(at)].tag ^= 1;
        tr[at].tag = 0;
    }
}
void update(int nl,int nr,int k,int l=0,int r=n,int at=1)
{
    if(nl > nr) return;
    if(nl <= l && r <= nr)
    {
        if(k != 2) tr[at] = {k,0};
        else tr[at].tag ^= 1;
        return;
    }
    push_down(at); int mid = (l + r) >> 1;
    if(nl <= mid) update(nl,nr,k,l,mid,ls(at));
    if(nr > mid) update(nl,nr,k,mid+1,r,rs(at));
}
void query(int l,int r,int at)
{
    if(l == r)
    {
        if(tr[at].cov == -1) ans[l] = 0;
        else ans[l] = tr[at].cov ^ tr[at].tag;
        return;
    }
    push_down(at); int mid = (l + r) >> 1;
    query(l,mid,ls(at)); query(mid+1,r,rs(at));
}
#define gc() getchar()
#define pc(a) putchar(a)
void get(int &l,int &r)
{
    char ch = gc(); while(ch != '(' && ch != '[') ch = gc();
    int w = (ch == '('); l = r = 0; while(!isdigit(ch)) ch = gc();
    while(isdigit(ch)) { l = (l << 1) + (l << 3) + (ch ^ 48); ch = gc(); }
    l <<= 1; l += w; while(!isdigit(ch)) ch = gc();
    while(isdigit(ch)) { r = (r << 1) + (r << 3) + (ch ^ 48); ch = gc(); }
    r <<= 1; while(ch != ')' && ch != ']') ch = gc(); r -= (ch == ')');
}
void print()
{
    query(0,n,1);
    int flag = 0, sz = 0;
    for(int i=0; i<=n; i++)
    {
        if(ans[i] && !flag)
        {
            flag = sz = 1;
            if(i & 1) cout << '(' << ((i-1) >> 1) << ',';
            else cout << '[' << (i >> 1) << ',';
        }
        if(!ans[i] && flag)
        {
            flag = 0;
            if(i & 1) cout << ((i-1) >> 1) << "] ";
            else cout << (i >> 1) << ") ";
        }
    }
    if(!sz) cout << "empty set\n";
}
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    build(1,n,1);
    for(int l,r; scanf("%s", s) != EOF; )
    {
        get(l,r); // DDD;
        switch(s[0])
        {
            case 'U' : update(l,r,1); break;
            case 'I' : update(0,l-1,0); update(r+1,n,0); break;
            case 'D' : update(l,r,0); break;
            case 'C' : update(0,n,2); update(0,l-1,0); update(r+1,n,0); break;
            case 'S' : update(l,r,2); break;
            default : cout << "what ??" << '\n'; break;
        }
    }
    print();
    return 0;
}