线段树|nssl 1476.联线段树|离散化

D e s c r i p t i o n Description Description 有一个初始全是0的01序列 [ 1 , + ∞ ) [1,+\infty ) [1,+∞)，有三种操作

区间赋值为1
区间赋值为0
区间取反

每次操作后，询问最左边的0位于哪个位置
数据范围： n ≤ 1 0 5 n\leq 10^5 n≤105，区间的两端在 l o n gl o n g long\ long long long范围内
S o l u t i o n Solution Solution 线段树水题，离散化后，维护区间和即可，查询就是查询第一个 s u m ≠ i sum\neq i sum?=i的位置
【线段树|nssl 1476.联】时间复杂度： O ( m l o g m ) O(mlogm) O(mlogm)
C o d e Code Code

#include #include #include #include #define LL long long using namespace std; LL m,b[200010]; struct node{int type; LL l,r; }q[200010]; int tot; inline LL read() { char c; LL d=1,f=0; while(c=getchar(),!isdigit(c)) if(c=='-') d=-1; f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } struct xds { #define lson k<<1 #define rson k<<1|1 LL sum[800010],lzy[800010],flg[800010]; xds (){memset(lzy,-1,sizeof(lzy)); } inline void pushdown(int k,int l,int r) { int mid=l+r>>1; if(lzy[k]!=-1) { lzy[rson]=lzy[lson]=lzy[k]; sum[lson]=(mid-l+1)*lzy[k]; sum[rson]=(r-mid)*lzy[k]; flg[lson]=flg[rson]=0; lzy[k]=-1; } if(flg[k]) { flg[lson]^=1; flg[rson]^=1; sum[lson]=(mid-l+1)-sum[lson]; sum[rson]=(r-mid)-sum[rson]; flg[k]=0; } return; } inline void pushup(int k) { sum[k]=sum[lson]+sum[rson]; return; } inline void Modify(int ql,int qr,int v,int k=1,int l=1,int r=tot) { if(ql<=l&&r<=qr) {lzy[k]=v; flg[k]=0; sum[k]=(r-l+1)*v; return; } int mid=l+r>>1; pushdown(k,l,r); if(ql<=mid) Modify(ql,qr,v,lson,l,mid); if(qr>mid) Modify(ql,qr,v,rson,mid+1,r); pushup(k); return; } inline void Fanz(int ql,int qr,int k=1,int l=1,int r=tot) { if(ql<=l&&r<=qr){flg[k]^=1; sum[k]=(r-l+1)-sum[k]; return; } int mid=l+r>>1; pushdown(k,l,r); if(ql<=mid) Fanz(ql,qr,lson,l,mid); if(qr>mid) Fanz(ql,qr,rson,mid+1,r); pushup(k); return; } inline int Ask(int k=1,int l=1,int r=tot) { if(l==r) return l; int mid=l+r>>1; pushdown(k,l,r); if(sum[lson]<(mid-l+1)) return Ask(lson,l,mid); else return Ask(rson,mid+1,r); } #undef lson #undef rson }T; signed main() { m=read(); b[++tot]=1; for(register int i=1; i<=m; i++) q[i].type=read(),q[i].l=read(),q[i].r=read(),b[++tot]=q[i].l,b[++tot]=q[i].r+1; //输入并保存 //存r+1的原因是因为r+1可能作为答案，要放进线段树才行 sort(b+1,b+1+tot); tot=unique(b+1,b+1+tot)-b-1; for(register int i=1; i<=m; i++) { q[i].l=lower_bound(b+1,b+1+tot,q[i].l)-b; q[i].r=lower_bound(b+1,b+1+tot,q[i].r+1)-b-1; //这里记得要减回来 if(q[i].type==1) T.Modify(q[i].l,q[i].r,1); else if(q[i].type==2) T.Modify(q[i].l,q[i].r,0); else T.Fanz(q[i].l,q[i].r); printf("%lld\n",b[T.Ask()]); //查询 } }