[NOIP2017 提高组] 列队

本文主要是介绍[NOIP2017 提高组] 列队，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

个人难度：Medium+/Hard-

题目描述

给你一个矩阵，每次操作删除一个数 $a_{x,y}$，然后第 $x$ 行 $y$ 右边所有数左移一位填补空位，然后第 $m$ 列 $x$ 上边所有数下移一位填补空位，最后把 $a_{x,y}$ 放到 $n$ 行 $m$ 列填补空位。每次操作时求 $a_{x,y}$ 的值。

$n,m,q\le 3\times 10^5$

题解

听说正解是高妙的树状数组，可是我不会QAQ。

发现我们实际上是对每一行和每一列进行两种操作：删除一个数和插入一个数。但是这样空间达到了 $O(nm)$，很完蛋。可是由于操作只有 $3\times 10^5$ 次，所以实际上有一些数从头到尾都会左右挨着，我们初始时就对每一行这样的数合并一下，若是操作要删除这个区间中间的数则把这个区间拆开成两个即可。

顺便还可以发现其实不需要维护每一列，因为每次会移下来填补的只有最后一列，所以我们只需要维护每一行和最后一列即可。

使用Splay，时间复杂度 $O(nlogn)$。

感觉写起来还是挺臭的。

Code

#include<bits/stdc++.h>
#define ls son[p][0]
#define rs son[p][1]
using namespace std;const int N=3e5+5,M=3e6+5;
typedef long long ll;
const ll INF=1e18;int n,m,q,num,fa[M],cnt[M],siz[M],son[M][2];
ll a[M],l[M],r[M];struct treap{int rt;ll tot;bool lr(int p){return son[fa[p]][1]==p;}void pushup(int p){siz[p]=siz[ls]+siz[rs]+cnt[p];}void rorate(int x){bool k=lr(x);int y=fa[x],z=fa[y];son[z][lr(y)]=x;son[y][k]=son[x][!k];fa[son[x][!k]]=y;son[x][!k]=y;fa[y]=x;fa[x]=z;pushup(y),pushup(x);}void splay(int x,int f){while(fa[x]!=f){int y=fa[x],z=fa[y];if(z!=f) rorate(lr(y)==lr(x)?y:x);rorate(x);}if(f==0) rt=x;}void insert(ll x,ll l1,ll r1){if(l1>r1) return;int p=rt,f=0;while(p){f=p;p=(a[p]>x?ls:rs);}p=++num;if(!f) rt=p;a[p]=x;fa[p]=f;son[f][x>a[f]]=p;siz[p]=cnt[p]=r1-l1+1;l[p]=l1,r[p]=r1;splay(p,0);}int find(int x){int p=rt;while(true){if(ls&&x<=siz[ls]) p=ls;else if(rs&&x>siz[ls]+cnt[p]){x-=siz[ls]+cnt[p];p=rs;}else{splay(p,0);return p;}}}int pre(int x){int p=find(x);p=ls;while(rs) p=rs;splay(p,0);return p;}int suc(int x){int p=find(x);p=rs;while(ls) p=ls;splay(p,0);return p;}void del(int x){int pr=pre(x),sc=suc(x);splay(pr,0),splay(sc,pr);int p=sc;ls=0;pushup(sc),pushup(pr); }}t[N],t1;int main(){srand(time(0));scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n;i++){t[i].tot=1ll*n*m;t[i].insert(-INF,0,0);t[i].insert(INF,1ll*n*m+1,1ll*n*m+1);t[i].insert(1ll*(i-1)*m+1,1ll*(i-1)*m+1,1ll*i*m-1);}t1.tot=1ll*n*m;t1.insert(-INF,0,0);t1.insert(INF,1ll*n*m+1,1ll*n*m+1);for(int i=1;i<=n;i++)t1.insert(1ll*i*m,1ll*i*m,1ll*i*m);for(int i=1,x,y;i<=q;i++){scanf("%d%d",&x,&y);if(y==m){ll p=t1.find(x+1),l1=l[p],r1=r[p];printf("%lld\n",l1);t1.insert(++t1.tot,l1,r1);t1.del(x+1);continue;}int p=t[x].find(y+1);ll l1=l[p],r1=r[p],z=y-siz[ls]+l[p];printf("%lld\n",z);t[x].del(y+1);t[x].insert(l1,l1,z-1);t[x].insert(z+1,z+1,r1);t1.insert(++t1.tot,z,z);p=t1.find(x+1);t[x].insert(++t[x].tot,l[p],r[p]);t1.del(x+1);}return 0;
}

这篇关于[NOIP2017 提高组] 列队的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---