题解 CF817F 【MEX Queries】

RedreamMer · 2020-07-28 13:23:56 · 题解

\Large{\texttt{CF817F}}

题目调了好久，发片题解纪念下QwQ

算法：线段树+离散化

（题意略有改动）

共有 n 个操作，一个区间（初始全为 0 ），共三种操作如下：

区间修改，查询，首先想到线段树，但是建一个 10^{18} 量级的线段树，时间和空间显然不合理。

但是发现 n 的范围很小，每次修改的区间的左右端点顶多也只有2*10^{5}，所以套路将数据离线下来进行离散化处理，将每个端点排序再依次标号，用数组储存。

然后的操作和普通的线段树没有什么不同，在线段数中对每一段区间存储两个变量( p_0 ：区间中是否有 0 ， p_1 ：区间中是否有 1 )。

操作一：p_0 赋值为 0 ， p_1 赋值为 1 。

操作二：p_0 赋值为 0 ， p_1 赋值为 1 。

操作三：交换 p_0 和 p_1 。

但是需要注意的是（这里我卡了好久）， \texttt{push\_down} 的操作中，对于要下传的标记为3时，若儿子节点的懒标记还没有下传，是不可以直接覆盖的，原因显然。

可是懒标记的特点就是 “懒” ，不可能让操作一直递归下去吧。

所以对此需要进行分类讨论：

若下传的操作是 1 或 2 ：可以直接覆盖懒标记，因为这次操作会将整个区间都赋值为 0 或 1 ，和之前的操作无关。

若下传的操作是 3 ：那么如果懒标记为 3 ，可以直接消除懒标记，取反 + 取反 = 不变。

若下传的操作是 3 ：如果懒标记为 1 ，则就改懒标记为 2 ，如果懒标记为 2 ，则就改懒标记为 1 ，覆盖( 1/0 )+取反=覆盖( 0/1 ) （这个操作代码中未体现 其实是我懒的写）。

代码细节还是挺多的，请细细看（码风应该可以令人接受QwQ）

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(1)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <immintrin.h>
#include <emmintrin.h>
//qqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzk
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <bits/stdc++.h>
using namespace std;

// #define PB push_back
// #define MP make_pair
#define ls now << 1
#define rs now << 1 | 1
// #define int long long
// #define us unsigned
#define LL long long
const int N = 1e5;
// const int N = 4e5;
// #define re register
// const int mod = 1e9 + 7;
// const int inf = 0x7fffffff;
// char buf[(int)1e8], *ss = buf;
// inline int INIT()
// {
//     buf[fread(buf, 1, (int)1e8 - 1, stdin)] = '\n';
//     fclose(stdin);
//     return 0;
// }
// const int __START__ = INIT();

inline char nc()
{
    static const int BS = 1 << 22;
    static unsigned char buf[BS], *st, *ed;
    if (st == ed)
        ed = buf + fread(st = buf, 1, BS, stdin);
    return st == ed ? EOF : *st++;
}
//#define nc getchar
inline LL read()
{
    char ch;
    LL res = 0;
    bool flag = 0;
    while (!isdigit(ch = nc()))
        ;
    while (ch >= '0' and ch <= '9')
    {
        res = (res << 1) + (res << 3) + (ch - '0');
        ch = nc();
    }
    return res;
}

int a, top, id;
LL p[(N << 5) + 10];
map<LL, int> st;
struct node
{
    int opt;
    LL l, r;
} s[(N << 5) + 10];
struct S
{
    int l, r, lazy;
    bool p0, p1, qq;
} m[(N << 5) + 10];

inline void up(int now)
{
    m[now].p0 = m[ls].p0 | m[rs].p0;
    m[now].p1 = m[ls].p1 | m[rs].p1;
}

inline void down(int now)
{
    if (!m[now].lazy || m[now].qq)
        return;
    if (m[now].lazy == 1)
    {
        m[ls].p0 = m[rs].p0 = 0;
        m[ls].p1 = m[rs].p1 = 1;
    }
    else if (m[now].lazy == 2)
    {
        m[ls].p0 = m[rs].p0 = 1;
        m[ls].p1 = m[rs].p1 = 0;
    }
    else
    {
        if (m[ls].lazy)
            down(ls);
        if (m[rs].lazy)
            down(rs);
        swap(m[ls].p0, m[ls].p1);
        swap(m[rs].p0, m[rs].p1);
    }
    m[ls].lazy = m[rs].lazy = m[now].lazy;
    m[now].lazy = 0;
}

inline void build(int now, int l, int r)
{
    m[now].l = l;
    m[now].r = r;
    if (l == r)
    {
        m[now].p0 = 1;
        m[now].p1 = 0;
        m[now].qq = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    up(now);
    return;
}

inline void add(int now, int l, int r, int k)
{
    if (m[now].l >= l && m[now].r <= r)
    {
        if (k == 1)
        {
            m[now].p0 = 0;
            m[now].p1 = 1;
        }
        else if (k == 2)
        {
            m[now].p0 = 1;
            m[now].p1 = 0;
        }
        else
        {
            swap(m[now].p0, m[now].p1);
        }
        if (k == 1 || k == 2)
            m[now].lazy = k;
        else if (k == 3 && m[now].lazy == 3)
            m[now].lazy = 0;
        else
        {
            down(now);
            m[now].lazy = k;
        }
        return;
    }
    down(now);
    int mid = (m[now].l + m[now].r) >> 1;
    if (l <= mid)
        add(ls, l, r, k);
    if (mid < r)
        add(rs, l, r, k);
    up(now);
}

inline int query(int now, int l, int r)
{
    if (m[now].r < l || m[now].l > r || m[now].p0 == 0)
        return -1;
    if (m[now].p0 == 1 && m[now].p1 == 0)
        return m[now].l;
    down(now);
    int mid = (m[now].l + m[now].r) >> 1;
    int k = query(ls, l, r);
    if (k != -1)
        return k;
    return query(rs, l, r);
}

signed main()
{
    a = read();
    for (int i = 1; i <= a; i++)
    {
        s[i].opt = read();
        s[i].l = read();
        s[i].r = read();
        if (s[i].l != 1)
            p[++top] = s[i].l - 1;
        p[++top] = s[i].l;
        p[++top] = s[i].l + 1;
        if (s[i].r != 1)
            p[++top] = s[i].r - 1;
        p[++top] = s[i].r;
        p[++top] = s[i].r + 1;
    }
    p[++top] = 1;
    sort(p + 1, p + top + 1);
    int k = unique(p + 1, p + top + 1) - p - 1;
    build(1, 1, k);
    for (int i = 1; i <= k; i++)
        st[p[i]] = i;
    // cout << st[2] << ' ' << st[10];
    for (int i = 1; i <= a; i++)
    {
        add(1, st[s[i].l], st[s[i].r], s[i].opt);
        // for (int i = 1; m[i].l; i++)
        //     cout << i << ' ' << m[i].l << ' ' << m[i].r << ' ' << m[i].p0 << ' ' << m[i].p1 << ' ' << m[i].lazy << endl;
        printf("%lld\n", p[query(1, 1, k)]);
    }
    return 0;
}

\large\texttt{My Blog}