Greetings

Problem - 1915F - Codeforces

题意

给一些(l,r)找到所有能够包含(l,r)的数目

引入

也就是找逆序对个数

要用到归并排序中的思想:

//https://www.luogu.com.cn/problem/P1216
#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e18 + 10;
const int N = 2e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k, ans;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
int a[N];
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
int b[N];
void merge(int l,int r)
{
    // 拆分
    if(l == r) return;
    int mid = l + r >> 1;
    merge(l,mid);
    merge(mid+1,r);
    // 合并
    int i = l,j = mid + 1,k = l;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j]) b[k ++] = a[i ++];
        else b[k ++] = a[j ++];
    }
    while(i <= mid) b[k ++] = a[i ++];
    while(j <= r) b[k ++] = a[j ++];
    for(i = l;i <= r;i ++) a[i] = b[i];
}

void gzy()
{
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    merge(1,n);
    for(int i = 1;i <= n;i ++) cout << a[i] << ' ';
    puts("");
}
signed main()
{
    IOS;
    int _ = 1; 
    while (_--) gzy();
    return 0;
}

思路

只需要加一个 sum += mid - i + 1;

code

#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e18 + 10;
const int N = 5e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k, ans;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
int a[N];
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
int b[N];
int sum = 0;
void merge(int l,int r)
{
    // 拆分
    if(l == r) return;
    int mid = l + r >> 1;
    merge(l,mid);
    merge(mid+1,r);
    // 合并
    int i = l,j = mid + 1,k = l;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j])
        {
            b[k ++] = a[i ++];
            
        }
        else 
        {
            sum += mid - i + 1;
            b[k ++] = a[j ++];
        }
    }
    while(i <= mid) b[k ++] = a[i ++];
    while(j <= r) b[k ++] = a[j ++];
    for(i = l;i <= r;i ++) a[i] = b[i];
}

void gzy()
{
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    merge(1,n);
    // for(int i = 1;i <= n;i ++) cout << a[i] << ' ';
    // puts("");
    cout << sum << endl;
}
signed main()
{
    IOS;
    int _ = 1; 
    while (_--) gzy();
    return 0;
}

思路

就是对first排序之后 找到second中的逆序对个数

code

//https://www.luogu.com.cn/problem/P1216
#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>  
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e18 + 10;
const int N = 5e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k, ans;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
PII d[N];
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
int a[N],b[N];
int sum = 0;
void merge(int l,int r)
{
    // 拆分
    if(l == r) return;
    int mid = l + r >> 1;
    merge(l,mid);
    merge(mid+1,r);
    // 合并
    int i = l,j = mid + 1,k = l;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j])
        {
            b[k ++] = a[i ++];   
        }
        else 
        {
            sum += mid - i + 1;
            b[k ++] = a[j ++];
        }
    }
    while(i <= mid) b[k ++] = a[i ++];
    while(j <= r) b[k ++] = a[j ++];
    for(i = l;i <= r;i ++) a[i] = b[i];
}

void gzy()
{
    sum = 0;
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> d[i].first >> d[i].second;
    sort(d+1,d+1+n);
    for(int i = 1;i <= n;i ++) a[i] = d[i].second;
    merge(1,n);
    cout << sum << endl;
}
signed main()
{
    IOS;
    int _ = 1; cin >> _;
    while (_--) gzy();
    return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

centos7修改ssh登录错误限制和端口修改

前几天登录服务器的时候发现有错误登录信息15w多条&#xff0c;该服务器映射了外网&#xff0c;估计是被爆破了。为了防止再有人进行爆破&#xff0c;修改一下ssh的限制登录顺便把默认端口改掉 编辑ssh配置文件 vim /etc/ssh/sshd_config去掉注释 按需修改次数 MaxAuthTries 6…

阿里云数据库RDS PostgreSQL价格227元一年,2核4GB(通用型)

阿里云数据库优惠价格99元1年&#xff0c;配置为云数据库RDS MySQL版基础系列经济版&#xff0c;2核2GB、50GB通用云盘&#xff0c;新老用户均可购买&#xff0c;续费99元1年&#xff0c;云数据库MySQL 2核4GB 100GB 通用云盘优惠价格227元1年&#xff0c;其他云数据库版本如SQ…

ssh连接报错:REMOTE HOST IDENTIFICATION HAS CHANGED问题解决

ssh之前连接没有问题&#xff0c;远程主机发生修改后&#xff0c;重新连接&#xff0c;出现如下报错&#xff1a;WARNING:REMOTE HOST IDENTIFICATION HAS CHANGED! 问题原因&#xff1a; ssh-keygen是用于为SSH创建新的身份验证密钥对的工具。此类密钥对用于自动登录&#xf…

vue methods 函数为啥不能是箭头函数

1、首先&#xff0c;因为methods里面的方法中的this是可以拿到data中定义的属性&#xff0c;所以它肯定不是window,但是methods 中 箭头函数里面的this指向window所以methods里面的方法不能定义箭头函数。 下面用代码说明为啥 methods中箭头函数中的this指向window <div i…

上位机图像处理和嵌入式模块部署(qmacvisual畸变矫正)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 大部分同学在开始做计算机图像的时候&#xff0c;是没有意识到畸变矫正这个问题的。当然不仅仅是畸变矫正&#xff0c;很多同学还会忽略光源的问题…

深入了解 Spring boot的事务管理机制:掌握 Spring 事务的几种传播行为、隔离级别和回滚机制,理解 AOP 在事务管理中的应用

&#x1f389;&#x1f389;欢迎光临&#xff0c;终于等到你啦&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;持续更新的专栏《Spring 狂野之旅&#xff1a;从入门到入魔》 &a…

深圳女游客山顶拍照不慎跌落,幸得及时救助无大碍。

深圳排牙山近日发生了一起惊险的意外事件。一名女游客在龟仙石打卡拍照时&#xff0c;因手滑不慎从石头上跌落&#xff0c;幸运的是&#xff0c;周围的游客迅速反应&#xff0c;合力接住了她&#xff0c;避免了更严重的后果。 据了解&#xff0c;这位女游客在攀爬龟仙石时&…

Dagger2相关知识

目录 一、Dagger简介1.1 什么是Dagger?1.2 Dagger用来干什么&#xff1f;1.3 使用Dagger2注入对象1.4 Dagger注解 二、Dagger2使用2.1 非单例2.2 局部单例2.3 全局单例 三、参考链接 一、Dagger简介 1.1 什么是Dagger? Dagger 2 是一个由 Google 开发的依赖注入框架&#x…

HTML + CSS 核心知识点- 定位

简述&#xff1a; 补充固定定位也会脱离文档流、不会占据原先位置 1、什么是文档流 文档流是指HTML文档中元素排列的规律和顺序。在网页中&#xff0c;元素按照其在HTML文档中出现的顺序依次排列&#xff0c;这种排列方式被称为文档流。文档流决定了元素在页面上的位置和互相之…

【图论】树链剖分

本篇博客参考&#xff1a; 【洛谷日报#17】树链剖分详解Oi Wiki 树链剖分 文章目录 基本概念代码实现常见应用路径维护&#xff1a;求树上两点路径权值和路径维护&#xff1a;改变两点最短路径上的所有点的权值求最近公共祖先 基本概念 首先&#xff0c;树链剖分是什么呢&…

centos7.9的GUI桌面样式不符合默认熟悉的操作习惯

一、问题描述&#xff1a; 原因&#xff1a;桌面样式选错了。 二、解决&#xff1a; 1.先登进去LogOut。 2.点击设置的工具图标中的GNOME Classic即可恢复成默认操作习惯的桌面样式。 3.恢复到默认熟悉的操作界面

基于有限状态机开发健壮的Nodejs/TCP客户端

有限状态机是一种数学计算模型&#xff0c;它描述了在任何给定时间只能处于一种状态的系统的行为。形式上&#xff0c;有限状态机有五个部分&#xff1a; 初始状态值 (initial state)有限的一组状态 (states)有限的一组事件 (events)由事件驱动的一组状态转移关系 (transition…

浏览器如何查看http请求的报文?

HTTP协议用于从WWW服务器传输超文本到本地浏览器的传送协议。 它可以使浏览器更加高效&#xff0c;使网络传输减少。 它不仅保证计算机正确快速地传输超文本文档&#xff0c;还确定传输文档中的哪一部分&#xff0c;以及哪部分内容首先显示 (如文本先于图形)等。所以在node.js里…

viple拓展题

数数问题 题目&#xff1a;使用viple来实现程序&#xff0c;使得运行结果能将数字逐个数出即可 思路&#xff1a;首先&#xff0c;数数字&#xff0c;不知道用户具体要求数到多少结束&#xff0c;所以&#xff0c;可以采用简单的对话活动来实现与用户的交互。其次&#xff0c;…

Linux系统安装1Panel管理面板并实现无公网IP远程管理本地服务器

文章目录 前言1. Linux 安装1Panel2. 安装cpolar内网穿透3. 配置1Panel公网访问地址4. 公网远程访问1Panel管理界面5. 固定1Panel公网地址 前言 1Panel 是一个现代化、开源的 Linux 服务器运维管理面板。高效管理,通过 Web 端轻松管理 Linux 服务器&#xff0c;包括主机监控、…

string类型的使用以及编码方式

Redis 中所有的键的类型都是字符串类型&#xff0c;⼀个字符串的最⼤值不能超过 512 MB。 由于 Redis 内部存储字符串完全是按照⼆进制流的形式保存的&#xff0c;所以 Redis 是不处理字符集编码问题的&#xff0c;客⼾端传⼊的命令中使⽤的是什么字符集编码&#xff0c;就存储…

放在你后口袋里的七种基本质量工具

以下是我反复看到的七种质量改进工具。这些质量工具中的大多数已经存在了一段时间&#xff0c;但这肯定不会降低它们的价值&#xff01; 这些工具最大的优点是使用非常简单&#xff0c;并且可以在中快速使用Minitab统计软件或者从事&#xff0c;但你当然可以使用其他方法&…

【已解决】MySQL:常用的除法运算+精度处理+除数为0处理

目录 问题现象&#xff1a; 问题分析&#xff1a; 拓展&#xff1a; 1、除法运算&#xff1a; 拓展&#xff1a;MySQL中常用的几种除法运算 1、取整除法 2、浮点数除法 3、取余除法 4、向上取整除法 5、向下取整除法 2、运算结果的精度处理 1.1、浮点数 1.2、总位数 1.3、…

c++的const总结(转)

为什么使用const&#xff1f;采用符号常量写出的代码更容易维护&#xff1b;指针常常是边读边移动&#xff0c;而不是边写边移动&#xff1b;许多函数参数是只读不写的。const最常见用途是作为数组的界和switch分情况标号(也可以用枚举符代替)&#xff0c;分类如下&#xff1a;…

什么是网站?为什么要搭建网站?

网站&#xff1a;简单来说&#xff0c;网站就是通过互联网来展示信息的页面集合。它可以在电脑或者手机上打开&#xff0c;提供各种功能&#xff0c;比如查看新闻、购买商品、搜索信息等。 一、建网站的目的&#xff1a;展示个人或企业的存在 网站建设的首要目的之一是展示个人…