Reincarnation

正因为梦易碎，才格外美好。

CF817F MEX Queries

发表于 更新于 分类于
本文字数： 4.7k 阅读时长 ≈ 4 分钟

还不错的题。

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/contest/817/problem/F

形式化题意，维护一个初始为空的正整数集合 ，一共 次操作：

  • 将 中未出现过的数插入 ；
  • 删除 在集合中出现过的数。
  • 删除当前 内出现过的数，然后插入未出现的。

每次操作后求出集合的 。

数据范围：

考虑维护一棵权值线段树表示当前集合维护区间赋值操作（不知道数据强不强，说不定 都能做）。记录区间和，那么每次求 就可以直接实现线段树二分。

对于三个操作，我们转化为：

  • 将区间 赋为 ；
  • 将区间 赋为 ；
  • 对区间 执行区间反转（ 翻转）。

那么直接维护即可。值域较大，考虑离散化，别把 离散化进去就好，判一下边界。时间复杂度 。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
// ----- Eternally question-----
// Problem: F. MEX Queries
// Contest: Codeforces - Educational Codeforces Round 23
// URL: https://codeforces.com/problemset/problem/817/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-09-08 08:12:01
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10,MAXM=1e6+10;
int Q,N;
struct Opera
{
	int opt;
	ll l,r;
}Qr[MAXM];
std::vector<ll>Nums;
#define ls (p<<1)
#define rs (p<<1|1)
struct Segment
{
	int l,r;
	int val,cov,rev;
}Tr[MAXM<<2];
inline void pushUp(int p)
{ Tr[p].val=Tr[ls].val+Tr[rs].val; }
inline void reverse(int p)
{
	Tr[p].val=(Tr[p].r-Tr[p].l+1)-Tr[p].val;
	Tr[p].rev^=1;
}
inline void cover(int p,int c)
{
	Tr[p].val=c*(Tr[p].r-Tr[p].l+1);
	Tr[p].cov=c,Tr[p].rev=0;
}
inline void pushDown(int p)
{
	if(~Tr[p].cov)
	{
		cover(ls,Tr[p].cov),cover(rs,Tr[p].cov);
		Tr[p].cov=-1;
	}
	if(Tr[p].rev)
	{
		reverse(ls),reverse(rs);
		Tr[p].rev=0;
	}
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r,Tr[p].cov=-1;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}
void modifyCov(int p,int l,int r,int c)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return cover(p,c);
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyCov(ls,l,r,c);
	if(mid<r) modifyCov(rs,l,r,c);
	pushUp(p);
}
void modifyRev(int p,int l,int r)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return reverse(p);
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyRev(ls,l,r);
	if(mid<r) modifyRev(rs,l,r);
	pushUp(p);
}
ll queryDiv(int p)
{
	if(Tr[p].l==Tr[p].r) return Nums[Tr[p].l-1];
	pushDown(p);
	// write(Tr[p].l,' ',Tr[p].r,' ',Tr[p].val,'\n');
	if(Tr[ls].val!=Tr[ls].r-Tr[ls].l+1) return queryDiv(ls);
	else return queryDiv(rs);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Q),Nums.push_back(0),Nums.push_back(1);
	for(int i=1;i<=Q;++i)
	{
		read(Qr[i].opt,Qr[i].l,Qr[i].r);
		Nums.push_back(Qr[i].l-1),Nums.push_back(Qr[i].l),Nums.push_back(Qr[i].l+1);
		Nums.push_back(Qr[i].r-1),Nums.push_back(Qr[i].r),Nums.push_back(Qr[i].r+1);
	}
	std::sort(Nums.begin(),Nums.end());
	Nums.erase(std::unique(Nums.begin(),Nums.end()),Nums.end());
	N=Nums.size();
	for(int i=1;i<=Q;++i)
	{
		Qr[i].l=std::lower_bound(Nums.begin(),Nums.end(),Qr[i].l)-Nums.begin()+1;
		Qr[i].r=std::lower_bound(Nums.begin(),Nums.end(),Qr[i].r)-Nums.begin()+1;
	}
	build(1,1,N);
	modifyCov(1,1,1,1);
	for(int i=1;i<=Q;++i)
	{
		auto q=Qr[i];
		if(q.opt==1) modifyCov(1,q.l,q.r,1);
		else if(q.opt==2) modifyCov(1,q.l,q.r,0);
		else modifyRev(1,q.l,q.r);
		write(queryDiv(1),'\n');
		// puts("---");
	}
	return 0;
}
/*

*/
相关文章