noip2017集训测试赛（三） Problem B: mex [补档]

Description

给你一个无限长的数组，初始的时候都为0，有3种操作：

操作1是把给定区间[l,r][l,r] 设为1，

操作2是把给定区间[l,r][l,r] 设为0，

操作3把给定区间[l,r][l,r] 0,1反转。

一共n个操作，每次操作后要输出最小位置的0。

Input

第一行一个整数n，表示有n个操作

接下来n行，每行3个整数op,l,r表示一个操作

Output

共n行，一行一个整数表示答案

Sample Input

Sample Output

HINT

对于30%的数据\(1≤n≤10^3,1≤l≤r≤10^{18}1≤n≤10^3,1≤l≤r≤10^{18}\)

对于100%的数据\(1≤n≤10^5,1≤l≤r≤10^{18}1≤n≤10^5,1≤l≤r≤10^{18}\)

Solution

正解时空复杂度为\(O(n \log n)\).

我的解法时空复杂度也是\(O(n \log n)\)

但是它就是MLE了那么一点.

正解: 离散化 + 线段树.

我的做法: 开两棵离散线段树, 分别代表0和1, 每次把一棵中的一些点拆下来放到另一棵里面.

/*

mind the value of INF

*/

#include <cstdio>

#include <cctype>

namespace Zeonfai

{

    inline long long getInt()

    {

        long long a = 0, sgn = 1; char c;

        while(! isdigit(c = getchar())) if(c == '-') sgn *= -1;

        while(isdigit(c)) a = a * 10 + c - '0', c = getchar();

        return a * sgn;

    }

}

const long long INF = (long long)1e18 + 7;

// const long long INF = 11;

struct segmentTree

{

    struct node

    {

        node *suc[2];

        long long L, R;

        long long vst, sz;

        inline node(long long _L, long long _R)

        {

            L = _L; R = _R; vst = 0; sz = R - L + 1;

            for(long long i = 0; i < 2; ++ i) suc[i] = NULL;

        }

    }*rt;

    struct result

    {

        node *a, *b;

        inline result(node *_a, node *_b) {a = _a; b = _b;}

    };

    inline void initialize() {rt = new node(1, INF);}

    result split(node *u, long long L, long long R)

    {

        if(u == NULL || (u->L >= L && u->R <= R)) return result(u, NULL);

        long long mid = u->L + u->R >> 1;

        if(! u->vst)

        {

            u->suc[0] = new node(u->L, mid); u->suc[1] = new node(mid + 1, u->R);

            u->vst = 1;

        }

        node *_u = new node(u->L, u->R); _u->vst = 1;

        if(L <= mid)

        {

            result res = split(u->suc[0], L, R);

            _u->suc[0] = res.a; u->suc[0] = res.b;

        }

        if(R > mid)

        {

            result res = split(u->suc[1], L, R);

            _u->suc[1] = res.a; u->suc[1] = res.b;

        }

        u->sz = 0;

        for(long long i = 0; i < 2; ++ i) if(u->suc[i] != NULL) u->sz += u->suc[i]->sz;

        _u->sz = 0;

        for(long long i = 0; i < 2; ++ i) if(_u->suc[i] != NULL) _u->sz += _u->suc[i]->sz;

        return result(_u, u);

    }

    inline node* split(long long L, long long R)

    {

        result res = split(rt, L, R);

        rt = res.b; return res.a;

    }

    inline node* merge(node *u, node *_u)

    {

        if(u == NULL) return _u; if(_u == NULL) return u;

        for(long long i = 0; i < 2; ++ i) u->suc[i] = merge(u->suc[i], _u->suc[i]);

        u->sz = 0;

        for(long long i = 0; i < 2; ++ i) if(u->suc[i] != NULL) u->sz += u->suc[i]->sz;

        delete _u; return u;

    }

    inline void merge(node *u) {rt = merge(rt, u);}

    long long query(node *u)

    {

        if(! u->vst) return u->L;

        else if(u->suc[0] != NULL && u->suc[0]->sz) return query(u->suc[0]);

        else return query(u->suc[1]);

    }

    inline long long query() {return query(rt);}

}seg[2];

int main()

{

#ifndef ONLINE_JUDGE

    freopen("mex.in", "r", stdin);

    freopen("mex.out", "w", stdout);

#endif

    using namespace Zeonfai;

    seg[0].initialize();

    long long n = getInt();

    for(long long i = 0; i < n; ++ i)

    {

        long long opt = getInt(); long long L = getInt(), R = getInt();

        if(opt == 1) seg[1].merge(seg[0].split(L, R));

        else if(opt == 2) seg[0].merge(seg[1].split(L, R));

        else if(opt == 3)

        {

            segmentTree::node *u = seg[0].split(L, R), *v = seg[1].split(L, R);

            seg[0].merge(v); seg[1].merge(u);

        }

        printf("%lld\n", seg[0].query());

    }

}

巴特西