CF817F MEX Queries

题目

CF
luogu

思路

好菜呀
数据太大，需要离散化
但是离散化x的时候，需要带上x-1和x+1
因为这也有可能是答案，当然你分类讨论也阔以
然后维护一下第一个1出现的位置和第一个0出现的位置

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define ls rt<<1
#define rs rt<<1|1
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn = 6e5 + 7;
const int inf = 0x3f3f3f3f;
ll read() {
    ll x = 0, f = 1; char s = getchar();
    for (; s < '0' || s > '9'; s = getchar()) if (s == '-') f = -1;
    for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';
    return x * f;
}
struct node {
    int l, r, size;
    int k1, k0, sum;
    int lazy1, lazy2;
    void sap() {
        swap(k1,k0);
        sum=size-sum;
        lazy2++;
    }
} e[maxn << 2];
int n;
void pushup(int rt) {
    e[rt].k0 = (e[ls].k0 == e[rt].l+e[ls].size+1) ? e[rs].k0 : e[ls].k0;
    e[rt].k1 = (e[ls].k1 == e[rt].l+e[ls].size+1) ? e[rs].k1 : e[ls].k1;
    e[rt].sum = e[ls].sum + e[rs].sum;
}
void pushdown(int rt) {
    if (e[rt].lazy1 != -1) {
        e[rs].lazy1 = e[ls].lazy1 = e[rt].lazy1;
        e[rs].lazy2 = e[ls].lazy2 = 0;
        if (e[rt].lazy1 == 0) {
            e[ls].k0 = e[ls].l;
            e[ls].k1 = e[ls].l+e[ls].size+1;
            e[ls].sum = 0;
            e[rs].k0 = e[rs].l;
            e[rs].k1 = e[rs].l+e[rs].size+1;
            e[rs].sum = 0;
        } else {
            e[ls].k1 = e[ls].l;
            e[ls].k0 = e[ls].l+e[ls].size+1;
            e[ls].sum = e[ls].size;
            e[rs].k1 = e[rs].l;
            e[rs].k0 = e[rs].l+e[rs].size+1;
            e[rs].sum = e[rs].size;
        }
        e[rt].lazy1 = -1;
    }
    if (e[rt].lazy2 % 2) {
        e[ls].sap();
        e[rs].sap();
        e[rt].lazy2 = 0;
    }
}
void build(int l, int r, int rt) {
    e[rt].l = l, e[rt].r = r, e[rt].size = r - l + 1;
    e[rt].lazy1 = -1;
    if (l == r) {
        e[rt].k0 = e[rt].l;
        e[rt].k1 = e[rt].l+e[rt].size+1;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ls);
    build(mid + 1, r, rs);
    pushup(rt);
}
void modify_1(int L, int R, int k, int rt) {
    if (L <= e[rt].l && e[rt].r <= R) {
        if (k == 0) {
            e[rt].k0 = e[rt].l;
            e[rt].k1 = e[rt].l+e[rt].size+1;
            e[rt].sum = 0;
            e[rt].lazy1 = 0;
        } else {
            e[rt].k1 = e[rt].l;
            e[rt].k0 = e[rt].l+e[rt].size+1;
            e[rt].sum = e[rt].size;
            e[rt].lazy1 = 1;
        }
        e[rt].lazy2 = 0;
        return;
    }
    pushdown(rt);
    int mid = (e[rt].l + e[rt].r) >> 1;
    if (L <= mid) modify_1(L, R, k, ls);
    if (R > mid) modify_1(L, R, k, rs);
    pushup(rt);
}
void modify_2(int L, int R, int rt) {
    if (L <= e[rt].l && e[rt].r <= R) {
        e[rt].sap();
        return;
    }
    pushdown(rt);
    int mid = (e[rt].l + e[rt].r) >> 1;
    if (L <= mid) modify_2(L, R, ls);
    if (R > mid) modify_2(L, R, rs);
    pushup(rt);
}
struct dsr {
    int pd;
    ll x,y;
}Q[maxn];
ll b[maxn];
int gs;
int main() {
    // 离散化
    n = read();
    b[++gs]=1;
    FOR(i, 1, n) {
        Q[i].pd=read(),Q[i].x=read(),Q[i].y=read();
        b[++gs]=Q[i].x;
        b[++gs]=Q[i].x+1;
        if(Q[i].x-1!=0)
        b[++gs]=Q[i].x-1;
        b[++gs]=Q[i].y;
        b[++gs]=Q[i].y+1;
        if(Q[i].y-1!=0)
        b[++gs]=Q[i].y-1;
    }
    sort(b+1,b+1+gs);
    int PKU=unique(b+1,b+1+gs)-b-1;
    FOR(i,1,n) {
        Q[i].x=lower_bound(b+1,b+1+PKU,Q[i].x)-b;
        Q[i].y=lower_bound(b+1,b+1+PKU,Q[i].y)-b;
    }
    // 询问
    build(1, 6e5, 1);
    FOR(i,1,n) {
        if (Q[i].pd == 1) {
            modify_1((int)Q[i].x, (int)Q[i].y, 1, 1);
        } else if (Q[i].pd == 2) {
            modify_1((int)Q[i].x, (int)Q[i].y, 0, 1);
        } else {
            modify_2((int)Q[i].x, (int)Q[i].y, 1);
        }
        printf("%lld\n",b[e[1].k0]);
    }
    return 0;
}