首页 > 编程语言 >分治算法

分治算法

时间:2023-09-20 22:57:45浏览次数:47  
标签:递归 int 分治 mid 算法 两边 排序 sim

基本思想:将序列分为 \([l,mid]\) 和 \([mid+1,r]\),然后递归两边,同时再计算 \([l,mid]\) 与 \([mid+1,r]\) 影响所产生的答案(满足单调性的话一般使用走指针)。

二维偏序

首先将所有元素按 \(x,y\) 排序。

然后递归两边,随后用两个指针 \(i\) 和 \(j\),\(i\) 从 \(l\) 到 \(mid\),\(j\) 从 \(mid+1\) 到 \(r\),当 \(y_i>y_j\),说明 \(l\sim i-1\) 的点都不超过 \(j\),于是 \(ans_j\) 累加 \(i-l\),然后 \(j\) 后移一位;如果不是,那么我们的 \(i\) 往后移动一位。

这么做会有一个问题,我们的两边都应该按 \(y\) 排序,才能满足 \(y\) 的单调性,然而我们却按 \(x\) 排序,所以在统计完后重构 \(l\sim r\) 即可。

void f(int l,int r){
	if(l==r) return ;
	int m=(l+r)/2,i=l,j=m+1,c=l;
	f(l,m);f(m+1,r);
	while(i<=m||j<=r){
		if(j>r||(i<=m&&a[i].y<=a[j].y))
			b[c++]=a[i++];//类似于归并排序
		else ans[a[j].id]+=i-l,b[c++]=a[j++];
	}
	for(int i=l;i<=r;i++)a[i]=b[i];
}

标签:递归,int,分治,mid,算法,两边,排序,sim
From: https://www.cnblogs.com/includec/p/17718720.html

相关文章

  • 基于FasterRCNN深度学习网络的车辆检测算法matlab仿真
    1.算法运行效果图预览 Tttttttttttttt123   2.算法运行软件版本MATLAB2022A 3.算法理论概述       车辆检测是计算机视觉和人工智能领域的重要研究方向,它在交通管理、智能驾驶和安防等领域具有广泛的应用。FasterR-CNN是一种常用的目标检测算法,结合了深度......
  • 6.1 KMP算法搜索机器码
    KMP算法是一种高效的字符串匹配算法,它的核心思想是利用已经匹配成功的子串前缀的信息,避免重复匹配,从而达到提高匹配效率的目的。KMP算法的核心是构建模式串的前缀数组Next,Next数组的意义是:当模式串中的某个字符与主串中的某个字符失配时,Next数组记录了模式串中应该回退到哪个位置,以......
  • 6.1 KMP算法搜索机器码
    KMP算法是一种高效的字符串匹配算法,它的核心思想是利用已经匹配成功的子串前缀的信息,避免重复匹配,从而达到提高匹配效率的目的。KMP算法的核心是构建模式串的前缀数组Next,Next数组的意义是:当模式串中的某个字符与主串中的某个字符失配时,Next数组记录了模式串中应该回退到哪个位置,以......
  • R语言RStan MCMC:NUTS采样算法用LASSO 构建贝叶斯线性回归模型分析职业声望数据|附代码
    原文链接:http://tecdat.cn/?p=24456原文出处:拓端数据部落公众号最近我们被客户要求撰写关于RStan的研究报告,包括一些图形和统计输出。如果你正在进行统计分析:想要加一些先验信息,最终你想要的是预测。所以你决定使用贝叶斯。但是,你没有共轭先验。你可能会花费很长时间编写Metr......
  • 6.1 KMP算法搜索机器码
    KMP算法是一种高效的字符串匹配算法,它的核心思想是利用已经匹配成功的子串前缀的信息,避免重复匹配,从而达到提高匹配效率的目的。KMP算法的核心是构建模式串的前缀数组Next,Next数组的意义是:当模式串中的某个字符与主串中的某个字符失配时,Next数组记录了模式串中应该回退到哪个位置,......
  • (笔记)机器人坐标系用法和算法原理
     机器人坐标系 一、基坐标系机器人都有一个不会变的坐标系,叫基坐标系或世界坐标系(每家叫法不同,原理一样)。基坐标系是怎么来的呢? 拿6轴机器人举例: 第一轴的旋转轴 一般都会定义机器人第一轴的旋转轴为基坐标系Z轴,旋转中心即是坐标系原点,X和Y的方向是的电机零点......
  • 算法学习笔记(29):分块
    分块这是一种基于根号的算法,核心为大块标记,散块暴力,做到复杂度的平衡。可能第一个想到于此相关的就是莫队吧,这是利用分块优化暴力的方法。目录分块RmqProblem/mex[国家集训队]排队-洛谷[TJOI2009]开关-洛谷[Violet]蒲公英-洛谷小小总结RmqProblem/mex这本不......
  • 《算法的乐趣》高清高质量PDF 电子书 附源码
    本书从一系列有趣的生活实例出发,全面介绍了构造算法的基础方法及其广泛应用,生动地展现了算法的趣味性和实用性。全书分为两个部分,第一部分介绍了算法的概念、常用的算法结构以及实现方法,第二部分介绍了算法在各个领域的应用,如物理实验、计算机图形学、数字音频处理等。其中,既有各种......
  • <学习笔记>线段树分治
    一种离线处理方法可以处理“具体哪个修改对询问有影响”、可以贡献不独立、可以支持插入删除。例题对这道题来说,对修改开线段树,线段树上每个节点开一个\(vector\)来维护出现在这段区间的线段,加入一个线段的区间,直接在区间查询时对所包含的节点压入这条线段就可以。然后从根......
  • 【目标检测】Fast R-CNN算法实现
    一、前言2014年,RossGirshick提出RCNN,成为目标检测领域的开山之作。一年后,借鉴空间金字塔池化思想,RossGirshick推出设计更为巧妙的FastRCNN(https://github.com/rbgirshick/fast-rcnn),极大地提高了检测速度。FastRCNN的提出解决了RCNN结构固有的三个弊端:繁琐的多阶段训练:RCNN......