正題

題目鏈接:https://cometoj.com/contest/79/problem/E?problem_id=4207

---

題目大意

$n$個棧，要求支持操作

$l～r$區間內的棧壓入一個數

$l～r$區間內的棧彈出一個數

求第$x$個棧內第$k$個數

---

解題思路

對于每個詢問我們其實就是要求在他之前的第一個位置使得棧內有$t?k$個數的操作。

我們可以倒著跑，維護一個線段樹表示每個詢問的“倒計時”，如果是壓入就對于所有詢問$?1$，彈出就是$+1$，然后每次操作后0的詢問答案就是該次操作。

這里可以先把沒有接觸到的詢問都賦值為$inf$，觸碰到后再修改“倒計時”

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

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define lowbit(x) (x&-x) using namespace std; const ll N=2e5+10,inf=1e9; ll n,q,l[N],r[N],v[N]; ll cnt,p[N],L[N],R[N],ans[N]; ll w[N*4],num[N*4],lazy[N*4]; void Merge(ll x){w[x]=min(w[x*2],w[x*2+1]);if(w[x*2]<w[x*2+1])num[x]=num[x*2];else num[x]=num[x*2+1];return; } void Downdata(ll x){if(!lazy[x])return;w[x*2]+=lazy[x];w[x*2+1]+=lazy[x];lazy[x*2]+=lazy[x];lazy[x*2+1]+=lazy[x];lazy[x]=0;return; } void Build(ll x,ll l,ll r){if(l==r){w[x]=inf;num[x]=l;return;}ll mid=(l+r)>>1;Build(x*2,l,mid);Build(x*2+1,mid+1,r);Merge(x);return; } void Updata(ll x,ll L,ll R,ll pos,ll val){if(L==R)w[x]=val;if(L>=R)return;ll mid=(L+R)>>1;Downdata(x);if(pos<=mid)Updata(x*2,L,mid,pos,val);else if(pos>mid)Updata(x*2+1,mid+1,R,pos,val);Merge(x);return; } void Add(ll x,ll L,ll R,ll l,ll r,ll val){if(L>R||l>r)return;if(L<1||R>cnt)return;if(l<=L&&R<=r){w[x]+=val;lazy[x]+=val;return;}ll mid=(L+R)>>1;Downdata(x);if(r<=mid)Add(x*2,L,mid,l,r,val);else if(l>mid)Add(x*2+1,mid+1,R,l,r,val);else Add(x*2,L,mid,l,r,val),Add(x*2+1,mid+1,R,l,r,val);Merge(x);return; } bool cmp(ll x,ll y) {return (l[x]==l[y])?(x<y):(l[x]<l[y]);} int main() {scanf("%lld%lld",&n,&q);for(ll i=1;i<=q;i++){char op[10];scanf("%s",op);if(op[1]=='u'){scanf("%lld%lld%lld",&l[i],&r[i],&v[i]);}if(op[1]=='o'){scanf("%lld%lld",&l[i],&r[i]);v[i]=-inf;}if(op[1]=='i'){scanf("%lld%lld",&l[i],&r[i]);p[++cnt]=i;}}sort(p+1,p+1+cnt,cmp);for(ll i=0;i<=n+1;i++)L[i]=cnt+1;for(ll i=1;i<=cnt;i++){v[p[i]]=-i;L[l[p[i]]]=min(L[l[p[i]]],i);R[l[p[i]]]=max(R[l[p[i]]],i);}for(ll i=n-1;i>=1;i--)L[i]=min(L[i],L[i+1]);for(ll i=2;i<=n;i++)R[i]=max(R[i],R[i-1]);if(!cnt)return 0;Build(1,1,cnt);for(ll i=q;i>=1;i--){if(v[i]>=0){Add(1,1,cnt,L[l[i]],R[r[i]],-1);while(w[1]<=0){ans[p[num[1]]]=v[i];Updata(1,1,cnt,num[1],inf);}}else if(v[i]<-cnt)Add(1,1,cnt,L[l[i]],R[r[i]],1);else{Updata(1,1,cnt,-v[i],r[i]);}}for(ll i=1;i<=q;i++)if(v[i]>=-cnt&&v[i]<0)printf("%lld\n",ans[i]);return 0; }

總結

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

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