题目链接

MEX Queries

题目描述

You are given a set of integer numbers, initially it is empty. You should perform $n$ queries.

There are three different types of queries:

  • $1\ l\ r$ — Add all missing numbers from the interval $[l,r]$
  • $2\ l\ r$ — Remove all present numbers from the interval $[l,r]$
  • $3\ l\ r$ — Invert the interval $[l,r]$ — add all missing and remove all present numbers from the interval $[l,r]$
    After each query you should output MEX of the set — the smallest positive ($MEX  \ge 1$) integer number which is not presented in the set.

输入格式

The first line contains one integer number $n$ ($1 \le n \le 10^5$).
Next $n$ lines contain three integer numbers $t,l,r$ ($1 \le t \le 3$,$1 \le l \le r \le 10^{18}$) — type of the query, left and right bounds.

输出格式

Print $MEX$ of the set after each query.

样例输入1

3
1 3 4
3 1 6
2 1 3

样例输出1

1
3
1

样例输入2

4
1 1 3
3 5 6
2 4 4
3 1 6

样例输出2

4
4
4
1

题解

题意:维护一个集合,有三种操作,第一种操作将区间$[l,r]$内所有元素加入集合中;第二种操作将区间$[l,r]$内所有在集合内的元素从集合中删除;第三种操作将区间$[l,r]$中所有在集合内的元素删除,不在集合内的元素加入集合。
要求每次操作后输出最小的没有在集合内的元素。
很明显是一道线段树水题,每次区间修改加上懒标记就好了。
但是我们发现这里区间的范围在$1e18$内,所幸修改操作数在$1e5$内,所以我们可以离散化一下。
因为如果直接离散化$l,r$的话边界情况会比较难处理,每次操作要离散$3$个点,所以我这里是离散化$l,r+1$,把区间离散化而不是把点离散化。
我们用$i$表示元素$i$和元素$i-1$的交界,那么我们要修改$[l,r]$的时候就要离散化$l$和$l-1$的交界和$r$和$r+1$的交界,也就是$l,r+1$两个点。
上代码:

#include<bits/stdc++.h>
using namespace std;
int n;
struct aa{
    int t;
    long long l,r;
}a[500009];
int lt=1;
struct cc{
    long long s;
    int from;
    bool k;
}to[500009];
struct bb{
    int x;
    int ld;
}p[4000009];
bool cmp(cc x,cc y){return x.s<y.s;}
void dn(int u,int l,int r){
    if(p[u].ld&(1<<2)){
        p[u*2].ld=p[u*2+1].ld=(1<<2);
        p[u].x=r-l;
    }
    if(p[u].ld&(1<<1)){
        p[u*2].ld=p[u*2+1].ld=(1<<1);
        p[u].x=0;
    }
    if(p[u].ld&1){
        p[u].x=r-l-p[u].x;
        if(p[u*2].ld&(1<<2)) p[u*2].ld=(1<<1);
        else if(p[u*2].ld&(1<<1)) p[u*2].ld=(1<<2);
        else p[u*2].ld^=1;
        if(p[u*2+1].ld&(1<<2)) p[u*2+1].ld=(1<<1);
        else if(p[u*2+1].ld&(1<<1)) p[u*2+1].ld=(1<<2);
        else p[u*2+1].ld^=1;
    }
    p[u].ld=0;
}
void dfs(int u,int l,int r,int x){
    dn(u,l,r);
    if(r<=a[x].l || l>=a[x].r) return;
    if(l>=a[x].l && r<=a[x].r){
        p[u].ld=(1<<(3-a[x].t));
        dn(u,l,r);
        if(r==l+1) return;
        dn(u*2,l,(l+r)/2);
        dn(u*2+1,(l+r)/2,r);
        p[u].x=p[u*2].x+p[u*2+1].x;
        return;
    }
    if(r==l+1) return;
    dfs(u*2,l,(l+r)/2,x);
    dfs(u*2+1,(l+r)/2,r,x);
    p[u].x=p[u*2].x+p[u*2+1].x;
}
void fd(int u,int l,int r){
    dn(u,l,r);
    if(p[u].x==0){
        printf("%lld\n",to[l].s);
        return;
    }
    else if(p[u].x==r-l){
        printf("%lld\n",to[r].s);
        return;
    }else{
        dn(u*2,l,(l+r)/2);
        if(p[u*2].x==(l+r)/2-l) fd(u*2+1,(l+r)/2,r);
        else fd(u*2,l,(l+r)/2);
    }
}
int main(){
    scanf("%d",&n);
    for(int j=1;j<=n;j++){
        scanf("%d%lld%lld",&a[j].t,&a[j].l,&a[j].r);
        a[j].r++;
        to[j*2-1].s=a[j].l;
        to[j*2-1].from=j;
        to[j*2].s=a[j].r;
        to[j*2].from=j;
        to[j*2].k=1;
    }
    to[n*2+1].s=1;
    sort(to+1,to+n*2+2,cmp);
    if(to[1].k) a[to[1].from].r=1;
    else a[to[1].from].l=1;
    for(int j=2;j<=n*2+1;j++){
        if(to[j].s!=to[lt].s) to[++lt]=to[j];
        if(to[j].k) a[to[j].from].r=lt;
        else a[to[j].from].l=lt;
    }
    for(int j=1;j<=n;j++){
        dfs(1,1,lt,j);
        fd(1,1,lt);
    }
    return 0;
}