首页 > 试题广场 >

小A的排列

[编程题]小A的排列

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

小A有一个长度为n的排列 $p_i$ ，
小A想要知道这个排列中，所有区间的中位数。
不过最近小A沉迷巫师3，到处打牌无法自拔，所以他找到了你，希望你能够解决这个问题。
设区间l,r的中位数为 $mid_{l,r}$
为了方便，只需要你输出 $ans=2×\sum_{l=1}^n \sum_{r=l}^n seed^{(l-1)*n+r} mid_{l,r}$ 。
答案对

取模。
中位数的定义：
对于一个不重集合，将这个集合里的数从小到大排序为 $a_1,a_2,a_3,....,a_m$
当m是奇数，S的中位数为 $a_{(m+1)/2}$
当m是偶数，S的中位数为 $(a_{m/2}+a_{m/2+1})/2$

输入描述:

第一行两个正整数n,seed ,含义如题目所示
第二行一个排列p

输出描述:

一个正整数ans。

示例1

输入

4 1
1 2 3 4

输出

算法知识视频讲解

Muscari

发表于 2020-10-04 17:27:25

一个暴力是枚举左右端点，用 set 求中位数，然而是的。但是我们注意到，在加入一个数后，中位数至多只会移动个位置，即不变或者变成前驱或后继。于是我们需要支持一个插入、求前驱后继的数据结构，发现并找不到。但是我们可以倒过来变成删除，这样子就可以用链表维护了。 // ======== 展开全文

问题信息

思维题

难度：

0条回答 0收藏 9浏览

相关试题

小A的排列

扫描二维码，关注牛客网
意见反馈
下载牛客APP，随时随地刷题

扫一扫，把题目装进口袋

求职之前，先上牛客: 扫描二维码，进入QQ群



扫描二维码，关注牛客公众号

公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
京ICP备14055008号-4 增值电信业务经营许可证营业执照人力资源服务许可证
京公网安备 11010502036488号

小A的排列

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题