【Codeforces 1000F】One Occurrence

时间:2024-08-18 17:35:26

题意:给一个序列,每次查询某个区间内一个只出现一次的数。

思路:线段树。

首先我们看只出现一次的本质是什么。

如果一个数\(x​\)在\((l,r)​\)中只出现了一次,那么它在其中第一次出现位置为\(p​\),其下一次出现肯定大于\(r​\)。

那么我们就有一个想法:

用线段树维护每一个数的下一次出现,那么区间中最大的一个还没有超过区间的右端点,则说明肯定无解。

但是我们只能够存下这个区间中每个数的第一次出现。

只好离线处理。

把所有的操作按照左端点排序,然后:

从右往左扫描所有的点,遇到一个新的就把当前的值下一次出现记录,同时把下一次出现“删除”。只用把其设成\(-\infty\)即可,因为足以让其不能参加取\(max\)。

这样就好了。

线段树需要单点修改、区间查询。

所以果断\(zkw\)。跑的飞快。

TangentDay:莫队。首先把操作离线,把他们按照左端点排序。维护一个(l,r)表示现在处理到的区间。
然后假设现在我们考虑的区间是(nl,nr),那么我们需要从(l,r)"挪"到(nl,nr):
不断把r右移直到r>=nr,同时把路上的所有数出现次数加1,同时维护所有的现在出现次数为1的数的集合。
不断把l左移直到l<=nl,r左移直到r<=nr,l右移直到l>=nl。
这个顺序是不能改变的。因为如果先左移r或者先右移l可能导致区间长度为负数。
但这个复杂度是O(q sqrt(n) log(n))的,TLE。

ivan100sic:BIT套set。首先把操作离线,把他们按照右端点排序。
维护一个BIT表示每一个后缀出现的数字有哪些是只有一次出现的。
然后就发现我们需要的是区间修改+单点查询。
从左往右扫描右端点,每到一个新的点就把(上一次出现,上上次出现)的那段区间干掉,并且加入(这次出现,上次出现)这个区间。
查询的时候就看左端点上有多少个第一次出现了。
但这个复杂度是O(q log(n)^2)的,TLE。
修改了几次都没有效果。

ei133333:线段树套set。其实和ivan100sic差不多,只是他单点修改,区间查询了。
这样其实想的更自然???可惜还是TLE。

ei133333:线段树。还是离线操作,并且从左往右扫描右端点。
然后每次加入(这次出现,上次出现)这个区间,但不删去(上一次出现,上上次)这段,留着,当查询的时候删。
这里就发现线段树中维护的是一堆(数,出现位置)这个pair,
查询的时候把这个节点的所有pair中出现位置不是最后一次出现位置的干掉。
应该能AC了。复杂度O(q log(n))

natsugiri:线段树。强烈谴责该选手比赛贴板子的恶劣行为,并禁赛三年。(删掉
然后就和上课讲的方法差不多了。

krijgertje:莫队。和TangentDay类似,只不过他用的是链表,消掉了一个log。
然后他的排序方式也不一样:先按照左端点排序,如果左端点是奇数,则右端点按照从小到大排序,否则从大到小。
可惜复杂度O(q sqrt(n)),还是TLE。

krijgertje:线段树。和上课讲的方法一模一样。

总结:出题人很厉害,
O(q sqrt(n))的方法在第8个点TLE了,
O(q log(n)^2)的方法即使过了第8个点还有第9个点,
都安排上了。

但是莫队还是可以过的。

思路2:莫队。

我们在加入、删除一个数的时候这样处理:

我们记录这个数是否只有一次出现,并且记录这个数所在的中有几个只有一次出现的。

块的大小自定。取\(O(\sqrt{n})\)可以达到最好的效果。

那么再看我们怎么找到第一个只有一次出现的数。

首先我们沿着每个块跑,看这个块中有没有。

如果有就进块内跑,找到第一个有的就是辣。

可惜隔壁线段树不知道比它高明到哪里去了,跑的比香港记者还快

但是可以贴着时限过。