noip2019集训测试赛（三）B.mex

本文主要是介绍noip2019集训测试赛（三）B.mex，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给你一个无限长的数组，初始的时候都为0，有3种操作：

操作1是把给定区间[l,r] 设为1，

操作2是把给定区间[l,r] 设为0，

操作3把给定区间[l,r] 0,1反转。

一共n个操作，每次操作后要输出最小位置的0。

---

Input

第一行一个整数n，表示有n个操作

接下来n行，每行3个整数op,l,r表示一个操作

---

Output

共n行，一行一个整数表示答案

---

Solution

考场上写挂了，没判端点重复。。。

其实不难，就一个离散化加线段树维护所有操作的l,r。
输入所有操作再离散化，用l,r建线段树即可。

注意一下将所有右端点r加1，找区间端点时直接用lower_bound查找第一个大于等于r+1的数的上一个数即可。

---

Code

#include<bits/stdc++.h>
#define inf 0x7fffffff
using namespace std;
int minn[800010][2];
int laz[800010];
bool lazr[800010];
void pushdown(int id,int l,int r){int mid=(l+r)>>1;if(laz[id]!=-1){int x=laz[id];minn[id*2][x]=l;minn[id*2+1][x]=mid+1;minn[id*2][x^1]=minn[id*2+1][x^1]=inf;laz[id*2]=laz[id*2+1]=laz[id];lazr[id*2]=lazr[id*2+1]=0;laz[id]=-1;}if(lazr[id]){lazr[id*2]^

这篇关于noip2019集训测试赛（三）B.mex的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---