[NOIP10.5模拟赛]1.a题解--离散化+异或线段树

题目链接:

咕咕咕

https://www.luogu.org/problemnew/show/CF817F

闲扯

在Yali经历几天折磨后信心摧残,T1数据结构裸题考场上连暴力都TM没打满

分析

观察到点值巨大,离散化即可

但是注意到$1,l+1,r+1$都是会产生答案的,也需要离散化,同时注意数组大小

然后区间异或线段树,为了查询我们记录一个数组$sum0[now]$表示now区间0的个数

同时相应的记录的一个$sum1[now]$表示区间1的个数方便各种操作的转换

下传标记时需要注意的就不多说了,也不用注意挺多,还挺好码的

但是注意数组别开小了!!!我们一条区间最多拓展四个点!

代码

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <iostream>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long 
#define ri register int 
using std::min;
using std::max;
using std::swap;
using namespace __gnu_pbds;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=400005;//数组一定要开大,线段树最多是平常的四倍
const int inf=0x7fffffff;
int L,R,dta;
int pos=-1;
struct Segment_Tree{
    int sum1[maxn<<2],sum0[maxn<<2];
    int tag[maxn<<2],set[maxn<<2];
    inline void pushup(int now){
        sum0[now]=sum0[now<<1]+sum0[now<<1|1];
        sum1[now]=sum1[now<<1]+sum1[now<<1|1];
        return ;
    }
    void build(int now,int l,int r){
        set[now]=-1,tag[now]=0;
        if(l==r){
            sum0[now]=1,sum1[now]=0;
            return ;
        }
        int mid=(l+r)>>1;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
        pushup(now);
    }
    inline void pushdown(int now,int ln,int rn){
        if(tag[now]){
            if(set[now]==-1){
                if(set[now<<1]!=-1)set[now<<1]^=1;
                if(set[now<<1|1]!=-1)set[now<<1|1]^=1;
                //tag[now<<1]^=1,tag[now<<1|1]^=1;
                swap(sum1[now<<1],sum0[now<<1]);
                swap(sum1[now<<1|1],sum0[now<<1|1]);
            }
            tag[now]=0;
        }
        if(set[now]!=-1){
            tag[now<<1]=tag[now<<1|1]=0;
            set[now<<1]=set[now<<1|1]=set[now];
            if(set[now]==1){
                sum1[now<<1]=ln,sum0[now<<1]=0;
                sum1[now<<1|1]=rn,sum0[now<<1|1]=0;
            }
            else{
                sum1[now<<1]=0,sum0[now<<1]=rn;
                sum1[now<<1|1]=0,sum0[now<<1|1]=rn;
            }
            set[now]=-1;
        }
        return ;
    }
    void update_s1(int now,int l,int r){
        if(L<=l&&r<=R){
            set[now]=1;
            tag[now]=0;
            sum0[now]=0,sum1[now]=(r-l+1);
            return ;
        }
        int mid=(l+r)>>1;
        pushdown(now,mid-l+1,r-mid);
        if(L<=mid)update_s1(now<<1,l,mid);
        if(mid<R)update_s1(now<<1|1,mid+1,r);
        pushup(now);
    }
    void update_s0(int now,int l,int r){
        if(L<=l&&r<=R){
            set[now]=0;
            tag[now]=0;
            sum0[now]=(r-l+1),sum1[now]=0;
            return ;
        }
        int mid=(l+r)>>1;
        pushdown(now,mid-l+1,r-mid);
        if(L<=mid)update_s0(now<<1,l,mid);
        if(mid<R)update_s0(now<<1|1,mid+1,r);
        pushup(now);
        return ;
    }
    void update_xor(int now,int l,int r){
        if(L<=l&&r<=R){
            if(set[now]!=-1){
                set[now]^=1;
            }
            else tag[now]^=1;
            swap(sum0[now],sum1[now]);
            return ;
        }
        int mid=(l+r)>>1;
        pushdown(now,mid-l+1,r-mid);
        if(L<=mid)update_xor(now<<1,l,mid);
        if(mid<R)update_xor(now<<1|1,mid+1,r);
        pushup(now);
        return ;
    }
    void query(int now,int l,int r){
        if(sum0[now]==0)return ;
        if(l==r){
            pos=l;
            return ;
        }
        int mid=(l+r)>>1;
        pushdown(now,mid-l+1,r-mid);
        if(sum0[now<<1]!=0)query(now<<1,l,mid);
        if(pos!=-1)return;
        if(sum0[now<<1|1]!=0)query(now<<1|1,mid+1,r);
        pushup(now);
        return ;
    }
}T;
struct OP{
    int ty;ll l,r;
}op[maxn];
int n;
ll f[maxn<<2];int tot=0;
gp_hash_table <ll,int> h;
int main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
    read(n);
	f[++tot]=1;
    for(ri i=1;i<=n;i++){
        read(op[i].ty),read(op[i].l),read(op[i].r);
        f[++tot]=op[i].l,f[++tot]=op[i].r;
		f[++tot]=op[i].l+1;
		f[++tot]=op[i].r+1;
    }
    std::sort(f+1,f+1+tot);
    tot=std::unique(f+1,f+1+tot)-(f+1);
    for(ri i=1;i<=tot;i++){
        h[f[i]]=i;
    }
    T.build(1,1,tot);
	//tot=1000;
    for(ri i=1;i<=n;i++){
        L=h[op[i].l],R=h[op[i].r];
        //L=op[i].l,R=op[i].r;
        //printf("%d %d\n",L,R);
        if(op[i].ty==1){
            T.update_s1(1,1,tot);
        }
        if(op[i].ty==2){
            T.update_s0(1,1,tot);
        }
        if(op[i].ty==3){
            T.update_xor(1,1,tot);
        }
        pos=-1;
        T.query(1,1,tot);
        //printf("--%d--\n",pos);
        printf("%lld\n",f[pos]);
    }
    return 0;
}