正文
luogu P3960 列队
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
传送门
因为\(Splay\)可以\(O(logn)\)维护区间,所以直接对每一行维护第一个元素到倒数第二个元素的\(Splay\),最后一列维护一个\(Splay\),每次把选出来的点删掉,然后把那一行对应的在最后一列\(Splay\)的点接在这一行后面,然后把选出来的点接在最后一列最后
注意这里要动态开点,即一个点代表一段区间,每次询问再拆开所以我大力分类讨论,写了好长好久qwq
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
using namespace std;
const int N=300000+10;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
LL n,m,q;
int rt[N],tt,fa[N*4],ch[N*4][2],sz[N*4];
LL a[N*4][3];
il void psup(int x)
{
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+a[x][0];
}
il void rot(int x)
{
int y=fa[x],z=fa[y],yy=ch[y][1]==x,w=ch[x][!yy];
ch[z][ch[z][1]==y]=x;fa[x]=z;
ch[y][yy]=w;fa[w]=y;
ch[x][!yy]=y,fa[y]=x;
psup(y),psup(x);
}
il void spl(int x,int en,int id)
{
if(!x) return;
while(fa[x]!=en)
{
int y=fa[x],z=fa[y];
if(z!=en) ((ch[y][1]==x)^(ch[z][1]==y))?rot(x):rot(y);
rot(x);
}
psup(x);
if(!en) rt[id]=x;
}
il int gkth(int x,int id)
{
if(x<=0||x>sz[rt[id]]) return 0;
int nw=rt[id];
while(233)
{
if(x<=sz[ch[nw][0]]) nw=ch[nw][0];
else if(x>sz[ch[nw][0]]+a[nw][0]) x-=sz[ch[nw][0]]+a[nw][0],nw=ch[nw][1];
else return spl(nw,0,id),nw;
}
}
il int bui(int l,int r)
{
if(l>r) return 0;
int mid=(l+r)>>1,nw=++tt;
sz[nw]=1,a[nw][0]=1,a[nw][1]=a[nw][2]=1ll*mid*m;
fa[ch[nw][0]=bui(l,mid-1)]=nw;
fa[ch[nw][1]=bui(mid+1,r)]=nw;
psup(nw);
return nw;
}
int main()
{
n=rd(),m=rd(),q=rd();
rt[0]=bui(1,n);
for(int i=1;i<=n;++i) rt[i]=++tt,a[tt][0]=sz[tt]=m-1,a[tt][1]=1ll*(i-1)*m+1,a[tt][2]=1ll*(i-1)*m+m-1;
while(q--)
{
int x=rd(),y=rd(),u;
if(y<m)
{
u=gkth(y,x);spl(u,0,x);
int len=a[u][0],szz=sz[ch[u][0]];
LL an=a[u][1]+(y-szz-1);
if(y>szz+1&&y<szz+len)
{
++tt,a[tt][0]=1,a[tt][1]=a[tt][2]=an;
a[u][0]=y-szz-1,a[u][2]=an-1,psup(u);
++tt,a[tt][0]=len-a[u][0]-1,a[tt][1]=an+1,a[tt][2]=a[u][1]+len-1;
ch[tt][1]=ch[u][1],fa[tt]=u,fa[ch[u][1]]=tt,ch[u][1]=tt;
psup(tt),psup(u);
int v=gkth(x,0);spl(v,0,0);
int w=gkth(sz[ch[v][0]],0);
if(w)
{
ch[w][1]=ch[v][1],fa[ch[v][1]]=w;
rt[0]=ch[v][0],ch[v][0]=ch[v][1]=fa[ch[v][0]]=0;
spl(w,0,0);
}
else
{
rt[0]=ch[v][1],ch[v][1]=fa[ch[v][1]]=0;
}
int z=gkth(m-2,x);
ch[z][1]=v,fa[v]=z;
spl(v,0,x);
z=gkth(n-1,0);
ch[z][1]=tt-1,fa[tt-1]=z,spl(tt-1,0,0);
}
else if(len==1)
{
int v,w=gkth(sz[ch[u][0]],x);
if(w)
{
ch[w][1]=ch[u][1],fa[ch[u][1]]=w;
rt[x]=ch[u][0],ch[u][0]=ch[u][1]=fa[ch[u][0]]=0;
spl(w,0,x);
}
else
{
rt[x]=ch[u][1],ch[u][1]=fa[ch[u][1]]=0;
}
v=gkth(x,0);spl(v,0,0);
w=gkth(sz[ch[v][0]],0);
if(w)
{
ch[w][1]=ch[v][1],fa[ch[v][1]]=w;
rt[0]=ch[v][0],ch[v][0]=ch[v][1]=fa[ch[v][0]]=0;
spl(w,0,0);
}
else
{
rt[0]=ch[v][1],ch[v][1]=fa[ch[v][1]]=0;
}
int z=gkth(m-2,x);
ch[z][1]=v,fa[v]=z,spl(v,0,x);
z=gkth(n-1,0);
ch[z][1]=u,fa[u]=z,spl(u,0,0);
}
else if(y==szz+len)
{
++tt,a[tt][0]=1,a[tt][1]=a[tt][2]=an;
--a[u][0],--a[u][2],psup(u);
int v=gkth(x,0);spl(v,0,0);
int w=gkth(sz[ch[v][0]],0);
if(w)
{
ch[w][1]=ch[v][1],fa[ch[v][1]]=w;
rt[0]=ch[v][0],ch[v][0]=ch[v][1]=fa[ch[v][0]]=0;
spl(w,0,0);
}
else
{
rt[0]=ch[v][1],ch[v][1]=fa[ch[v][1]]=0;
}
int z=gkth(m-2,x);
ch[z][1]=v,fa[v]=z;
spl(v,0,x);
z=gkth(n-1,0);
ch[z][1]=tt,fa[tt]=z,spl(tt,0,0);
}
else if(y==szz+1)
{
++tt,a[tt][0]=1,a[tt][1]=a[tt][2]=an;
--a[u][0],++a[u][1],psup(u);
int v=gkth(x,0);spl(v,0,0);
int w=gkth(sz[ch[v][0]],0);
if(w)
{
ch[w][1]=ch[v][1],fa[ch[v][1]]=w;
rt[0]=ch[v][0],ch[v][0]=ch[v][1]=fa[ch[v][0]]=0;
spl(w,0,0);
}
else
{
rt[0]=ch[v][1],ch[v][1]=fa[ch[v][1]]=0;
}
int z=gkth(m-2,x);
ch[z][1]=v,fa[v]=z;
spl(v,0,x);
z=gkth(n-1,0);
ch[z][1]=tt,fa[tt]=z,spl(tt,0,0);
}
printf("%lld\n",an);
}
else
{
u=gkth(x,0);
spl(u,0,0);
int v=gkth(sz[ch[u][0]],0);
if(v)
{
ch[v][1]=ch[u][1],fa[ch[u][1]]=v;
rt[0]=ch[v][0],ch[u][0]=ch[u][1]=fa[ch[u][0]]=0;
spl(v,0,0);
}
else
{
rt[0]=ch[u][1],ch[u][1]=fa[ch[u][1]]=0;
}
int z=gkth(n-1,0);
ch[z][1]=u,fa[u]=z,spl(u,0,0);
printf("%lld\n",a[u][1]);
}
}
return 0;
}
其他做法?
咕咕咕
