LostCowsPOJ-2182线段树||树状数组+二分

作者：暖暖252 | 来源：互联网 | 2023-05-18 17:01

传送门：POJ2182题意：给定一个序列每个数的逆序数（第一个逆序数个数默认为零，不给出），求原序列。思路：这题和POJ2828有些相似，如果用线段树做基本一样了，都是维护区间内还有几

传送门：POJ 2182

题意：给定一个序列每个数的逆序数（第一个逆序数个数默认为零，不给出），求原序列。

思路：这题和POJ2828有些相似，如果用线段树做基本一样了，都是维护区间内还有几个空位。

但这个题我是用树状数组+二分做的，这样做的核心思想：序列中第n个数的逆序数应该是其逆序数+1，第n个数确定后，以此类推能确定第n-1个数。。。一直到第一个数。

详见代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define pi acos(-1)
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
typedef pairP;
const int MAXN=10010;
int n; 
int a[MAXN],bit[MAXN],ans[MAXN];//树状数组保存的是哪些数已经出现过了
int sum(int i)
{
	int ans=0;
	while(i>0)
	{
		ans+=bit[i];
		i-=i&-i;
	}
	return ans;
}
void add(int i,int x)
{
	while(i<=n)
	{
		bit[i]+=x;
		i+=i&-i;
	}
}
int binery_search(int k)
{
	int l=0,r=n,mid;
	while(l<=r)
	{
		mid=(l+r)>>1;
		int temp=sum(mid);
		if(mid-1-temp>=k)
		r=mid-1;
		else
		l=mid+1;
	}
	return r+1;
}
int main()
{
	cin>>n;
	for(int i=1;i	{
		cin>>a[i];
	}
	for(int i=n-1;i>=0;i--)
	{
		int id=binery_search(a[i]);
		ans[i]=id;
		add(id,1);
	}
	for(int i=0;i	cout<    return 0;
}

顺便提一句，这题数据很水，纯暴力也能过。

推荐阅读

include
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
include
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
include
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
include
动态规划算法的基本步骤及最长递增子序列问题详解

本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]

蜡笔小新 2023-12-13 15:38:19
include
hdu 5439（找规律）的数列求和问题

本文讨论了一个数列求和问题，该数列按照一定规律生成。通过观察数列的规律，我们可以得出求解该问题的算法。具体算法为计算前n项i*f[i]的和，其中f[i]表示数列中有i个数字。根据参考的思路，我们可以将算法的时间复杂度控制在O(n)，即计算到5e5即可满足1e9的要求。 ... [详细]

蜡笔小新 2023-12-12 14:05:58
php
Java实现大数乘法（分治算法）

本文介绍了使用Java实现大数乘法的分治算法，包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]

蜡笔小新 2023-12-14 15:43:50
php
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
include
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
include
UVALive6575 Odd and Even Zeroes 数位dp+找规律

本文介绍了UVALive6575题目Odd and Even Zeroes的解法，使用了数位dp和找规律的方法。阶乘的定义和性质被介绍，并给出了一些例子。其中，部分阶乘的尾零个数为奇数，部分为偶数。 ... [详细]

蜡笔小新 2023-12-13 14:19:28
hash
[大整数乘法] java代码实现

本文介绍了使用java代码实现大整数乘法的过程，同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率，并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]

蜡笔小新 2023-12-13 11:21:32
include
C++中的三角函数计算及其应用

本文介绍了C++中的三角函数的计算方法和应用，包括计算余弦、正弦、正切值以及反三角函数求对应的弧度制角度的示例代码。代码中使用了C++的数学库和命名空间，通过赋值和输出语句实现了三角函数的计算和结果显示。通过学习本文，读者可以了解到C++中三角函数的基本用法和应用场景。 ... [详细]

蜡笔小新 2023-12-13 10:06:01
include
3.223.28周学习总结中的贪心作业收获及困惑

本文是对3.223.28周学习总结中的贪心作业进行总结，作者在解题过程中参考了他人的代码，但前提是要先理解题目并有解题思路。作者分享了自己在贪心作业中的收获，同时提到了一道让他困惑的题目，即input details部分引发的疑惑。 ... [详细]

蜡笔小新 2023-12-13 03:42:02
include
开发笔记：实验7的文件读写操作

本文介绍了使用C++的ofstream和ifstream类进行文件读写操作的方法，包括创建文件、写入文件和读取文件的过程。同时还介绍了如何判断文件是否成功打开和关闭文件的方法。通过本文的学习，读者可以了解如何在C++中进行文件读写操作。 ... [详细]

蜡笔小新 2023-12-12 17:48:18
include
最长上升子序列问题的变种解法

本文介绍了最长上升子序列问题的一个变种解法，通过记录拐点的位置，将问题拆分为左右两个LIS问题。详细讲解了算法的实现过程，并给出了相应的代码。 ... [详细]

蜡笔小新 2023-12-12 17:41:45
get
java boolean 大小_java boolean 大小

先看官方文档TheJavaTutorialshavebeenwrittenforJDK8.Examplesandpracticesdescribedinthispagedontta ... [详细]

蜡笔小新 2023-12-12 13:36:56

暖暖252

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章