cf817F MEX Queries(离散化+线段树)

817F

题意

给你一些操作

  • 将$[l,r]$内所有不在序列中的数全部加进序列中
  • 将$[l,r]$内所有在序列中的数全部移除
  • 将$[l,r]$内所有不在序列中的数全部加进序列中,并将$[l,r]$内所有在序列中的数全部移除

样例

sample1

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

sample2

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

题解

当时很多人直接写动态开点的线段树然后gg了…

然而其实不需要动态开点,因为操作的总是一个区间所以最终的答案一定是$1$,所有区间的$l$,或者所有区间的$r+1$,考虑直接离散化,对询问到的点返回离散化前的值即可。

线段树的话,维护两个标记:区间异或标记,区间染色标记。优先级:染色大于异或。染色时把异或标记清零,若在下传标记的时候发现既有染色又有异或则说明是先染色后异或,因而先传染色标记,后传异或标记。

复杂度

$\mathcal O(nlogn)$

程序

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100000+5;
int sumv[maxn*100],rev[maxn*100],setv[maxn*100];
int n;
struct query{
int op;
ll l,r;
} q[maxn];
vector<ll> vll;
map<int,ll > rfl;
ll mx=0;
#define lson (o<<1)
#define rson ((o<<1)+1)
void maintain(int o,int l,int r)
{
sumv[o]=sumv[lson]+sumv[rson];
if(setv[o]!=-1) sumv[o]=(r-l+1)*setv[o];
if(rev[o]) sumv[o]=(r-l+1)-sumv[o];
}
void getrev(int o,int l,int r)
{
rev[o]^=1;
maintain(o,l,r);
}
void getset(int o,int l,int r,int st)
{
setv[o]=st;
rev[o]=0;
maintain(o,l,r);
}
void pushdown(int o,int l,int r)
{
if(setv[o]!=-1){
int mid=(l+r)>>1;
getset(lson,l,mid,setv[o]);
getset(rson,mid+1,r,setv[o]);
setv[o]=-1;
}
if(rev[o]){
int mid=((l+r)>>1);
getrev(lson,l,mid);
getrev(rson,mid+1,r);
rev[o]=0;
}
}
void update(int o,int l,int r,int ql,int qr)
{
if(ql>r || qr<l) return;
else{
if(ql<=l && r<=qr) {getrev(o,l,r);return;}
else{
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid) update(lson,l,mid,ql,qr);
if(qr>mid) update(rson,mid+1,r,ql,qr);
maintain(o,l,r);
}
}
}
void Set(int o,int l,int r,int ql,int qr,int st)
{
if(ql>r || qr<l) return;
else{
if(ql<=l && r<=qr) {getset(o,l,r,st);return;}
else{
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid) Set(lson,l,mid,ql,qr,st);
if(qr>mid) Set(rson,mid+1,r,ql,qr,st);
maintain(o,l,r);
}
}
}
bool Full(int o,int l,int r)
{
return sumv[o]==(r-l+1);
}
bool empt(int o,int l,int r)
{
return sumv[o]==0;
}
ll Qmex(int o,int l,int r)
{
if(l==r) return rfl[l];
else{
int mid=(l+r)>>1;
pushdown(o,l,r);
if(Full(lson,l,mid) && Full(rson,mid+1,r)) return rfl[r+1];
else{
if(Full(lson,l,mid)) return Qmex(rson,mid+1,r);
else {
if(l==1 && empt(lson,l,mid)) return 1ll;
else return Qmex(lson,l,mid);
}
}
}
}
void printtree()
{
for(int i=1;i<=2*mx;i++){
printf("sumv[%d]=%d\n",i,sumv[i]);
printf("setv[%d]=%d\n",i,setv[i]);
printf("rev[%d]=%d\n",i,rev[i]);
puts("");
}puts("");
}
int main()
{
scanf("%d",&n);
vll.push_back(1ll);
for(int i=1;i<=n;i++){
scanf("%d%lld%lld",&q[i].op,&q[i].l,&q[i].r);
vll.push_back(q[i].l),vll.push_back(q[i].r);vll.push_back(q[i].r+1);
}
sort(vll.begin(),vll.end());
int sz=unique(vll.begin(),vll.end())-vll.begin();
for(int i=0;i<sz;i++) rfl[i+1]=vll[i];
memset(setv,-1,sizeof(setv));
for(int i=1;i<=n;i++){
q[i].l=lower_bound(vll.begin(),vll.begin()+sz,q[i].l)-vll.begin()+1;
q[i].r=lower_bound(vll.begin(),vll.begin()+sz,q[i].r)-vll.begin()+1;
mx=max(mx,q[i].l);mx=max(mx,q[i].r);
}
for(int i=1;i<=n;i++){
if(q[i].op==1){
Set(1,1,mx,q[i].l,q[i].r,1);
}else if(q[i].op==2){
Set(1,1,mx,q[i].l,q[i].r,0);
}else update(1,1,mx,q[i].l,q[i].r);
printf("%lld\n",Qmex(1,1,mx));
}
return 0;
}