Acwing241. 楼兰图腾

这篇具有很好参考价值的文章主要介绍了Acwing241. 楼兰图腾。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

在完成了分配任务之后,西部 314 来到了楼兰古城的西部。

相传很久以前这片土地上(比楼兰古城还早)生活着两个部落,一个部落崇拜尖刀(V),一个部落崇拜铁锹(),他们分别用 V 和  的形状来代表各自部落的图腾。

西部 314314 在楼兰古城的下面发现了一幅巨大的壁画,壁画上被标记出了 n 个点,经测量发现这 nn 个点的水平位置和竖直位置是两两不同的。

西部 314314 认为这幅壁画所包含的信息与这 n 个点的相对位置有关,因此不妨设坐标分别为 (1,y1),(2,y2),…,(n,yn),其中 y1∼yn是 1 到 n 的一个排列。

西部 314314 打算研究这幅壁画中包含着多少个图腾。

如果三个点 (i,yi),(j,yj),(k,yk)(i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n1≤i<j<k≤n 且 yi>yj,yj<yk,则称这三个点构成 V 图腾;

如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n且 yi<yj,yj>yk,则称这三个点构成  图腾;

西部 314 想知道,这 n 个点中两个部落图腾的数目。

因此,你需要编写一个程序来求出 V 的个数和  的个数。

输入格式

第一行一个数 n。

第二行是 n 个数,分别代表 y1,y2,…,yn。

输出格式

两个数,中间用空格隔开,依次为 V 的个数和  的个数。

数据范围

对于所有数据,n≤200000,且输出答案不会超过 int64。
y1∼yn是 1 到 n 的一个排列。

输入样例:

5
1 5 3 2 4

输出样例:

3 4

【代码及思路】

*要组成V即要前面的数字比当前数字大,后面的数字也要比当前数字大,可以将数字的个数看成变量,用前缀和的思想求解,组成的方案数就是前面比当前数字大的数A与后面比当前数字大的数B相乘之后的结果(排列组合)

*快速求解前缀和想到树状数组的方法文章来源地址https://www.toymoban.com/news/detail-463321.html

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
typedef long long ll;
int n, a[N], t[N];
int lower[N], great[N];
//lower表示比左边第i个位置小的数的个数
//greater表示左边比第i个位置大的数的个数
int lowbit(int x)
{
	return x & -x;
}
void update(int x, int d)
{
	for (int i = x; i <= n; i += lowbit(i)) t[i] += d;
}
int sum(int x)
{
	int res = 0;
	while (x)
	{
		res += t[x];
		x -= lowbit(x);
	}
	return res;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
	{
		int y = a[i];
		lower[i] = sum(y-1);//统计已经加入到树状数组中的数
		//出现在[1-y-1]中的次数
		great[i] = sum(n) - sum(y);
		//统计在[y+1,n]中数字出现的次数
		update(y, 1);
	}
	memset(t, 0, sizeof t);
	//从右向左统计比第i个位置小的数,以及比第i个位置大的数
	ll res1 = 0, res2 = 0;
	for (int i = n; i >0; i--)
	{
		int y = a[i];
		res1 += (ll)lower[i] * sum(y-1);
		res2 += (ll)great[i] * (sum(n) - sum(y));
		update(y, 1);
	}
	cout << res1 << " " << res2;
	return 0;
}

到了这里,关于Acwing241. 楼兰图腾的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【任务分配】基于CBBA算法带有任务属性、任务价值、任务时间窗等多种约束下多无人机任务分配附Matlab代码

     ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,代码获取、论文复现及科研仿真合作可私信。 🍎个人主页:Matlab科研工作室 🍊个人信条:格物致知。 更多Matlab完整代码及仿真定制内容点击👇 智能优化算法       神经网络预测       雷达通信       无

    2024年04月26日
    浏览(47)
  • 【任务分配】基于matlab市场的方法求解多机器人任务分配问题【含Matlab源码 3992期】

    ✅博主简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,Matlab项目合作可私信。 🍎个人主页:海神之光 🏆代码获取方式: 海神之光Matlab王者学习之路—代码获取方式 ⛳️座右铭:行百里者,半于九十。 更多Matlab仿真内容点击👇 Matlab图像处理(进阶版) 路径规划

    2024年03月11日
    浏览(42)
  • Flowable 之任务分配

    提示:以下是本篇文章正文内容,Java 系列学习将会持续更新 1.1.1 固定分配 固定分配就是我们前面介绍的,在绘制流程图或者直接在流程文件中通过 Assignee 来指定的方式。 1.1.2 表达式分配 Flowable 使用 UEL 进行表达式解析。UEL代表 Unified Expression Language ,是EE6规范的一部分.

    2024年02月09日
    浏览(32)
  • C++每日一练:任务分配问题(详解)

    今天这题比较有意思,排序算法还是比较有用的,显然选择排序在这里很容易实现。 提示:以下是本篇文章正文内容,下面案例可供参考 题目描述: 小明手头上有n个问题,每个问题都有一个数值,表示这个问题的难度;正好小明团队有n个人,每个人都有一个数值,表示这

    2023年04月26日
    浏览(39)
  • 【任务分配】多目标粒子群算法求解多无人机多任务路分配及路径规划(最短路程+最短时间)问题【含Matlab源码 3522期】

    1 粒子群算法 粒子群算法是智能算法领域中除蚁群算法、鱼群算法又一个智能群体算法。 PSO算法首先在可行解空间中初始化一群粒子,每个粒子都代表极值优化问题的一个潜在最优解。粒子在解空间中运动,通过跟踪个体极值Pbest和群体极值Gbest更新个体位置。 粒子每更新一次

    2024年02月04日
    浏览(62)
  • 2023最新版本Activiti7系列-任务分配

      在指派 用户任务 的审批人时。我们是直接指派的固定账号。但是为了保证流程设计审批的灵活性。我们需要各种不同的分配方式,所以这节我们就详细的来介绍先在Activiti7中我们可以使用的相关的分配方式.   固定分配就是我们前面介绍的,在绘制流程图或者直接在流

    2024年02月09日
    浏览(40)
  • RabbitMQ工作队列模型详解:实现高效任务分配与消费

    深入探索RabbitMQ的work消息模型,学习如何在多个消费者之间有效分配任务。掌握能者多劳的策略,优化队列消费效率,提升系统性能。

    2024年02月11日
    浏览(42)
  • 【任务分配】共识的捆绑算法CBBA多无人机多任务调度【含Matlab源码 3609期】

    本文采用一种两阶段启发式算法用于问题求解, 算法的第一阶段利用“最迟完成服务节点优先” (Latest-Service-Finished-First, 简称LSFF) 算法求得问题的初始解, 第二阶段利用模拟退火算法 (SA算法) 改善初始解, 获得“满意解”。 1 LSFF算法 LSFF算法是一种逆向计算的迭代算法, 其基本

    2024年02月03日
    浏览(62)
  • 用于异构团队搜索救援的多机器人任务分配框架

    A Multi-Robot Task Assignment Framework for Search and Rescue with Heterogeneous Teams 摘要:在灾后场景中,高效的搜索和救援行动需要机器人和人类之间的协作。现有的规划方法侧重于特定方面,但忽视了信息收集、任务分配和规划等关键要素。此外,以前考虑机器人能力和受害者需求的方法

    2024年02月03日
    浏览(46)
  • Linux定时任务详解&crontab -e 编辑之后如何保存并退出(Ubuntu)

    1. 保存 操作命令如下: crontab -e 打开crontab的配置文件,并编辑完成 Ctrl + O 写入内容, 出现 File name to Write ... ,输入 Enter Ctrl +X 保存并输出,保存完成 service cron restart , 重启 crontab 定时任务 2. 验证 两种验证方式: 使用 crontab -e 命令打开任务配置文件,此时可以看到刚才保

    2024年01月17日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包