Codeforces 817F (线段树上二分)

发表于 | 分类于 | | + s

Codeforces 817F
题意：对一个维护三种操作：
1 将$[l,r]$中的数全部加入集合中。
2 将集合中$[l,r]$范围内的数删去。
3 将集合中在$[l,r]$中的数删去，并将之前不在集合中的数加入集合

考虑将每个数字当前一个位置，$0$表示有，$1$表示没有，然后$mex$就是最前面的$0$。显然可以二分。

数据大，考虑离散化。对于1操作，则是区间修改为$1$。对于$2$操作，则是区间修改为$0$
若没有第三个操作，我们完全可以用树状数组+二分完成。而这里可以用线段树代替。

区间翻转相当于$sum=(r-l+1)-sum$
线段树维护两个标记即可。注意标记的抵消的写法。具体看代码。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky { 

    struct xw {
        LL t, l, r, l_s, r_s;
    } qy[100000 + 5];

    LL n;
    LL tax[1000000 + 5], tax_tot;

    #define M ((l + r) >> 1)
    #define lc (o << 1)
    #define rc (o << 1 | 1)
    LL sumv[5000000 + 5], rev[5000000 + 5], upd[5000000 + 5];

    void pushdown(LL o, LL len) {
        if (len == 1) return ;
        if (upd[o] != -1) {
            upd[lc] = upd[rc] = upd[o];
            sumv[lc] = (len - len / 2) * upd[lc], sumv[rc] = (len / 2) * upd[rc];
            upd[o] = -1, rev[o] = 0;
        }
        if (rev[o]) {
            if (upd[lc] != -1)
                upd[lc] ^= 1, sumv[lc] = (len - len / 2) * upd[lc];
            else rev[lc] ^= 1, sumv[lc] = (len - len / 2) - sumv[lc];
            if (upd[rc] != -1)
                upd[rc] ^= 1, sumv[rc] = (len / 2) * upd[rc];
            else rev[rc] ^= 1, sumv[rc] = (len / 2) - sumv[rc];
            rev[o] = 0;
        }
    }
    void pushup(LL o) {sumv[o] = sumv[lc] + sumv[rc];}
    void build(LL o, LL l, LL r) {
        if (l == r) sumv[o] = rev[o] = 0, upd[o] = -1; else {
            build(lc, l, M), build(rc, M + 1, r);
            pushup(o);
        }
    }
    void update(LL o, LL l, LL r, LL x, LL y, LL v) {
        pushdown(o, r - l + 1);
        if (x <= l && r <= y) {
            upd[o] = v;
            sumv[o] = v * (r - l + 1);
            return ;
        }
        if (x <= M) update(lc, l, M, x, y, v);
        if (M < y) update(rc, M + 1, r, x, y, v);
        pushup(o);
    }
    void reverse(LL o, LL l, LL r, LL x, LL y) {
        pushdown(o, r - l + 1);
        if (x <= l && r <= y) {
            if (upd[o] != -1) 
                upd[o] ^= 1, sumv[o] = upd[o] * (r - l + 1);
            else rev[o] ^= 1, sumv[o] = (r - l + 1) - sumv[o];
            return ;
        }
        if (x <= M) reverse(lc, l, M, x, y);
        if (M < y) reverse(rc, M + 1, r, x, y);
        pushup(o);
    }
    LL query(LL o, LL l, LL r) {
        pushdown(o, r - l + 1);
        if (l == r) return tax[l];
        if (sumv[lc] < M - l + 1) return query(lc, l, M);
        return query(rc, M + 1, r);
    }

    void clean() {
        tax_tot = 0;
    }
    int solve() {

        clean();

        scanf("%lld", &n);
        tax[++tax_tot] = 1;
        for (LL i = 1; i <= n; ++i) {
            scanf("%lld%lld%lld", &qy[i].t, &qy[i].l, &qy[i].r);
            tax[++tax_tot] = qy[i].l, tax[++tax_tot] = qy[i].r;
            tax[++tax_tot] = qy[i].l + 1, tax[++tax_tot] = qy[i].r + 1;
            if (qy[i].l - 1 > 0) tax[++tax_tot] = qy[i].l - 1;
            if (qy[i].r - 1 > 0) tax[++tax_tot] = qy[i].r - 1;
        }

        sort(tax + 1, tax + 1 + tax_tot);
        tax_tot = unique(tax + 1, tax + 1 + tax_tot) - tax - 1;

        for (LL i = 1; i <= n; ++i) {
            qy[i].l_s = lower_bound(tax + 1, tax + 1 + tax_tot, qy[i].l) - tax;
            qy[i].r_s = lower_bound(tax + 1, tax + 1 + tax_tot, qy[i].r) - tax;
            //printf("%lld %lld\n", qy[i].l_s, qy[i].r_s);
        }

        build(1, 1, tax_tot);

        for (LL i = 1; i <= n; ++i) {
            if (qy[i].t == 1) {
                update(1, 1, tax_tot, qy[i].l_s, qy[i].r_s, 1);
            }
            if (qy[i].t == 2) {
                update(1, 1, tax_tot, qy[i].l_s, qy[i].r_s, 0);
            }
            if (qy[i].t == 3) {
                reverse(1, 1, tax_tot, qy[i].l_s, qy[i].r_s);
            }
            printf("%lld\n", query(1, 1, tax_tot));
        }

        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------