正題

---

題目大意

無限長的$01$序列，每次進行一個操作

區間內賦值為$0$

區間內賦值為$1$

區間取反

求第一個$0$的位置

---

解題思路

離散化（儲存每個區間的左右端點和他們加一之后的值）后可以用線段樹儲存第一個$0$和第一個$1$的位置。然后區間取反時就交換兩個值并且讓$lazy$標記同樣取反即可

時間復雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=4e5+10; ll n,m,l[N],r[N],op[N],a[N]; ll minw[N*4],minb[N*4],lazy[N*4]; void Downdata(ll x,ll l,ll r,ll op){if(op==3&&lazy[x]){if(lazy[x]==1)lazy[x]=2;else if(lazy[x]==2)lazy[x]=1;else if(lazy[x]==3)lazy[x]=0;}else lazy[x]=op;if(op==1)minw[x]=l,minb[x]=n+1;else if(op==2)minw[x]=n+1,minb[x]=l;else swap(minw[x],minb[x]);return; } void Change(ll x,ll L,ll R,ll l,ll r,ll op){if(L==l&&R==r){Downdata(x,l,r,op);return;}ll mid=(L+R)>>1;if(lazy[x]){Downdata(x*2,L,mid,lazy[x]);Downdata(x*2+1,mid+1,R,lazy[x]);lazy[x]=0;}if(r<=mid)Change(x*2,L,mid,l,r,op);else if(l>mid)Change(x*2+1,mid+1,R,l,r,op);else Change(x*2,L,mid,l,mid,op),Change(x*2+1,mid+1,R,mid+1,r,op);minw[x]=min(minw[x*2],minw[x*2+1]);minb[x]=min(minb[x*2],minb[x*2+1]);return; } int main() {scanf("%lld",&m);for(ll i=1;i<=m;i++){scanf("%lld%lld%lld",&op[i],&l[i],&r[i]);a[++n]=l[i];a[++n]=r[i];a[++n]=l[i]+1;a[++n]=r[i]+1;}a[++n]=1;sort(a+1,a+1+n);n=unique(a+1,a+1+n)-a-1;a[n+1]=a[n]+1;for(ll i=1;i<N*4;i++)minb[i]=minw[i]=n+1;Change(1,1,n,1,n,2);for(ll i=1;i<=m;i++){l[i]=lower_bound(a+1,a+1+n,l[i])-a;r[i]=lower_bound(a+1,a+1+n,r[i])-a;Change(1,1,n,l[i],r[i],op[i]);printf("%lld\n",a[minb[1]]);} }

總結

以上是生活随笔為你收集整理的nssl1476-联【线段树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。