NOIP2017 day2T3 列队题解

NOIP2017时候的一颗大炸弹。

当时考场上面完全懵逼,用了数组模拟还把n和m写反了只拿了20分。

题目链接:洛谷 P3960 列队

30分做法

开n行的vector,和一个m的vector,维护每一行的数和最后一列,假如移动(x,y),那么找到x行第y个数字,把第x行y的数字直接放在最后一列队尾,再把最后一列第x个数字放在第x行的队尾。注意特判一下最后一行。

开二维数组交换数字移动也是可以的。

难度普及-,纯模拟。

50分做法

观察数据,除了前30分的小数据,还有几个特殊的数据点,对于n=1的特殊数据,我们可以认为矩阵是一个长序列,使用平衡树维护,每次找到对应的人放在队尾。

前30分的数据也可以用平衡树维护,只要n棵维护一下每一列就可以了。

60分做法

询问只有x=1的,不需要记录其他的没用的结点,转换为50分做法来做。

100分做法

由于数据过于肥大,使用朴素的平衡树维护的话,需要n*m个结点,显然是不现实的。

观察一下题目要求,发现最初状态的平衡树,任意第i行的数都是$(i-1)*m+1$到$i*m$的顺序序列,并且发生位移的数字不超过$3*10^5$个,那么我们可以将每一段连续区间作为平衡树的一个结点,需要移动数字时候只要把区间分成三部分,将中间需要移动的数字移动即可。

例如,”1,2,3,4,5,6,7,8,9,10”这个序列我们可以直接存为[1,10],当移动”6”到队尾时,则先吧区间拆成[1,5],[6,6],[7,10]三个结点,然后把[6,6]移动得到[1,5][7,10][6,6]。

平衡树的话用FHQ_Treap来维护。关于FHQ_Treap可以参考我的这篇文章

维护区间的话,每个结点存储l和r的作为区间边界,以往size除了统计结点功能还兼有统计数字的排名功能,但是维护区间的话,size就不再有统计排名功能了,因此需要引入一个len来统计。

还要注意细节,如通过len来寻找包含查找数字的的结点位置,和普通的平衡树有不同之处。

std代码

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
#include<cstdio>

#pragma GCC optimize("O2")
#define FIO

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

using LL=long long;
using ULL=unsigned long long;

const int inf=0x7fffffff;
const LL linf=0x7fffffffffffffff;

class FHQ_Treap
{
private:
inline long random()
{
static int seed=19260817;
return seed=int(seed*48271LL%inf);
}

typedef struct TreapNode
{
LL l,r,len;
int priority,size;
TreapNode *lch,*rch;

inline void update()
{
len=lch->len+rch->len+(r-l+1);
size=lch->size+rch->size+1;
}

TreapNode(LL l,LL r):l(l),r(r){}

~TreapNode()
{
if(lch->priority!=inf)
delete lch;
if(rch->priority!=inf)
delete rch;
}
}*Treap;

Treap root,nil;

inline Treap creat(LL l,LL r)
{
Treap node=new TreapNode(l,r);
node->priority=random();
node->lch=node->rch=nil;
node->update();
return node;
}

Treap merge(Treap x,Treap y)
{
if(x==nil||y==nil)
return x==nil?y:x;
if(x->priority < y->priority)
{
x->rch=merge(x->rch,y);
x->update();
return x;
}
else
{
y->lch=merge(x,y->lch);
y->update();
return y;
}
}

void split(Treap node,int k,Treap &x,Treap &y)
{
if(node==nil)
x=y=nil;
else
{
if(node->lch->size<k)
{
x=node;
split(node->rch,k-node->lch->size-1,node->rch,y);
}
else
{
y=node;
split(node->lch,k,x,node->lch);
}
node->update();
}
}

int ord(Treap node,int k)
{
if(!k)
return 0;
if(node->lch->len<k && k<=node->lch->len+(node->r-node->l+1))
return node->lch->size+1;
if(k<=node->lch->len)
return ord(node->lch,k);
else
return ord(node->rch,k-node->lch->len-(node->r-node->l+1))+node->lch->size+1;
}

public:
FHQ_Treap()
{
nil=new TreapNode(0,0);
nil->lch=nil->rch=nil;
nil->size=0;
nil->len=0;
nil->priority=2147483647;
root=nil;
}

~FHQ_Treap()
{
if(root!=nil)
delete root;
delete nil;
}

void push_back(LL l,LL r=-1)
{
root=merge(root,creat(l,~r?r:l));
}

LL find_pop(int k)
{
Treap x,y,z;
//注意处理区间问题
int t=ord(root,k);//找到包含需要值的区间结点位置
split(root,t-1,x,y);
split(y,1,y,z);//将这个区间单独分裂出来
LL ans=k-x->len-1+y->l;
if(y->len==1)//当区间只有1个元素,删除掉这个区间。
{
delete y;
root=merge(x,z);
}
else//当区间多个元素
{
y->len--;//区间长度减少
if(y->l==ans)//假如需要删除的数位于边界
y->l++;
else if(y->r==ans)
y->r--;
else//待删除的数位于内部,拆分结点为两个不包含删除数的序列,作为当前结点。
{
Treap tmp=y;
y=merge(creat(y->l,ans-1),creat(ans+1,y->r));
delete tmp;
}
root=merge(merge(x,y),z);
}
return ans;
}
}*Que,*Last_line;

int main()
{
#ifdef FIO
freopen("phalanx.in","r",stdin);
freopen("phalanx.out","w",stdout);
#endif
int n,m,Q;
scanf("%d%d%d",&n,&m,&Q);
Que=new FHQ_Treap[n+10],Last_line=new FHQ_Treap;
for(int i=1;i<=n;i++)
{
Que[i].push_back(1ll*(i-1)*m+1,1ll*i*m-1);//放入一个区间
Last_line->push_back(1ll*i*m);
}
while(Q--)
{
int x,y;
LL ans;
scanf("%d%d",&x,&y);
if(y==m)//最后一列,不需要改变前面的各行,要动最后一列。
{
ans=Last_line->find_pop(x);//找到第x个数并扔出序列
Last_line->push_back(ans);//放在序列尾
}
else
{
ans=Que[x].find_pop(y);//找到第x行第y个数扔出序列
LL tmp=Last_line->find_pop(x);//把最后一列第x个数弹出序列
Que[x].push_back(tmp);//放在第x行尾
Last_line->push_back(ans);//把一开始扔出来的数放在最后一列尾
}
printf("%lld\n",ans);
}
delete [] Que;
delete Last_line;
return 0;
}