树状数组+概率论,ABC380G - Another Shuffle Window

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解


一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

G - Another Shuffle Window


二、解题报告

1、思路分析

不难用树状数组计算全局逆序对tot

我们可以在滑窗过程中维护当前 k-子数组的逆序对数目cur(不计入滑窗内的数和滑窗外的数字构成的逆序对)

对于滑窗的每个时刻,滑窗外元素对逆序对的贡献为 tot - cur

也就是说,每个滑窗,不带滑窗内会有tot - cur个逆序对

每个滑窗这一部分的贡献为 (tot - cur) * (n - k + 1),因为 n - k + 1个滑窗等概率,所以贡献比例相同,这一部分的答案我们滑窗过程中直接累加

关键在于如何理解滑窗内元素之间的逆序对数目?

我们发现我们只需计算子数组内产生的逆序对,而对于一个数组而言,数组内任意两个数之间构成逆序对的数目为 1 / 2,而 k-数组 pair 的数目为 k * (k - 1) / 2,每个pair 贡献1个逆序对的概率为1/2,根据二项分布的数学期望计算公式:E = np可得,k-数组的逆序对贡献期望为 k * (k - 1) / 4

那么答案就是把两部分加起来,详细看代码

2、复杂度

时间复杂度: O(NlogN)空间复杂度:O(N)

3、代码详解

 ​
#include <bits/stdc++.h>// #define DEBUGusing u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;template<class T>
constexpr T power(T a, i64 b) {T res = 1;for (; b; b /= 2, a *= a) {if (b % 2) {res *= a;}}return res;
}constexpr i64 mul(i64 a, i64 b, i64 p) {i64 res = a * b - i64(1.L * a * b / p) * p;res %= p;if (res < 0) {res += p;}return res;
}
template<i64 P>
struct MLong {i64 x;constexpr MLong() : x{} {}constexpr MLong(i64 x) : x{norm(x % getMod())} {}static i64 Mod;constexpr static i64 getMod() {if (P > 0) {return P;} else {return Mod;}}constexpr static void setMod(i64 Mod_) {Mod = Mod_;}constexpr i64 norm(i64 x) const {if (x < 0) {x += getMod();}if (x >= getMod()) {x -= getMod();}return x;}constexpr i64 val() const {return x;}explicit constexpr operator i64() const {return x;}constexpr MLong operator-() const {MLong res;res.x = norm(getMod() - x);return res;}constexpr MLong inv() const {assert(x != 0);return power(*this, getMod() - 2);}constexpr MLong &operator*=(MLong rhs) & {x = mul(x, rhs.x, getMod());return *this;}constexpr MLong &operator+=(MLong rhs) & {x = norm(x + rhs.x);return *this;}constexpr MLong &operator-=(MLong rhs) & {x = norm(x - rhs.x);return *this;}constexpr MLong &operator/=(MLong rhs) & {return *this *= rhs.inv();}friend constexpr MLong operator*(MLong lhs, MLong rhs) {MLong res = lhs;res *= rhs;return res;}friend constexpr MLong operator+(MLong lhs, MLong rhs) {MLong res = lhs;res += rhs;return res;}friend constexpr MLong operator-(MLong lhs, MLong rhs) {MLong res = lhs;res -= rhs;return res;}friend constexpr MLong operator/(MLong lhs, MLong rhs) {MLong res = lhs;res /= rhs;return res;}friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {i64 v;is >> v;a = MLong(v);return is;}friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {return os << a.val();}friend constexpr bool operator==(MLong lhs, MLong rhs) {return lhs.val() == rhs.val();}friend constexpr bool operator!=(MLong lhs, MLong rhs) {return lhs.val() != rhs.val();}
};template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;template<int P>
struct MInt {int x;constexpr MInt() : x{} {}constexpr MInt(i64 x) : x{norm(x % getMod())} {}static int Mod;constexpr static int getMod() {if (P > 0) {return P;} else {return Mod;}}constexpr static void setMod(int Mod_) {Mod = Mod_;}constexpr int norm(int x) const {if (x < 0) {x += getMod();}if (x >= getMod()) {x -= getMod();}return x;}constexpr int val() const {return x;}explicit constexpr operator int() const {return x;}constexpr MInt operator-() const {MInt res;res.x = norm(getMod() - x);return res;}constexpr MInt inv() const {assert(x != 0);return power(*this, getMod() - 2);}constexpr MInt &operator*=(MInt rhs) & {x = 1LL * x * rhs.x % getMod();return *this;}constexpr MInt &operator+=(MInt rhs) & {x = norm(x + rhs.x);return *this;}constexpr MInt &operator-=(MInt rhs) & {x = norm(x - rhs.x);return *this;}constexpr MInt &operator/=(MInt rhs) & {return *this *= rhs.inv();}friend constexpr MInt operator*(MInt lhs, MInt rhs) {MInt res = lhs;res *= rhs;return res;}friend constexpr MInt operator+(MInt lhs, MInt rhs) {MInt res = lhs;res += rhs;return res;}friend constexpr MInt operator-(MInt lhs, MInt rhs) {MInt res = lhs;res -= rhs;return res;}friend constexpr MInt operator/(MInt lhs, MInt rhs) {MInt res = lhs;res /= rhs;return res;}friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {i64 v;is >> v;a = MInt(v);return is;}friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {return os << a.val();}friend constexpr bool operator==(MInt lhs, MInt rhs) {return lhs.val() == rhs.val();}friend constexpr bool operator!=(MInt lhs, MInt rhs) {return lhs.val() != rhs.val();}
};template<>
int MInt<0>::Mod = 998244353;template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();constexpr int P = 998244353;
using Z = MInt<P>;template<typename T>
class FenWick {
private:int n;std::vector<T> tr;
public:FenWick(int _n) : n(_n), tr(_n + 1) {}FenWick(const std::vector<T> &_init) : FenWick(_init.size()) {init(_init);}void init(const std::vector<T> &_init) {for (int i = 1; i <= n; ++ i) {tr[i] += _init[i - 1];int j = i + (i & -i);if (j <= n)tr[j] += tr[i];}}void add(int x, int k) {for (; x <= n; x += x & -x) tr[x] += k;}void add(int l, int r, T k) {add(l, k);if (r + 1 <= n)add(r + 1, -k);}T query(int x) const {T res = T{};for (; x; x &= x - 1) { res += tr[x];}return res;}T query(int l, int r) const {if (l > r) return T{};return query(r) - query(l - 1);}int select(int k) {int x = 0;T cur{};for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i <= n && cur + tr[x + i] < k) {x += i;cur = cur + tr[x];}}return x + 1;}void clear() {tr.assign(n + 1, T{});}
};void solve() {int n, k;std::cin >> n >> k;std::vector<int> p(n);for (int i = 0; i < n; ++ i) {std::cin >> p[i];}FenWick<Z> fen(n);Z tot = 0;for (int i = n - 1; ~i; -- i) {tot += fen.query(p[i]);fen.add(p[i], 1);}fen.clear();Z cur = 0;for (int i = k - 1; ~i; -- i) {cur += fen.query(p[i]);fen.add(p[i], 1);}Z ans = tot - cur;for (int i = 0; i + k < n; ++ i) {fen.add(p[i], -1);cur -= fen.query(p[i]);cur += fen.query(p[i + k], n);fen.add(p[i + k], 1);ans += tot - cur;}std::cout << (ans * Z(n - k + 1).inv() + Z(4).inv() * Z(k) * Z(k - 1)) << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);#ifdef DEBUGint START = clock();freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint t = 1;// std::cin >> t;while (t --) {solve();}
#ifdef DEBUGstd::cerr << "run-time: " << clock() - START << '\n';
#endifreturn 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/472679.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MySQL:表设计

表的设计 从需求中获得类&#xff0c;类对应到数据库中的实体&#xff0c;实体在数据库中表现为一张一张的表&#xff0c;类中的属性就对应着表中的字段&#xff08;也就是表中的列&#xff09; 表设计的三大范式&#xff1a; 在数据库设计中&#xff0c;三大范式&#xff0…

网盘聚合搜索项目Aipan(爱盼)

本文软件由网友 刘源 推荐&#xff1b; 简介 什么是 Aipan&#xff08;爱盼&#xff09; ? Aipan&#xff08;爱盼&#xff09;是一个基于 Vue 和 Nuxt.js 技术构建的开源网盘搜索项目。其主要目标是为用户提供一个能够自主拥有和管理的网盘搜索网站。该项目持续维护和更新&a…

当微软windows的记事本被AI加持

1985年&#xff0c;微软发布了Windows 1.0&#xff0c;推出了一款革命性的产品&#xff1a;记事本&#xff08;Notepad&#xff09;。这款软件旨在鼓励使用一种未来主义的新设备——鼠标&#xff0c;并让人们可以不依赖VI等键盘工具就能书写文本和编写代码。记事本因其简洁和高…

Dubbo 3.x源码(25)—Dubbo服务引用源码(8)notify订阅服务通知更新

基于Dubbo 3.1&#xff0c;详细介绍了Dubbo服务的发布与引用的源码。 此前我们学习了接口级的服务引入订阅的refreshInterfaceInvoker方法&#xff0c;当时还有最为关键的notify服务通知更新的部分源码没有学习&#xff0c;本次我们来学习notify通知本地服务更新的源码。 Dubb…

自存 关于RestController请求传参数 前端和后端相关

1.Get请求 Get请求传递参数一般是 1.通过PathVariable来映射 URL 绑定的占位符 后端 GetMapping("test/{id}")public R test(PathVariable Integer id){System.out.println(id);return R.success(id);}前端 export function test(id:any){return request({url:&q…

Python练习27

Python日常练习 题目&#xff1a; 编写函数&#xff0c;接收一个正偶数a&#xff0c;任何一个都可以分解成两个 素数之和&#xff0c;如果存在多组符合条件的素数&#xff0c;则全部输出。 例如&#xff1a; 【请输入一个正偶数】50 50 3 47 50 7 43 50 13 37 5…

查询DBA_FREE_SPACE缓慢问题

这个是一个常见的问题&#xff0c;理论上应该也算是一个bug&#xff0c;在oracle10g&#xff0c;到19c&#xff0c;我都曾经遇到过&#xff1b;今天在给两套新建的19C RAC添加监控脚本时&#xff0c;又发现了这个问题&#xff0c;在这里记录一下。 Symptoms 环境&#xff1a;…

已解决:spark代码中sqlContext.createDataframe空指针异常

这段代码是使用local模式运行spark代码。但是在获取了spark.sqlContext之后&#xff0c;用sqlContext将rdd算子转换为Dataframe的时候报错空指针异常 Exception in thread "main" org.apache.spark.sql.AnalysisException: java.lang.RuntimeException: java.lang.Nu…

20.UE5UI预构造,开始菜单,事件分发器

2-22 开始菜单、事件分发器、UI预构造_哔哩哔哩_bilibili 目录 1.UI预构造 2.开始菜单和开始关卡 2.1开始菜单 2.2开始关卡 2.3将开始菜单展示到开始关卡 3.事件分发器 1.UI预构造 如果我们直接再画布上设计我们的按钮&#xff0c;我们需要为每一个按钮进行编辑&#x…

每天五分钟机器学习:支持向量机算法数学基础之核函数

本文重点 从现在开始,我们将开启支持向量机算法的学习,不过在学习支持向量机算法之前,我们先来学习一些支持向量机所依赖的数学知识,这会帮助我们更加深刻的理解支持向量机算法,本文我们先来学习核函数。 定义 核函数(Kernel Function)是一种在支持向量机(SVM)、高…

向潜在安全信息和事件管理 SIEM 提供商提出的六个问题

收集和解读数据洞察以制定可用的解决方案是强大网络安全策略的基础。然而&#xff0c;组织正淹没在数据中&#xff0c;这使得这项任务变得复杂。 传统的安全信息和事件管理 ( SIEM ) 工具是组织尝试使用的一种方法&#xff0c;但由于成本、资源和可扩展性等几个原因&#xff0…

sqli-labs靶场17-20关(每日四关)持续更新!!!

Less-17 打开靶场&#xff0c;发现页面比之前多了一行字 翻译过来就是&#xff0c;密码重置&#xff0c;大家肯定会想到&#xff0c;自己平时在日常生活中怎么密码重置&#xff0c;肯定是输入自己的用户名&#xff0c;输入旧密码&#xff0c;输入新密码就可以了&#xff0c;但…

谷歌AI进军教育,这将改变未来?

近日&#xff0c;谷歌&#xff08;Google&#xff09;正式发布了一款名为“Learn About”的全新人工智能工具&#xff0c;这犹如一颗耀眼的新星&#xff0c;在教育领域掀起了一阵波澜。这款产品具有诸多令人瞩目的亮点&#xff0c;为学习者带来了全新的学习体验。 个性化的学习…

高级计算机算法的8道题(贪心、动态规划)

记录这篇的起因&#xff1a;最近要考试了&#xff0c;我又要考试了&#xff01;&#xff01;&#xff01;是之前上过的一门课&#xff0c;然后这次老师划的重点跟没划无差了。毫无头绪&#xff0c;我就开始翻以前上过这门课的资料。&#xff08;为什么我有点焦虑&#xff0c;是…

Nginx: 实现Websocket代理

概述 Nginx 代理模式中&#xff0c;大多都是基于 HTTP 的 Proxy 模块来对应设置的除此之外&#xff0c;Nginx 还可以实现更多细小化的协议的HTTP代理&#xff0c;比如 ws 的代理 WS 的建立模式 websocket 它其实是建立在HTTP连接上&#xff0c;先要建立起HTTP连接 建立好连接…

TypeORM在Node.js中的高级应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 TypeORM在Node.js中的高级应用 TypeORM在Node.js中的高级应用 TypeORM在Node.js中的高级应用 引言 TypeORM 基本概念 1. 实体&am…

Spring整合Redis

前言 在Spring项目中整合Redis&#xff0c;能显著提升数据缓存、分布式锁、会话管理等操作的效率。Jedis作为轻量级的Java Redis客户端&#xff0c;搭配Spring Data Redis模块&#xff0c;能够简化Redis的连接和数据操作&#xff0c;实现更高性能的读写与灵活的缓存管理。本文…

将已有的MySQL8.0单机架构变成主从复制架构

过程: 把数据库做一个完全备份, 恢复到从节点上, 恢复后从备份的那个点开始往后复制,从而保证后续数据的一致性。 步骤: 修改 master 主节点 的配置&#xff08; server-id log-bin &#xff09;master 主节点 完全备份&#xff08; mysqldump &#xff09;master 主节点 创建…

一文3000字从0到1带你进行Mock测试(建议收藏)

​什么是mock&#xff1f; ​mock测试是以可控的方式模拟真实的对象行为。程序员通常创造模拟对象来测试对象本身该具备的行为&#xff0c;很类似汽车设计者使用碰撞测试假人来模拟车辆碰撞中人的动态行为 为什么要使用Mock&#xff1f; 之所以使用mock测试&#xff0c;是因…

小程序如何完成订阅

小程序如何完成订阅 参考相关文档实践问题处理授权弹窗不再触发引导用户重新授权 参考相关文档 微信小程序实现订阅消息推送的实现步骤 发送订阅消息 小程序订阅消息&#xff08;用户通过弹窗订阅&#xff09;开发指南 实践 我们需要先选这一个模板&#xff0c;具体流程参考…