重构了一天的代码,,,
dalao 过来 10min 帮我 A 了 2333 Orz Orz Orz https://www.cnblogs.com/lajioj/
维护 n+1 颗 splay, 分别代表 n 行, 前 1~m-1 个, 最后 1 棵表示最后 1 列
每个节点表示人的编号为 [l,r).(因为有些人一直挨在一起, 所以可以合并)
裂点细节比较多.
还有, 每行只可能插入最后一个位置 (即这一行有人走了, 插入第 m-1 个位置), 所以找对应这棵 splay 最大的位置, 把最后一行对应点弹出, 作为这个最大位置的右儿子即可 (中序遍历它就在最后了).
代码,,, 可读性还算可以吧,,
- #include<bits/stdc++.h>
- #include<cstdio>
- #include<cmath>
- #include<cstring>
- #include<cstdlib>
- #include<algorithm>
- #include<queue>
- #include<deque>
- #include<list>
- #include<set>
- #include<vector>
- #include<iostream>
- #define ll long long
- #define re register
- #define inf 0x7f7f7f7f
- #define inl inline
- #define sqr(x) (x*x)
- //#define eps 1e-8
- #define debug printf("debug\n");
- //#pragma comment(linker, "/STACK:1024000000,1024000000")
- //#pragma GCC optimize (2)
- //#pragma G++ optimize (2)
- using namespace std;
- //const ll mod;
- const ll MAXN=3e5+10;
- inl ll read() {
- re ll x = 0; re int f = 1;
- char ch = getchar();
- while(ch<'0'||ch>'9') { if(ch== '-' ) f = -1; ch = getchar(); }
- while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
- return x * f;
- }
- inl char readc() {
- char ch=getchar();
- while(('z'<ch||ch<'a')&&('Z'<ch||ch<'A')) ch=getchar();
- return ch;
- }
- inl void write(re ll x){
- if(x>=10)write(x/10);
- putchar(x%10+'0');
- }
- inl void writeln(re ll x){
- if(x<0) {x=-x;putchar('-');}
- write(x); puts("");
- }
- inl ll gcd(re ll x,re ll y){while(y^=x^=y^=x%=y);return x;}
- inl ll Lcm(re ll a,re ll b) {return a/gcd(a,b)*b;}
- inl void FR() {
- freopen(".in","r",stdin);
- freopen(".out","w",stdout);
- }
- inl void FC() {
- fclose(stdin);
- fclose(stdout);
- }
- ll Tcnt;
- struct Node {
- ll fa,son[2],l,r,siz;
- }nod[MAXN*10];
- struct Splay {
- ll rt;
- inl ll newnod(ll l,ll r) {
- ++Tcnt;
- nod[Tcnt].fa=nod[Tcnt].son[0]=nod[Tcnt].son[1]=0;
- nod[Tcnt].siz=(nod[Tcnt].r=r)-(nod[Tcnt].l=l);
- return Tcnt;
- }
- inl void init(ll l,ll r) {rt=newnod(l,r);}
- inl void pushup(ll x) {
- nod[x].siz=nod[x].r-nod[x].l+nod[nod[x].son[1]].siz+nod[nod[x].son[0]].siz;
- }
- inl ll dir(ll x) {return nod[nod[x].fa].son[1]==x;}
- inl void rotate(ll x) {
- ll y = nod[x].fa, z = nod[y].fa,o=dir(x);
- nod[x].fa = z;
- if(y==rt) rt=x;
- else nod[z].son[dir(y)] = x;
- if(nod[y].son[o]=nod[x].son[o^1]) nod[nod[y].son[o]].fa=y;
- nod[nod[x].son[o^1]=y].fa=x;
- pushup(y);pushup(x);
- }
- inl void splay(ll x){
- for(ll y;y=nod[x].fa;rotate(x)){
- if(nod[y].fa) rotate(dir(x)==dir(y)?y:x);
- }
- }
- inl ll splitnod(ll x,ll k) {
- k+=nod[x].l;
- ll y=newnod(k,nod[x].r);
- nod[x].r=k;
- if(!nod[x].son[1]) {nod[nod[x].son[1]=y].fa=x;}
- else {
- ll t=nod[x].son[1];
- while(nod[t].son[0]) t=nod[t].son[0];
- nod[nod[t].son[0]=y].fa=t;
- while(t!=x) pushup(t),t=nod[t].fa;
- }
- splay(y);
- return y;
- }
- ll popk(ll k) {
- ll o=rt;
- while(1) {
- if(nod[nod[o].son[0]].siz>=k) {o=nod[o].son[0];}
- else {
- k-=nod[nod[o].son[0]].siz;
- if(k<=nod[o].r-nod[o].l) {
- if(k!=nod[o].r-nod[o].l) splitnod(o,k);
- if(k!=1) o=splitnod(o,k-1);
- break ;
- }
- else {
- k-=nod[o].r-nod[o].l;
- o=nod[o].son[1];
- }
- }
- }
- splay(o);
- nod[nod[o].son[0]].fa=nod[nod[o].son[1]].fa=0;
- if(!nod[o].son[0]) {rt=nod[o].son[1];}
- else {
- ll t=nod[o].son[0];
- while(nod[t].son[1]) t=nod[t].son[1];
- splay(t);
- pushup(rt=nod[nod[t].son[1]=nod[o].son[1]].fa=t);
- }
- return nod[o].l;
- }
- inl void insert(ll x) {
- ll y=newnod(x,x+1);
- if(!rt) rt=y;
- else {
- ll o=rt;
- while(nod[o].son[1]) o=nod[o].son[1];
- splay(o);
- pushup(nod[nod[o].son[1]=y].fa=o);
- }
- }
- }s[MAXN];
- ll n,m,q;
- int main() {
- // FR();
- Tcnt=0;
- n=read(),m=read(),q=read();
- for(re ll i=1;i<=n;i++) s[i].init((i-1)*m+1,i*m);
- s[0].init(m,m+1);
- for(re ll i=2;i<=n;i++) s[0].insert(i*m);
- ll p;
- for(re ll i=1;i<=q;i++) {
- re ll x=read(),y=read();
- s[x].insert(s[0].popk(x));
- writeln(p=s[x].popk(y));
- s[0].insert(p);
- }
- // FC();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2729202.html