NOIP2017 列队

时间:2023-03-08 17:09:45
NOIP2017 列队

https://www.luogu.org/problemnew/show/P3960

p<=500 50分 模拟

每个人的出队只会影响当前行和最后一列

p<=500,有用的行只有500行

所以只维护这p行和最后一列的信息

然后模拟

时间复杂度:O(p*(n+m))

空间复杂度:O(p*m+n)

#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 501
#define M 50001 typedef long long LL; LL pos[N][M],last[M]; struct node
{
int x,y;
}e[N]; int h[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int main()
{
int n,m,q;
read(n); read(m); read(q);
for(int i=;i<=q;++i)
{
read(e[i].x);
read(e[i].y);
h[i]=e[i].x;
}
sort(h+,h+q+);
int tot=unique(h+,h+q+)-h-;
LL t;
for(int i=;i<=tot;++i)
{
t=(LL)(h[i]-)*m;
for(int j=;j<=m;++j) pos[i][j]=++t;
}
for(int i=;i<=n;++i) last[i]=last[i-]+m;
int nx;
LL ans;
for(int i=;i<=q;++i)
{
nx=lower_bound(h+,h+tot+,e[i].x)-h;
if(e[i].y==m) ans=last[h[nx]];
else ans=pos[nx][e[i].y];
cout<<ans<<'\n';
if(e[i].y!=m)
{
for(int j=e[i].y;j<m-;++j) pos[nx][j]=pos[nx][j+];
pos[nx][m-]=last[h[nx]];
}
for(int j=h[nx];j<n;++j) last[j]=last[j+];
last[n]=ans;
}
}

x=1

x=1,全部的操作只涉及第一行和最后一列

用数据结构分别维护第一行A和最后一列B

每次的出队相当于查询A中的第k个元素

然后B中末尾插入一个数

当A中不足k个元素时,到B中查第k-|A|个元素

30分 线段树

A中以第i个数的值作为下标

B中以第i个数被插入到B中的顺序作为下标,另用a数组存它的值

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm> using namespace std; #define N 300001 typedef long long LL; int n; int sum[N<<]; LL a[N<<];
int sum2[N<<]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void build(int k,int l,int r)
{
sum[k]=r-l+;
if(l==r) return;
int mid=l+r>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
} int query(int k,int l,int r,int pos)
{
if(l==r) return l;
int mid=l+r>>;
if(pos<=sum[k<<]) return query(k<<,l,mid,pos);
return query(k<<|,mid+,r,pos-sum[k<<]);
} void change(int k,int l,int r,int pos)
{
if(l==r)
{
sum[k]=;
return;
}
int mid=l+r>>;
if(pos<=mid) change(k<<,l,mid,pos);
else change(k<<|,mid+,r,pos);
sum[k]=sum[k<<]+sum[k<<|];
} void build2(int k,int l,int r)
{
if(l==r)
{
if(l<=n) sum2[k]=;
return;
}
int mid=l+r>>;
build2(k<<,l,mid);
build2(k<<|,mid+,r);
sum2[k]=sum2[k<<]+sum2[k<<|];
} int query2(int k,int l,int r,int pos)
{
if(l==r) return l;
int mid=l+r>>;
if(pos<=sum2[k<<]) return query2(k<<,l,mid,pos);
return query2(k<<|,mid+,r,pos-sum2[k<<]);
} void change2(int k,int l,int r,int pos,int w)
{
if(l==r)
{
sum2[k]=w;
return;
}
int mid=l+r>>;
if(pos<=mid) change2(k<<,l,mid,pos,w);
else change2(k<<|,mid+,r,pos,w);
sum2[k]=sum2[k<<]+sum2[k<<|];
} int main()
{
int m,q;
read(n); read(m); read(q);
build(,,m-);
int i=; LL j=m;
for(;i<=n;j+=m,++i) a[i]=j;
build2(,,n+q);
int x,y; LL ans;
for(int i=;i<=q;++i)
{
read(x); read(y);
if(y<=sum[])
{
ans=query(,,m-,y);
cout<<ans<<'\n';
change(,,m-,ans);
change2(,,n+q,n+i,);
a[n+i]=ans;
}
else
{
y-=sum[];
y=query2(,,n+q,y);
cout<<a[y]<<'\n';
change2(,,n+q,y,);
change2(,,n+q,n+i,);
a[n+i]=a[y];
}
}
}

30分 树状数组

另一种求解方式,下面100分线段树方法于此类似

两个树状数组,树状数组c1维护第1行,树状数组c2一个维护最后1列

0 1 分别表示这个位置有没有数

这样就可以使用树桩数组查询第k个数

在树状数组内二分即可

用两个vector 记录后添加进树状数组中的数

开始树状数组是满的,即c1有第一行的所有数,c2有最后一列的所有数

(x,y)出队

如果y=m,那么到c2中找第1个元素t

若t<=n 输出m*x,c2的末尾加入t

否则 到对应的vector中找第 t-n-1(下标从0开始)个输出,

输出的值插入到c2的末尾

如果y!=m,到c1中找第y个元素t

若t<=m-1 输出t

否则到对应的vector中找第t-m(下标从0开始)个输出

输出的值插入到c2的末尾

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm> #define N 300001 using namespace std; typedef long long LL; #define lowbit(x) x&-x int n,m,q,mx; int c1[N<<],c2[N<<];
int siz_c1,siz_c2; vector<LL>V[]; int l,r,mid,tmp; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int *c,int x,int w)
{
while(x<=mx)
{
c[x]+=w;
x+=lowbit(x);
}
} int ask(int *c,int x)
{
int sum=;
while(x)
{
sum+=c[x];
x-=lowbit(x);
}
return sum;
} LL work2(int x,LL y)
{
l=; r=mx;
while(l<=r)
{
mid=l+r>>;
if(ask(c2,mid)>=x) tmp=mid,r=mid-;
else l=mid+;
}
add(c2,tmp,-);
LL ans=tmp<=n ? (LL)tmp*m : V[][tmp-n-];
add(c2,++siz_c2,);
V[].push_back(y ? y : ans);
return ans;
} LL work1(int x,int y)
{
l=; r=mx;
while(l<=r)
{
mid=l+r>>;
if(ask(c1,mid)>=y) tmp=mid,r=mid-;
else l=mid+;
}
add(c1,tmp,-);
LL ans=tmp<m ? tmp : V[][tmp-m];
add(c1,++siz_c1,);
V[].push_back(work2(x,ans));
return ans;
} int main()
{
read(n); read(m); read(q);
mx=max(m,n)+q;
for(int i=;i<m;++i) add(c1,i,);
for(int i=;i<=n;++i) add(c2,i,);
siz_c1=m-; siz_c2=n;
int x,y;
for(int i=;i<=q;++i)
{
read(x); read(y);
if(y==m) cout<<work2(x,)<<'\n';
else cout<<work1(x,y)<<'\n';
}
}

30分 splay

第一行splay0,最后一列splay1

裸地splay删除、查询k值、添加

查询(x,y)

如果y==m,splay1中找到第1个,输出,删除,加到最后面

否则,splay0中找到第y个,输出,从splay0中删除,加到splay1中;找到splay1中第1个,删除,加到splay0中

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std; #define N 300001 typedef long long LL; LL a[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} struct SPLAY
{
int root,tot;
int fa[N<<],ch[N<<][];
int siz[N<<];
LL num[N<<]; void build(int l,int r,int f,LL *a)
{
if(l>r) return;
int mid=l+r>>;
fa[mid]=f;
ch[f][mid>f]=mid;
num[mid]=a[mid];
siz[mid]=;
build(l,mid-,mid,a);
build(mid+,r,mid,a);
siz[mid]=siz[ch[mid][]]+siz[ch[mid][]]+;
} void update(int x)
{
siz[x]=;
if(ch[x][]) siz[x]+=siz[ch[x][]];
if(ch[x][]) siz[x]+=siz[ch[x][]];
} bool getson(int x)
{
return ch[fa[x]][]==x;
} void rotate(int x)
{
int y=fa[x],z=fa[y],k=getson(x);
if(y!=root) ch[z][ch[z][]==y]=x;
ch[y][k]=ch[x][k^]; ch[x][k^]=y;
fa[x]=z; fa[y]=x; fa[ch[y][k]]=y;
update(y);
} void splay(int x)
{
for(int f;f=fa[x];rotate(x))
if(fa[f]) rotate(getson(x)==getson(f) ? f : x);
update(x);
root=x;
} void insert_last(LL x)
{
if(!root)
{
root=++tot;
num[tot]=x;
siz[tot]=;
return;
}
int now=root;
while(ch[now][]) now=ch[now][];
ch[now][]=++tot;
fa[tot]=now;
num[tot]=x;
siz[tot]=;
splay(tot);
} int find_kth(int x)
{
int now=root;
while()
{
if(siz[ch[now][]]+==x) return now;
if(ch[now][] && siz[ch[now][]]>=x)
{
now=ch[now][];
continue;
}
x-=siz[ch[now][]]+;
now=ch[now][];
}
} int getpre()
{
int now=ch[root][];
while(ch[now][]) now=ch[now][];
return now;
} void del()
{
if(!ch[root][] && !ch[root][])
{
root=;
return;
}
if(!ch[root][])
{
root=ch[root][];
fa[root]=;
return;
}
if(!ch[root][])
{
root=ch[root][];
fa[root]=;
return;
}
int pre=getpre();
int tmp=root;
splay(pre);
ch[root][]=ch[tmp][];
fa[ch[root][]]=root;
update(root);
} }Splay[]; int main()
{
int n,m,q;
read(n);
read(m);
read(q);
int i; LL j;
for(i=;i<m;++i)
a[i]=i;
Splay[].build(,m-,,a);
Splay[].tot=m-;
Splay[].root=m>>;
for(i=,j=m;i<=n;++i,j+=m)
a[i]=j;
Splay[].build(,n,,a);
Splay[].tot=n;
Splay[].root=n+>>;
int x,y; int id0,id1;
for(i=;i<=q;++i)
{
read(x);
read(y);
if(y==m)
{
id0=Splay[].find_kth();
Splay[].splay(id0);
Splay[].del();
Splay[].insert_last(Splay[].num[id0]);
cout<<Splay[].num[id0];
continue;
}
id0=Splay[].find_kth(y);
Splay[].splay(id0);
Splay[].del();
Splay[].insert_last(Splay[].num[id0]);
id1=Splay[].find_kth(x);
Splay[].splay(id1);
Splay[].del();
Splay[].insert_last(Splay[].num[id1]);
cout<<Splay[].num[id0]<<'\n';
}
}

满分做法

与x=1的做法类似

我们只需要用n个数据结构Ai维护每一行的前m-1个

再用一个数据结构B维护最后一列即可

注意所选数据结构的空间问题

每一次查询(x,y)

如果y不是最后一列,就从Ax中找到第y个元素,记为ans,输出ans,Ax中删去ans,

把B中的第x个元素插到Ax的最后面,把ans插到B的最后面

如果y是最后一列,在B中找到第y个元素,记为ans,输出ans,B中删去ans

把ans插入到B的最后一个

100分 线段树

对于每一行维护一个线段树

显然不能提前都开满,所以动态开节点

线段树区间维护的大小固定,所以动态删除和动态添加不是很方便

所以不直接执行删除操作,不在线段树上添加

开始我们默认维护前n行m-1列的线段树中所有节点都是满的

维护最后一列的线段树也是满的

删除操作:

用sum[k]记录下k包含的这段区间删除的数的个数

这样查询时,当前区间数的个数 为区间大小-sum[k]

如果要查的数<=区间大小-sum[k] 到左孩子查

否则,查的数减去 区间大小-sum[k] ,到右孩子查

添加操作:

令开n+1个vector,存储动态添加到对应线段树里的数

查询操作:

如果y=m,

假设维护最后一列的线段树是第n+1颗

查询第n+1颗线段树里第x个值pos

若pos<=n,输出 pos*m,

否则输出第n+1个vector里第pos-n-1(下标从0开始)个元素

输出的值插入到最后一列的线段树的末尾

如果y!=m

到第x颗线段树里查询第y个数pos

若pos<=m-1,输出(x-1)*m+pos,

否则输出第x个vector里 第pos-m(下标从0开始)个元素

输出的值插入到最后一列线段树的末尾

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm> using namespace std; #define N 300001 typedef long long LL; int n,m,q,mx; int tot;
int root[N+],lc[N*],rc[N*];
int sum[N*]; int pos; vector<LL>V[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int query(int k,int l,int r,int w)
{
if(l==r) return l;
int mid=l+r>>,tmp=mid-l+-sum[lc[k]];
if(w<=tmp) return query(lc[k],l,mid,w);
return query(rc[k],mid+,r,w-tmp);
} void change(int &k,int l,int r)
{
if(!k) k=++tot;
sum[k]++;
if(l==r) return;
int mid=l+r>>;
if(pos<=mid) change(lc[k],l,mid);
else change(rc[k],mid+,r);
} LL work0(int x,LL y)
{
pos=query(root[n+],,mx,x);
change(root[n+],,mx);
LL ans=pos<=n ? (LL)pos*m : V[n+][pos-n-];
V[n+].push_back(y ? y : ans);
return ans;
} LL work1(int x,int y)
{
pos=query(root[x],,mx,y);
change(root[x],,mx);
LL ans=pos<m ? (LL)(x-)*m+pos : V[x][pos-m];
V[x].push_back(work0(x,ans));
return ans;
} int main()
{
read(n); read(m); read(q);
mx=max(n,m)+q;
int x,y;
while(q--)
{
read(x); read(y);
if(y==m) cout<<work0(x,)<<'\n';
else cout<<work1(x,y)<<'\n';
}
}

100分 树状数组

树状数组不能动态开节点

30分树状数组做法中,树状数组的作用是查询k值

在这里我们仍然只用树状数组查询k值

我们不存储没有离队过的元素,因为知道了它一开始在第i行第j列后就可以得出它的编号是(i-1)*m+j

而会离队的元素至多只有q个

所以对于每一行的前m-1列和最后一列都开一个vector Ai,B,记录本行或最后一列补进来的编号

每次询问的(x,y)是第j个出现在第x行的数只与 这次询问之前对第x行进行的询问有关

默认原来队列中的数是第1到m个出现在本行的数

那就可以读入所有数据,离线处理

若我们能够处理出每一个查询(x,y)应该是第几个出现在第x行的数,记为pre[i]

然后按输入顺序枚举每一个询问(x,y)

若y!=m,2个操作:

1、第x行第pre[i]个数出队,到最后一列的最后一个位置,即vector B中加入第x行第pre[i]个数

2、第x行最后补上最后一列的第x个数,即vector Ax 中加入 最后一列的第x个数

若y==m,

最后一列的第x个数出队,到最后一列末尾,vector B中加入最后一列第x个数

如何得到 最后一列的第x个数?

树状数组维护最后一列,每查询一次(x,y),标记一次x

对于树状数组中查到的第x个数h,意为是第h个出现在最后一列的数

若h<=n,则为h*m

若h>m,那就是vector B 中第h-n-1(下标从0开始)个元素

如何得到第x行第pre[i]个出现的数?

若pre[i]<m,就是(x-1)*m+pre[i]

若pre[i]>=m,就是vector Ax 中 第pre[i]-m(下标从0开始)个出现的数

如何得到第i个询问(x,y)的pre[i]?

枚举每一行,

在树状数组中二分出第y个数在哪个位置

处理一个,树状数组中删一个

处理完一行之后,再把之前删的都加回来供下一行使用

这样我们就得到了每一个查询(x,y)应该是第几个出现在第x行的数

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm> using namespace std; #define N 300001 typedef long long LL; #define lowbit(x) x&-x int mx;
int n,m,q; struct node
{
int pos,id; node(int pos_=,int id_=) : pos(pos_),id(id_) { } };
vector<node>V[N];
vector<LL>num[N]; int c[N<<]; int qx[N],qy[N]; int pre[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int x,int w)
{
while(x<=mx)
{
c[x]+=w;
x+=lowbit(x);
}
} int ask(int x)
{
int sum=;
while(x)
{
sum+=c[x];
x-=lowbit(x);
}
return sum;
} int query_kth(int k)
{
int l=,r=mx;
int mid,tmp;
while(l<=r)
{
mid=l+r>>;
if(ask(mid)>=k) tmp=mid,r=mid-;
else l=mid+;
}
return tmp;
} void init()
{
read(n); read(m); read(q);
mx=max(n,m)+q;
for(int i=;i<=q;++i)
{
read(qx[i]); read(qy[i]);
if(qy[i]!=m) V[qx[i]].push_back(node(qy[i],i));
}
} void solve1()
{
for(int i=;i<=mx;++i) add(i,);
int siz;
node now;
for(int i=;i<=n;++i)
{
siz=V[i].size();
for(int j=;j<siz;++j)
{
now=V[i][j];
pre[now.id]=query_kth(now.pos);
add(pre[now.id],-);
}
for(int j=;j<siz;++j) add(pre[V[i][j].id],);
}
} void solve2()
{
LL ans; int h;
for(int i=;i<=q;++i)
{
h=query_kth(qx[i]);
ans= h<=n ? (LL)h*m : num[][h-n-];
add(h,-);
if(qy[i]!=m)
{
num[qx[i]].push_back(ans);
ans= pre[i]<m ? LL(qx[i]-)*m+pre[i] : num[qx[i]][pre[i]-m];
}
num[].push_back(ans);
cout<<ans<<'\n';
}
} int main()
{
init();
solve1();
solve2();
}

100分 splay

没有用到的区间都压缩成一个大节点

每一行一个splay,最后一列一个splay

刚开始每一行的前m-1列都压缩成一个点

最后一列的splay把元素填进去

与30分不同的是查询的时候需要分裂节点

#include<cstdio>
#include<iostream> using namespace std; #define N 300001 typedef long long LL; int tot; int root[N];
int l[N*],r[N*]; int ch[N*][],fa[N*],siz[N*],key[N*];
LL num[N*]; int rt; LL a[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void build(int l,int r,int f)
{
if(l>r) return;
int mid=l+r>>;
fa[mid]=f;
ch[f][mid>f]=mid;
key[mid]=siz[mid]=;
num[mid]=a[mid];
build(l,mid-,mid);
build(mid+,r,mid);
siz[mid]=siz[ch[mid][]]+siz[ch[mid][]]+;
} bool getson(int x)
{
return ch[fa[x]][]==x;
} void update(int x)
{
siz[x]=siz[ch[x][]]+siz[ch[x][]]+key[x];
} void rotate(int x,int &goal)
{
int y=fa[x],z=fa[y];
bool k=getson(x);
if(y!=goal) ch[z][ch[z][]==y]=x;
else goal=x;
ch[y][k]=ch[x][k^];
ch[x][k^]=y;
fa[x]=z; fa[y]=x; fa[ch[y][k]]=y;
update(y);
} void splay(int x,int &goal)
{
int y;
while(x!=goal)
{
y=fa[x];
if(y!=goal) rotate(getson(x)==getson(y) ? y : x,goal);
rotate(x,goal);
}
update(x);
} void split(int now,int k,int id)
{
if(k<=siz[ch[now][]]) split(ch[now][],k,id);
else if(k>siz[ch[now][]]+key[now]) split(ch[now][],k-siz[ch[now][]]-key[now],id);
else
{
k-=siz[ch[now][]];
if(k!=)
{
fa[ch[++tot][]=ch[now][]]=tot;
fa[ch[now][]=tot]=now;
key[tot]=k-;
key[now]-=k-;
l[tot]=l[now];
r[tot]=l[now]+key[tot]-;
l[now]=r[tot]+;
update(tot);
}
if(key[now]!=)
{
fa[ch[++tot][]=ch[now][]]=tot;
fa[ch[now][]=tot]=now;
key[tot]=key[now]-;
key[now]=;
l[tot]=l[now]+;
r[tot]=r[now];
r[now]=l[now];
update(tot);
}
splay(now,root[id]);
}
} void insert_last(int &rt,LL x)
{
if(!rt)
{
rt=++tot;
l[tot]=r[tot]=key[tot]=siz[tot]=;
num[tot]=x;
return;
}
int now=rt;
while(ch[now][]) now=ch[now][];
fa[++tot]=now;
ch[now][]=tot;
l[tot]=r[tot]=key[tot]=siz[tot]=;
num[tot]=x;
splay(tot,rt);
} int find_kth(int now,int x)
{
while()
{
if(x<=siz[ch[now][]])
{
now=ch[now][];
continue;
}
x-=siz[ch[now][]];
if(x==) return now;
x--;
now=ch[now][];
}
} int find_pre(int rt)
{
int now=ch[rt][];
while(ch[now][]) now=ch[now][];
return now;
} void del(int &rt)
{
if(!ch[rt][] && !ch[rt][])
{
rt=;
return;
}
if(!ch[rt][])
{
rt=ch[rt][];
return;
}
if(!ch[rt][])
{
rt=ch[rt][];
return;
}
int pre=find_pre(rt);
int tmp=rt;
splay(pre,rt);
ch[rt][]=ch[tmp][];
fa[ch[rt][]]=rt;
update(rt);
} int main()
{
int n,m,q;
read(n); read(m); read(q);
int i; LL j;
for(i=,j=m;i<=n;++i,j+=m) a[i]=j;
build(,n,);
tot=n;
root[]=n+>>;
for(int i=;i<=n;++i)
{
root[i]=++tot;
siz[tot]=m-;
key[tot]=m-;
l[tot]=; r[tot]=m-;
}
int x,y;
LL ans;
int tmp;
while(q--)
{
read(x); read(y);
tmp=find_kth(root[],x);
splay(tmp,root[]);
del(root[]);
if(y!=m)
{
split(root[x],y,x);
ans=num[root[x]] ? num[root[x]] : (LL)(x-)*m+l[root[x]];
del(root[x]);
insert_last(root[],ans);
insert_last(root[x],num[tmp]);
}
else
{
ans=num[tmp];
insert_last(root[],ans);
}
cout<<ans<<'\n';
}
}