[Codeforces]817F. 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 ≥ 1) integer number which is not presented in the set.
Input
The first line contains one integer number n (1 ≤ n ≤ 105).
Next n lines contain three integer numbers t, l, r (1 ≤ t ≤ 3, 1 ≤ l ≤ r ≤ 1018) — type of the query, left and right bounds.
Output
Print MEX of the set after each query.
Examples
input
3
1 3 4
3 1 6
2 1 3
output
1
3
1
input
4
1 1 3
3 5 6
2 4 4
3 1 6
output
4
4
4
1
Note
Here are contents of the set after each query in the first example:
{3, 4} — the interval [3, 4] is added
{1, 2, 5, 6} — numbers {3, 4} from the interval [1, 6] got deleted and all the others are added
{5, 6} — numbers {1, 2} got deleted

题意

给你一个无限长的数组，初始的时候都为0，操作1是把给定区间清零，操作2是把给定区间设为1，操作3把给定区间反转。每次操作后要输出最小位置的0。

题解

看到数据范围n<=10^5，结合题意可以考虑使用线段树维护对区间的修改操作。但是l，r<=10^18，所以首先要离散化一下。在使用线段树维护的时候，节点维护该区间数相加的总和。对于操作1和操作2,我们分别赋值为1和0，对于操作3，我们把区间反转，那么新的区间和就是区间的长度减去原来的区间和。然后每次查询最小位置的0，只需要看一下左儿子所代表的区间是否小于这个区间的长度，如果是就在左儿子，否则就在右儿子查找。

题目细节

这道题有很多坑人的点，首先，在离散化的时候必须把1也加上，因为答案可能为1；线段树在下传标记时要注意顺序；记录原来信息的数组必须得开long long，空间一定要开够。

代码

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<map>

 using namespace std;

 #define ll long long

 #define REP(i,a,b) for(register int i=(a),_end_=(b);i<=_end_;i++)

 #define DREP(i,a,b) for(register int i=(a),_end_=(b);i>=_end_;i--)

 #define EREP(i,a) for(register int i=start[(a)];i;i=e[i].next)

 inline int read()

 {

     int sum=,p=;char ch=getchar();

     while(!((''<=ch && ch<='') || ch=='-'))ch=getchar();

     if(ch=='-')p=-,ch=getchar();

     while(''<=ch && ch<='')sum=sum*+ch-,ch=getchar();

     return sum*p;

 }

 const int maxn=;

 map <ll,int> mp;

 int m,cnt;

 ll s[maxn*],n;

 struct qu {

     ll l,r;

     int type;

 }a[maxn];

 struct node {

     int s,lz,id;//s记录区间和，lz为懒标记，id维护区间是否反转

 }c[maxn*];

 #define lc (o<<1)

 #define rc (o<<1 | 1)

 #define left lc,l,mid

 #define right rc,mid+1,r

 inline void make_tree(int o,int l,int r)

 {

     c[o].s=;c[o].lz=-;c[o].id=;

     if(l==r)return;

     int mid=(l+r)>>;

     make_tree(left);

     make_tree(right);

 }

 void maintain(int o,int l,int r)

 {

     c[o].s=c[lc].s+c[rc].s;

 }

 void pushdown(int o,int l,int r)

 {

     int mid=(l+r)>>;

     if(c[o].lz!=-)//下传懒标记，同时将儿子节点的反转标记清0

     {

         c[lc].lz=c[rc].lz=c[o].lz;

         c[lc].s=(mid-l+)*c[o].lz;

         c[rc].s=(r-mid)*c[o].lz;

         c[lc].id=c[rc].id=;

         c[o].lz=-;

     }

     if(c[o].id)//将儿子节点的反转标记也反转，同时维护儿子的区间和

     {

         c[lc].id^=;

         c[rc].id^=;

         c[lc].s=(mid-l+)-c[lc].s;

         c[rc].s=(r-mid)-c[rc].s;

         c[o].id=;

     }

 }

 inline void updates(int ql,int qr,int x,int o,int l,int r)

 {

     pushdown(o,l,r);

     if(ql==l && r==qr)//把区间覆盖为x

     {

         c[o].s=(r-l+)*x;

         c[o].lz=x;

         c[o].id=;

         return;

     }

     int mid=(l+r)>>;

     if(ql>mid)

     {

         updates(ql,qr,x,right);

     }

     else if(qr<=mid)

     {

         updates(ql,qr,x,left);

     }else

     {

         updates(ql,mid,x,left);

         updates(mid+,qr,x,right);

     }

     maintain(o,l,r);

 }

 inline void updatex(int ql,int qr,int o,int l,int r)

 {

     pushdown(o,l,r);

     if(ql==l && r==qr)//把区间反转

     {

         c[o].s=(r-l+)-c[o].s;

         c[o].id^=;

         return;

     }

     int mid=(l+r)>>;

     if(ql>mid)

     {

         updatex(ql,qr,right);

     }

     else if(qr<=mid)

     {

         updatex(ql,qr,left);

     }else

     {

         updatex(ql,mid,left);

         updatex(mid+,qr,right);

     }

     maintain(o,l,r);

 }

 void init()

 {

     m=read();

     REP(i,,m)

     {

         cin>>a[i].type>>a[i].l>>a[i].r;

         a[i].r++;

         s[++cnt]=a[i].l;

         s[++cnt]=a[i].r;

     }

     s[++cnt]=;//答案中可能会有1，必须加上

     sort(s+,s+cnt+);

     n=unique(s+,s+cnt+)-(s+);

     REP(i,,n)mp[s[i]]=i;

     make_tree(,,n);

 }

 void query(int o,int l,int r)

 {

     if(l==r)

     {

         cout<<s[l]<<endl;

         return;

     }

     int mid=(l+r)>>;

     pushdown(o,l,r);

     if(c[lc].s<mid-l+)

         query(left);

     else query(right);

 }

 void doing()

 {

     REP(i,,m)

     {

         int type=a[i].type,l=mp[a[i].l],r=mp[a[i].r]-;

         if(type==)

         {

             updates(l,r,,,,n);

         }

         else if(type==)

         {

             updates(l,r,,,,n);

         }else

         {

             updatex(l,r,,,n);

         }

         query(,,n);

     }

 }

 int main()

 {

     init();

     doing();

     return ;

 }

[Codeforces]817F. MEX Queries 离散化+线段树维护

[Codeforces]817F. MEX Queries

题意

题解

题目细节

代码