这题考场上居然调出来了没炸细节……
第一思路是链表,然而链表上没法二分所以是\(n^2\)的
要不是数据范围很大就可以用线段树了
考虑离散化,但离散化完两个不连续的位置可能会被离散得连续了
所以把每个\(l-1, l, r, r+1\)全扔进去离散化,同时注意把1也扔进去就行了
我打的是全0/1和异或标记,注意这两个标记不共存即可
Code:
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long
#define ld long double
#define usd unsigned
#define ull unsigned long long
#define int long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
char buf[1<<21], *p1=buf, *p2=buf;
inline int read() {
int ans=0, f=1; char c=getchar();
while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
return ans*f;
}
int m;
namespace force{
bool vis[N];
void solve() {
for (int i=1,t,l,r; i<=m; ++i) {
t=read(); l=read(); r=read();
if (t==1) {
for (int j=l; j<=r; ++j) vis[j]=1;
}
else if (t==2) {
for (int j=l; j<=r; ++j) vis[j]=0;
}
else {
for (int j=l; j<=r; ++j) vis[j]^=1;
}
for (int j=1; j<N; ++j) if (!vis[j]) {printf("%lld\n", j); break;}
}
exit(0);
}
}
namespace task1{
int uni[N*10], usize;
int qt[N], ql[N], qr[N];
const int SIZE=(N*8)<<2;
int tl[SIZE], tr[SIZE];
bool tag0[SIZE], tag1[SIZE], tagx[SIZE];
#define tl(p) tl[p]
#define tr(p) tr[p]
#define tag0(p) tag0[p]
#define tag1(p) tag1[p]
#define tagx(p) tagx[p]
void build(int p, int l, int r) {
tl(p)=l; tr(p)=r; tag0(p)=1;
if (l>=r) return ;
int mid=(l+r)>>1;
build(p<<1, l, mid);
build(p<<1|1, mid+1, r);
}
void spread(int p) {
if (tag0(p) || tag1(p)) {
tag0(p<<1)=tag0(p), tag1(p<<1)=tag1(p), tagx(p<<1)=0;
tag0(p<<1|1)=tag0(p), tag1(p<<1|1)=tag1(p), tagx(p<<1|1)=0;
//assert(!tagx(p));
return ;
}
if (!tagx(p)) return ;
//assert(!(tag0(p)&&tag1(p)));
if (tag0(p<<1)||tag1(p<<1)) {swap(tag0(p<<1), tag1(p<<1)); tagx(p<<1)=0;}
else tagx(p<<1)^=1;
if (tag0(p<<1|1)||tag1(p<<1|1)) {swap(tag0(p<<1|1), tag1(p<<1|1)); tagx(p<<1|1)=0;}
else tagx(p<<1|1)^=1;
tagx(p)=0;
}
void upd(int p, int ql, int qr, int dat) {
//cout<<"upd: "<<p<<' '<<tl(p)<<' '<<tr(p)<<' '<<ql<<' '<<qr<<' '<<dat<<endl;
if (ql<=tl(p)&&qr>=tr(p)) {
if (dat==0) {tag0(p)=tag1(p)=tagx(p)=0; tag0(p)=1; return ;}
if (dat==1) {tag0(p)=tag1(p)=tagx(p)=0; tag1(p)=1; return ;}
if (dat==2) {
//cout<<"x1: "<<p<<' '<<tl(p)<<' '<<tr(p)<<' '<<tag0(p)<<' '<<tag1(p)<<' '<<tagx(p)<<endl;
if (tag0(p)||tag1(p)) swap(tag0(p), tag1(p)), tagx(p)=0; //, cout<<"case1"<<endl;
else tagx(p)^=1; //, cout<<"case2"<<endl;
//cout<<"x2: "<<p<<' '<<tl(p)<<' '<<tr(p)<<' '<<tag0(p)<<' '<<tag1(p)<<' '<<tagx(p)<<endl;
return ;
}
}
spread(p);
tag0(p)=tag1(p)=0;
//cout<<"zero "<<p<<endl;
int mid=(tl(p)+tr(p))>>1;
if (ql<=mid) upd(p<<1, ql, qr, dat);
if (qr>mid) upd(p<<1|1, ql, qr, dat);
}
int query(int p) {
//cout<<"query "<<p<<' '<<tl(p)<<' '<<tr(p)<<endl;
if (!p) return -1;
//assert(!(tag0(p)&&tag1(p)));
if (tag0(p)) return tl(p);
if (tag1(p)) return -1;
if (tl(p)==tr(p)) return -1;
spread(p);
int t, ans=-1;
t=query(p<<1);
if (t!=-1) {
if (ans==-1) ans=t;
else ans=min(ans, t);
}
if (ans!=-1) return ans;
t=query(p<<1|1);
if (t!=-1) {
if (ans==-1) ans=t;
else ans=min(ans, t);
}
return ans;
}
void solve() {
//cout<<double(sizeof(tl)*4+sizeof(uni))/1024/1024<<endl;
for (int i=1; i<=m; ++i) {
qt[i]=read(); ql[i]=read(); qr[i]=read();
uni[++usize]=ql[i]; if (ql[i]-1>0) uni[++usize]=ql[i]-1; uni[++usize]=ql[i]+1;
uni[++usize]=qr[i]; if (qr[i]-1>0) uni[++usize]=qr[i]-1; uni[++usize]=qr[i]+1;
}
uni[++usize]=1;
sort(uni+1, uni+usize+1);
usize=unique(uni+1, uni+usize+1)-uni-1;
//cout<<"usize: "<<usize<<endl;
//cout<<"uni: "; for (int i=1; i<=usize; ++i) cout<<uni[i]<<' '; cout<<endl;
build(1, 1, usize+1);
int tsk[]={-1, 1, 0, 2};
for (int i=1,t; i<=m; ++i) {
upd(1, lower_bound(uni+1, uni+usize+1, ql[i])-uni, lower_bound(uni+1, uni+usize+1, qr[i])-uni, tsk[qt[i]]);
//cout<<"upd: "<<lower_bound(uni+1, uni+usize+1, ql[i])-uni<<' '<<lower_bound(uni+1, uni+usize+1, qr[i])-uni<<' '<<tsk[qt[i]]<<endl;
t = query(1);
//cout<<"t: "<<t<<endl;
printf("%lld\n", uni[t]);
}
exit(0);
}
}
signed main()
{
#ifdef DEBUG
freopen("1.in", "r", stdin);
#endif
m=read();
//force::solve();
task1::solve();
return 0;
}