【NOIP17 D2T3】列队

Source and Judge

NOIP2017 提高组 D2T3
Loj2319
Luogu3960

Problem

【Description】
Sylvia 是一个热爱学习的女♂孩子。

前段时间,Sylvia 参加了学校的军训。众所周知,军训的时候需要站方阵。

Sylvia 所在的方阵中有n×m名学生,方阵的行数为 n,列数为 m。

为了便于管理,教官在训练开始时,按照从前到后,从左到右的顺序给方阵中 的学生从 1 到 n×m 编上了号码(参见后面的样例)。即:初始时,第 i 行第 j 列 的学生的编号是(i−1)×m+j。

然鹅在练习方阵的时候,经常会有学生因为各种各样的事情需要离队。在一天 中,一共发生了 q件这样的离队事件。每一次离队事件可以用数对(x,y)(1≤x≤n,1≤y≤m)描述,表示第 x 行第 y 列的学生离队。

在有学生离队后,队伍中出现了一个空位。为了队伍的整齐,教官会依次下达 这样的两条指令:

向左看齐。这时第一列保持不动,所有学生向左填补空缺。不难发现在这条 指令之后,空位在第 x 行第 m 列。
向前看齐。这时第一行保持不动,所有学生向前填补空缺。不难发现在这条 指令之后,空位在第 n 行第 m 列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后, 下一个学生才能离队。因此在每一个离队的学生要归队时,队伍中有且仅有第 n 行 第 m 列一个空位,这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊,所以 Sylvia 想要计算每一次离队事件中,离队的同学 的编号是多少。

注意:每一个同学的编号不会随着离队事件的发生而改变,在发生离队事件后 方阵中同学的编号可能是乱序的。
【Input】
输入共 q+1 行。
第 1 行包含 3 个用空格分隔的正整数 n,m,q,表示方阵大小是 n 行 m 列,一共发 生了 q 次事件。
接下来 q 行按照事件发生顺序描述了 q 件事件。每一行是两个整数 x,y,用一个空 格分隔,表示这个离队事件中离队的学生当时排在第 x 行第 y 列。
【Output】
按照事件输入的顺序,每一个事件输出一行一个整数,表示这个离队事件中离队学 生的编号。
【Limited conditions】

数据保证每一个事件满足 1≤x≤n,1≤y≤m
【Sample input】
2 2 3
1 1
2 2
1 2
【Sample output】
1
1
4
【Sample explanation】

列队的过程如上图所示,每一行描述了一个事件。 在第一个事件中,编号为 1 的同学离队,这时空位在第一行第一列。接着所有同学 向左标齐,这时编号为 2 的同学向左移动一步,空位移动到第一行第二列。然后所有同 学向上标齐,这时编号为 4 的同学向上一步,这时空位移动到第二行第二列。最后编号 为 1 的同学返回填补到空位中。

Record

2h

Analysis

请先思考后再展开

如果把每次排队,抽象成操作【删除】和【寻找某一行或者一列的第k个】
那么显然就是要用数据结构维护了
可以说这是一道我见过最不裸的数据结构题
反正我是没有独立看出来的能力的

但这个二维的矩阵要怎么维护呢?
如果说每行都开一个,那么每次向前看起的时候,最后一列向前移动了一位
也就是说我们需要插入、删除n次?显然是不可能的

其实向前的列只有最后一列,所以我们可以把行上的操作类比到最后一列上
也就是说,把最后一列单独维护,前面的n行,每行只维护m-1个元素就好了

接下来把操作具体化一下,设出队的人坐标为(x,y):
①y=m
【把最后一列的第x个删除并获得id】,【将id插入到最后一列的最后】
②y<m
【把第x行的第y个删除并获得id】,【将id插入到最后一列的最后】
【把最后一列的第x个删除并获得id】,【将id插入到第x行的最后】

还有一点就是,由于矩阵很大,不能直接存储,需要用一些手段动态利用空间

基于以上考虑,决定使用的数据结构
思路一:平衡树,我只会splay
思路二:线段树【%rose_max大爷,想到了这么神的做法】

平衡树很好理解,操作很常规,主要是怎么压缩空间
然后我自己想了个做法,结果tm到处都是这样做的……
就是把连续的节点用二元组(st,tot)表示,需要的时候分裂开就好了
找第k大就用siz来找就好了

至于线段树的做法,借鉴主席树的思想,动态开点,只产生链
对于找第k大,还是用siz,但这一次是用【线段树下标差-被删除数量】来搞
然后删除数量,就用一个sum维护即可
因为后面还要插入,所以预先每个线段树开n+q的范围
这样的空间复杂度是nlogn,比splay多个log,但是时间理论上会小常数

不过实际情况是,我写的splay总时间和线段树一样,约10000ms,
但单点最大1500ms,而线段树是1000ms
在极限时间相同的情况下,xgc和rose的线段树总时间只有6000ms
对比了一下,也没发现什么不同……

Code1

请先思考后再展开

splay

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=310000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
struct Nod
{
int f,son[2];
ll siz;
ll id,tot;//起始编号、连续长度
Nod()
{
f=son[0]=son[1]=0;
}
}p[MAXN*(2+4)];
int ln=0;
struct Splay
{
void update(int x)
{
p[x].siz=p[x].tot;
int lc=p[x].son[0],rc=p[x].son[1];
if(lc>0) p[x].siz+=p[lc].siz;//debug tot
if(rc>0) p[x].siz+=p[rc].siz;//debug tot
}
void rotate(int x,int w)
{
int f=p[x].f,ff=p[f].f;
if(p[ff].son[0]==f) p[ff].son[0]=x;
else p[ff].son[1]=x;
p[x].f=ff;
int son=p[x].son[w];
p[f].son[1-w]=son;
if(son>0) p[son].f=f;
p[x].son[w]=f;
p[f].f=x;
update(f);
update(x);
}
int root;
void splay(int x,int rt)
{
while(p[x].f!=rt)
{
int f=p[x].f,ff=p[f].f;
if(ff==rt)
{
if(p[f].son[0]==x) rotate(x,1);
else rotate(x,0);
}
else
{
if(p[ff].son[0]==f and p[f].son[0]==x) rotate(f,1),rotate(x,1);
else if(p[ff].son[0]==f and p[f].son[1]==x) rotate(x,0),rotate(x,1);
else if(p[ff].son[1]==f and p[f].son[0]==x) rotate(x,1),rotate(x,0);
else if(p[ff].son[1]==f and p[f].son[1]==x) rotate(f,0),rotate(x,0);
}
}
if(rt==0) root=x;
}
void add(int fa,int w,ll id,int tot)
{
int now=++ln;
p[now].f=fa;p[fa].son[w]=now;
p[now].id=id;p[now].tot=tot;
update(now);
}
void insert_wei(ll id,ll tot)
{
if(root==0)
{
root=++ln;
p[root].id=id;p[root].tot=tot;
update(root);//debug
}
else
{
int now=root;while(p[now].son[1]>0) now=p[now].son[1];
add(now,1,id,tot);
splay(ln,0);
}
}
int findk(ll &k)//返回编号
{
int now=root;
while(1)
{
int lc=p[now].son[0];
ll lcc=(lc>0)?p[lc].siz:0;
if(k<=lcc) now=lc;
else if(k>lcc+p[now].tot) k-=lcc+p[now].tot,now=p[now].son[1];
else {k-=lcc;return now;}
}
}
void del(int now)
{
splay(now,0);
int lc=p[now].son[0],rc=p[now].son[1];
if(lc==0 and rc==0)
{
//debug ln=0不能用!
root=0;
}
else if(lc>0 and rc==0)
{
root=lc;
p[root].f=0;
}
else if(lc==0 and rc>0)
{
root=rc;
p[root].f=0;
}
else
{
int nx=lc;while(p[nx].son[1]>0) nx=p[nx].son[1];
splay(nx,now);
root=nx;p[root].f=0;
p[rc].f=root;p[root].son[1]=rc;
update(root);
}
}
ll delk_getid(ll k)
{
int now=findk(k);
//printf("%lld %lld\n",p[now].id,k);
k=p[now].id+k-1;
if(p[now].tot==1) del(now);
else if(k==p[now].id)
{
p[now].id++;
p[now].tot--;//debug 漏了这句话,导致推移
splay(now,0);
}
else if(k==p[now].id+p[now].tot-1)
{
p[now].tot--;
splay(now,0);
}
else
{
ll backup=p[now].tot;
p[now].tot=k-1-p[now].id+1;
int rc=p[now].son[1];
p[now].son[1]=0;
add(now,1,k+1,backup-p[now].tot-1);
p[ln].son[1]=rc;p[rc].f=ln;
splay(ln,0);
}
return k;
}
}s[MAXN];
int main()
{
int n,m,q;scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
{
s[i].insert_wei( ll(i-1)*m+1 ,m-1);
s[0].insert_wei( (ll)i*m,1);//最后一列
}
while(q--)
{
int x,y;scanf("%d%d",&x,&y);
if(y==m)
{
ll id=s[0].delk_getid(x);
printf("%lld\n",id);
s[0].insert_wei(id,1);
}
else
{
ll id=s[x].delk_getid(y);
printf("%lld\n",id);
s[0].insert_wei(id,1);
id=s[0].delk_getid(x);
s[x].insert_wei(id,1);
}
}
}

Code2

请先思考后再展开

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=610000;//tot
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
struct Nod
{
int lc,rc;
int sum;//删除数量
ll id;
Nod()
{
lc=rc=sum=0;
id=0;
}
}p[2*MAXN*17];//2*tot+2*tot*log(tot)
int ln=0;
int rt[MAXN],ed[MAXN];
void change(int &now,int l,int r,int pos,int c,ll id)
{
if(now==0) now=++ln;
p[now].sum+=c;
if(l==r) { p[now].id=id;return; }
int mid=(l+r)/2;
if(pos<=mid) change(p[now].lc,l,mid,pos,c,id);
else change(p[now].rc,mid+1,r,pos,c,id);
}
int tmp;//局部编号,外面还原
ll findk(int now,int l,int r,int k,int &pos)//返回编号,pos为下标
{
if(now==0) {tmp=pos=l+k-1;return 0;}
if(l==r) {pos=l;tmp=l+k-1;return p[now].id;}
int mid=(l+r)/2;
int left=mid-l+1-p[p[now].lc].sum;//debug 不能对0节点特判(习惯……)
if(k<=left) return findk(p[now].lc,l,mid,k,pos);
else return findk(p[now].rc,mid+1,r,k-left,pos);
}
int main()
{
int n,m,q;scanf("%d%d%d",&n,&m,&q);
int tot1=m+q,tot2=n+q;//debug 原本用了动态的,然后还忘记分开来
ed[0]=n;for(int i=1;i<=n;i++) ed[i]=m-1;//长度
while(q--)
{
int x,y;scanf("%d%d",&x,&y);
if(y==m)
{
int pos;
ll id=findk(rt[0],1,tot2,x,pos);
change(rt[0],1,tot2,pos,1,0);//delete
if(id==0) id=(ll)tmp*m;
printf("%lld\n",id);
change(rt[0],1,tot2,++ed[0],0,id);
}
else
{
int pos;
ll id=findk(rt[x],1,tot1,y,pos);
change(rt[x],1,tot1,pos,1,0);//delete
if(id==0) id=ll(x-1)*m+tmp;
printf("%lld\n",id);
change(rt[0],1,tot2,++ed[0],0,id);
id=findk(rt[0],1,tot2,x,pos);
change(rt[0],1,tot2,pos,1,0);//delete
if(id==0) id=(ll)tmp*m;
change(rt[x],1,tot1,++ed[x],0,id);
}
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/1613.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%