正題

題目鏈接:https://www.luogu.com.cn/problem/P3960

---

題目大意

$n?m$的隊列，起初站在第$(i,j)$位置的人編號是$(i?1)?n+j$。然后每次選擇一個人出隊后所有人向左補齊后所有人向前補齊，然后剛剛出列的那個人入隊。

求每次出列的人的編號。

---

解題思路

我們發現每次要補齊的就是出隊那一行的和最后一列的。

首先考慮如何維護最后一列，我們要求每次刪除一個數并加入一個到隊尾。用權值線段樹可以維護。

然后考慮對于每一行，我們分為兩種情況，一種是本來在隊列里的，一種是新加進來的。新加進來的不難維護，也是每次刪除一個并且加入一個。對于原來就在隊列里的，我們顯然不能開$n?m$的線段樹，正男♂難則反，權值線段樹的權值表示這個范圍內已經出隊了的人數即可。

然后動態開點，時間復雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define p(x,y) (((x)-1)*m+(y)) using namespace std; const ll N=1e6+10; ll n,m,q,tot,rt[N],siz[N],ne[N]; struct Seq_Tree1{ll cnt,w[N<<4],ls[N<<4],rs[N<<4];ll Find(ll &x,ll l,ll r,ll val){if(!x)x=++cnt;if(l==r){w[x]++;return l;}ll mid=(l+r)>>1,ans;if(mid-w[ls[x]]>=val)ans=Find(ls[x],l,mid,val);else ans=Find(rs[x],mid+1,r,val+w[ls[x]]);w[x]=w[ls[x]]+w[rs[x]];return ans;} }T1; struct Seq_Tree2{ll cnt,w[N<<4],ls[N<<4],rs[N<<4],a[N<<4];void Insert(ll &x,ll l,ll r,ll pos,ll val){if(!x)x=++cnt;if(l==r){w[x]++;a[x]=val;return;}ll mid=(l+r)>>1;if(pos<=mid)Insert(ls[x],l,mid,pos,val);else Insert(rs[x],mid+1,r,pos,val);w[x]=w[ls[x]]+w[rs[x]];return;}ll Find(ll &x,ll l,ll r,ll val){if(!x)x=++cnt;if(l==r){w[x]--;return a[x];}ll mid=(l+r)>>1,ans;if(w[ls[x]]>=val)ans=Find(ls[x],l,mid,val);else ans=Find(rs[x],mid+1,r,val-w[ls[x]]);w[x]=w[ls[x]]+w[rs[x]];return ans;} }T2; int main() {//freopen("P3960_7.in","r",stdin);scanf("%lld%lld%lld",&n,&m,&q);tot=n;for(ll i=1;i<=n;i++)T2.Insert(rt[0],1,n+q,i,p(i,m)),siz[i]=m-1;for(ll i=1;i<=q;i++){if(i==469-10)i++,i--;ll x,y;scanf("%lld%lld",&x,&y);if(y==m){ll k=T2.Find(rt[0],1,n+q,x);printf("%lld\n",k);T2.Insert(rt[0],1,n+q,++tot,k);}else if(y<=siz[x]){ll k=T1.Find(rt[x],1,m,y);printf("%lld\n",p(x,k));ll w=T2.Find(rt[0],1,n+q,x);T2.Insert(rt[x+n],1,q,++ne[x],w);T2.Insert(rt[0],1,n+q,++tot,p(x,k));siz[x]--;}else{ll k=T2.Find(rt[x+n],1,q,y-siz[x]);printf("%lld\n",k);ll w=T2.Find(rt[0],1,n+q,x);T2.Insert(rt[x+n],1,q,++ne[x],w);T2.Insert(rt[0],1,n+q,++tot,k);}}return 0; }

總結

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

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