列队

发布时间 2023-12-17 12:34:20作者: 最爱丁珰

像这种大题,我们可以先直接按正解想,如果没啥思路,就转而考虑部分分,部分分会给我们提示的

最小的部分分就不说了,纯暴力

看一下\(x_i=1\)的部分分

显然除了第一行,其他都是摆设,所以把第一行和最后一列放在一起考虑

然后就转化为了“谜一样的牛”这一道题目,时间复杂度\(O(nlogn)\)

然后考虑正解

我们刚才是单独考虑了第一行和最后一列,所以正解中也单独考虑最后一列

问题是行怎么办?我们依葫芦画瓢,也单独考虑每一行

稍微模拟一下就知道,对某一行,其他行的操作只会改变这一行最后一位人的编号(从这里也可以看出最后一列是非常特殊的,我们需要单独拿出来考虑),所以我们考虑对同一行一起处理

所以我们离线处理,将询问排序,按照\(x_i\)为第一关键字,询问编号为第二关键字,这样同一行的询问就被放在一起了

我们对同一行的询问建立一个树状数组(具体实现),对每个询问算出其真实想删除的人在数组里面的真实位置(“谜一样的牛”)

然后我们又把询问排序回去,依次考虑每个询问

在处理询问的过程中,我们用\(n\)个vector存储每一行历史上加入进来的人的编号

比如(\(m=4\)

1 2 3 4 7 5 3

表示从最开始到现在,进入过这一行的编号是以上,其中前四个是最开始的四个人(没有用实际的数据结构存储),后面三个是后面加入进来的(在vector当中),而在这个时刻,真实的队列编号可能是

1 2 7 3

或其他一些可能的情况

对当前的这个询问

如果有标记,就在最后一列上进行操作

否则考虑其询问的真实位置\(x\),如果比\(m\)小,那么就可以直接通过计算输出,否则由于没有标记,直接输出vector中第\(x-m\)个数(注意下标从\(0\)开始)

注意维护vector和最后一列即可