洛谷P5463 小鱼比可爱(加强版) 题解

时间:2022-07-17 11:49:57

写博客不易,来玩会?

这道题我和dalao们的做法略有不同,我用的是归并排序做法qwq

归并排序求逆序对大家应该很清楚了,我这里就来讲讲如何用归并排序求出这道题的答案

让我们先观察一下规律

举个栗子,若存在一组逆序对a[3],a[4],n = 5,则这组逆序对存在于以下区间内:[ 1 , 4 ] , [ 1 , 5 ] , [ 2 , 4 ] , [ 2 , 5 ] , [ 3 , 4 ] , [ 3 , 5 ],共6个。我们可以画个图帮助理解:

洛谷P5463 小鱼比可爱(加强版) 题解

将其推广,若有逆序对a[ l ] , a[ r ],如图所示:

洛谷P5463 小鱼比可爱(加强版) 题解

则包含其的区间数,即该区间对答案的贡献为(l + 1 - 1) * (n - r + 1 ) = l * (n-r+1)。

然后再用归并排序即可。

注意两个点:

1.本题要用一个类似前缀和的变量来记录所有左半边的位置之和,搜到的时候再从\(sum\)中减去,否则会T(至少我T了)

2.会爆精度。记得开__int 128或者打高精(反正我开的__int 128 qwq)

code:

// Author : Kasugano_Sora
#include<bits/stdc++.h>
using namespace std;
struct item
{
int pl , val;
} a[1100000] , b[1100000];
int n;
__int128 ans;
inline __int128 read()
{
__int128 x = 0 , f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
} inline void print( __int128 x ) //int 128必备操作
{
if(x < 0)
{
putchar('-');
x = -x;
}
if(x > 9)
print(x / 10);
putchar(x % 10 + '0');
}
void msort( int l , int r )
{
if(l == r)
return ;
int mid = (l + r) >> 1;
msort(l , mid);
msort(mid + 1 , r);
long long sum = 0LL; //所谓的前缀
for(int i = l ; i <= mid ; i++ )
{
sum += 1ll * a[i].pl;
}
int i = l , j = mid + 1 , k = l;
while(1) //归并
{
if(i > mid || j > r)
break;
if(a[i].val <= a[j].val)
sum -= 1ll * a[i].pl , b[k++] = a[i++];
else
{
ans += sum * 1ll * (n - a[j].pl + 1);
b[k++] = a[j++];
}
}
if(i > mid) for( ; j <= r ; j++ , k++ )
{
b[k] = a[j];
}
else for( ; i <= mid ; i++ , k++ )
{
b[k] = a[i];
}
for(int i = l ; i <= r ; i++ )
{
a[i] = b[i];
}
return ;
}
int main()
{
// freopen("1.txt" , "r" , stdin);
cin >> n;
for(int i = 1 ; i <= n ; i++ )
{
scanf("%d" , &a[i].val);
a[i].pl = i;
}
msort(1 , n);
print(ans);
return 0;
}

洛谷P5463 小鱼比可爱(加强版) 题解的更多相关文章

  1. Java实现洛谷 P1428 小鱼比可爱

    题目描述 人比人,气死人:鱼比鱼,难死鱼.小鱼最近参加了一个"比可爱"比赛,比的是每只鱼的可爱程度.参赛的鱼被从左到右排成一排,头都朝向左边,然后每只鱼会得到一个整数数值,表示这只 ...

  2. 洛谷 P1428 小鱼比可爱

    题目描述 人比人,气死人:鱼比鱼,难死鱼.小鱼最近参加了一个“比可爱”比赛,比的是每只鱼的可爱程度.参赛的鱼被从左到右排成一排,头都朝向左边,然后每只鱼会得到一个整数数值,表示这只鱼的可爱程度,很显然 ...

  3. 洛谷P1428 小鱼比可爱

    题目描述 人比人,气死人:鱼比鱼,难死鱼.小鱼最近参加了一个"比可爱"比赛,比的是每只鱼的可爱程度.参赛的鱼被从左到右排成一排,头都朝向左边,然后每只鱼会得到一个整数数值,表示这只 ...

  4. 洛谷——P1428 小鱼比可爱

    https://www.luogu.org/problem/show?pid=1428 题目描述 人比人,气死人:鱼比鱼,难死鱼.小鱼最近参加了一个“比可爱”比赛,比的是每只鱼的可爱程度.参赛的鱼被从 ...

  5. 洛谷P1427 小鱼的数字游戏 题解 递归入门题

    题目链接:https://www.luogu.com.cn/problem/P1427 题目大意: 给你一串数(输入到0为止),倒序输出这些数. 解题思路: 首先这道题目可以用数组存数据,然后输出. ...

  6. 洛谷P1854 花店橱窗布置 分析&plus;题解代码

    洛谷P1854 花店橱窗布置 分析+题解代码 蒟蒻的第一道提高+/省选-,纪念一下. 题目描述: 某花店现有F束花,每一束花的品种都不一样,同时至少有同样数量的花瓶,被按顺序摆成一行,花瓶的位置是固定 ...

  7. HAOI2006 (洛谷P2341&rpar;受欢迎的牛 题解

    HAOI2006 (洛谷P2341)受欢迎的牛 题解 题目描述 友情链接原题 每头奶牛都梦想成为牛棚里的明星.被所有奶牛喜欢的奶牛就是一头明星奶牛.所有奶 牛都是自恋狂,每头奶牛总是喜欢自己的.奶牛之 ...

  8. 洛谷P3412 仓鼠找&dollar;Sugar&bsol; II&dollar;题解&lpar;期望&plus;统计论?&rpar;

    洛谷P3412 仓鼠找\(Sugar\ II\)题解(期望+统计论?) 标签:题解 阅读体验:https://zybuluo.com/Junlier/note/1327573 原题链接:洛谷P3412 ...

  9. 洛谷P3502 &lbrack;POI2010&rsqb;CHO-Hamsters感想及题解(图论&plus;字符串&plus;矩阵加速&dollar;dp&bsol;&amp&semi;Floyd&dollar;)

    洛谷P3502 [POI2010]CHO-Hamsters感想及题解(图论+字符串+矩阵加速\(dp\&Floyd\)) 标签:题解 阅读体验:https://zybuluo.com/Junl ...

随机推荐

  1. JavaWeb前端:JQuery

    Jquery基本概念 什么是Jquery Jquery是一个开源的,集成了Javascript,CSS,DOM,AJAX的前端框架:它诞生于2006年,最初是为了简化JavaScript开发而产生的, ...

  2. 在JavaScript里嵌入大量字符串常量的方法

    [转]在JavaScript文件里嵌入大量字符串常量是经常遇到的事.有时为了省事,就把一些界面的HTML和CSS直接写在JS文件里.数量少还好,多的话就密密麻麻的一坨文字,讲究美观的文艺青年们,会用大 ...

  3. mac上安装port

    今天和大家分享下 在mac os x 上安装port 本人在  OS X El Capitan 版本的操作系统上进行安装并测试. --------------------------------- 第 ...

  4. 数据库获取前N条记录SQL Server与SQLite的区别

    在使用sql语句进行前20条记录查询时SQL Server可以这样写: 1: select top 20 * from [table] order by ids desc 2: select top ...

  5. 写给初学者css优先级问题

    首先需要搞清楚几个基本概念 1.内嵌样式: 写在元素标签内的例如:<div style="background-color:red"> </div> 2.内 ...

  6. Python练习册 第 0013 题: 用 Python 写一个爬图片的程序,爬 这个链接里的日本妹子图片 &colon;-&rpar;,&lpar;http&colon;&sol;&sol;tieba&period;baidu&period;com&sol;p&sol;2166231880&rpar;

    这道题是一道爬虫练习题,需要爬链接http://tieba.baidu.com/p/2166231880里的所有妹子图片,点进链接看一下,这位妹子是日本著名性感女演员--杉本由美,^_^好漂亮啊,赶紧 ...

  7. tensorflow-RNN和LSTM

    本章主要介绍循环神经网络(recurrent neuralnetwork,RNN)和长短时记忆网络(long short-term memory,LSTM) 一. RNN简介 1.背景 循环神经网络挖 ...

  8. 数据库设计入门及ERMaster的安装和使用

    数据库的设计步骤 1.标识表  (根据需求创建表) 2.标识表的字段 3.标识表与表之间的关系 注意事项: 三大范式: 1.确保标识的字段的原子性,字段的概念分的不能再分 2.确保字段与表有依赖的关系 ...

  9. Unity编辑器:自定义编辑器样式——GUIStyle

    通过GUIStyle,可以自定义Unity编辑器的样式. GUIStyle可以new一个全新的实例,这样,需要自己处理所有自己需要的效果. GUIStyle还可以基于已经存在的实例new一个新的实例, ...

  10. Activity声明周期1

    oncreate():在Activity对象第一次创建时调用 onStart():当Activity变得可见时调用该函数 onResume():当Activity开始准备于用户交互时调用该方法(即获得 ...