首页 > 试题广场 >

Rabbit的数列

[编程题]Rabbit的数列

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

Rabbit得到了一个长度为N的数列(数列编号从0到N−1)。数列中每个数val_i满足1<=val_i<=C。
初始时数列中每个数均为1，现在Rabbit要对这个数列进行Q次操作，每次操作给出四个数：X Y A B，首先查询数列中值为X的个数P，然后计算出L，R：
L=(A+(P+B)²)mod N
R=(A+(P∗B)²)mod N
并将范围[min(L,R),max(L,R)]内的所有数改为Y。
最后询问经过Q次操作后数列中出现次数最多的那个数出现了几次。

输入描述:

第一行三个整数N，C，Q。

接下来Q行，每行四个整数X，Y，A，B，表示一个操作。

输出描述:

输出一个整数，表示经过Q次操作后数列中出现次数最多的那个数出现的次数。

示例1

输入

4 2 1
2 2 1 1

输出

备注:

1<=N,C,Q<=10⁵
1<=X,Y<=C，1<=A,B<=10⁸
A,B通过随机产生

算法知识视频讲解

耕云种月

发表于 2022-01-23 21:37:15

原题解链接：https://ac.nowcoder.com/discuss/151166 因为A，BA，BA，B是随机的，所以分块维护一下颜色即可。当然用其他方法也可以，验题人表示还可以用一个set/mapset/mapset/map存下所有的相同的段，每次把[l,r][l,r][l,r]这一段分展开全文