【题解】Luogu CF817F MEX Queries

原题传送门

817，我突然想到了某8位质数

这题珂以说是珂朵莉树的模板

三个操作都肥肠简单，前两个区间赋值，第三个区间0变1,1变0

每次输出从头开始扫描就行（我忘了珂朵莉树的性质，竟然还动态维护最左边0的位置）

#include  
#define getchar nc
#define ll long long
#define IT set::iterator
using namespace std;
inline char nc(){static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; 
}
inline ll read()
{register ll x=0,f=1;register char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;
}
inline void write(register ll x)
{if(!x)putchar('0');if(x<0)x=-x,putchar('-');static int sta[25];register int tot=0;while(x)sta[tot++]=x%10,x/=10;while(tot)putchar(sta[--tot]+48);
}
inline ll Min(register ll a,register ll b)
{return a s;
ll ans=1;
inline IT split(register ll pos)
{IT it = s.lower_bound(node(pos));if (it != s.end() && it->l == pos) return it;--it;ll L = it->l, R = it->r;bool V = it->v;s.erase(it);s.insert(node(L, pos-1, V));return s.insert(node(pos, R, V)).first;
}
inline void findnext()
{IT it = split(ans);for(;;++it)if(!it->v){ans=it->l;return;}
}
inline void assign_val(register ll l,register ll r,register bool val)
{IT itr = split(r+1),itl = split(l);s.erase(itl, itr);s.insert(node(l, r, val));if(val&&l<=ans&&ans<=r)findnext();else if(!val)ans=Min(ans,l);
}
inline void reverse(register ll l,register ll r)
{IT itr = split(r+1),itl = split(l);bool f=true;if(l<=ans&&ans<=r){for(; itl != itr; ++itl){itl->v^=1;if(f&&!itl->v){f=false;ans=itl->l;}}if(f)findnext();}elsefor(; itl != itr; ++itl){itl->v^=1;if(f&&!itl->v){f=false;ans=Min(ans,itl->l);}}       
}
int main()
{int q=read();s.insert(node(1,1e19,0));while(q--){int opt=read();ll l=read(),r=read();if(opt==1)assign_val(l,r,1);else if(opt==2)assign_val(l,r,0);elsereverse(l,r);write(ans),puts("");}return 0;
}

转载于:https://www.cnblogs.com/yzhang-rp-inf/p/10350935.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！