首页 > 其他分享 >扫描线模板

扫描线模板

时间:2024-05-18 22:18:26浏览次数:22  
标签:rt yy cnt int len i64 扫描线 模板

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e6 + 5;

//本模板是从左往右扫的,从下往上扫同理
#define ls (rt<<1)
#define rs (rt<<1|1)

i64 cover[N * 8]; //存放i节点对应区间覆盖情况的值
i64 n;
i64 len[N * 8];
i64 yy[N * 2]; //存放离散后的y值,下标用lowerbound进行查找
i64 cnt = 0;
struct node {
	i64 x;
	i64 up, down;; //边的y坐标上,y坐标下
	i64 inout;//入边为1,出边为-1
} line[N * 2], u;

bool cmp(node a, node b) {
	if ( a.x == b.x ) return a.inout > b.inout; //一定是加边在前面!!!
	return a.x < b.x;
}

void pushup( i64 l, i64 r, i64 rt ) {
	//pushup其实主要就思考在什么情况,需要更新哪些信息来维护线段树
	if ( cover[rt] > 0 ) len[rt] = yy[r] - yy[l];
	//如果某个节点的cover为正,那么这个点对应区间的长度全为有效的
	else if ( l + 1 == r ) len[rt] = 0; //到了叶子节点
	else len[rt] = len[ls] + len[rs];
}

void update( i64 yl, i64 yr, i64 pd, i64 l, i64 r, i64 rt ) {
	if ( yl > r || yr < l ) return ;
	if ( yl <= l && yr >= r ) {
		cover[rt] += pd;//根据出边入边,加上相应的值
		pushup( l, r, rt );
		return ;
	}
	if ( l + 1 == r ) return ; //到子节点,这句一定要有!!!
	i64 mid = (l + r) >> 1;
	if ( yl <= mid ) {
		update( yl, yr, pd, l, mid, ls );
	}
	if ( yr > mid ) {
		update( yl, yr, pd, mid, r, rs );
		//这里不再是m+1,因为要进入类似[1,2][2,3]的叶子节点
	}

	pushup( l, r, rt );
}

int main() {
	cnt = 0;
	cin >> n;

	//左上角到右下角
	auto get = [&](int x1, int y1, int x2, int y2) {
		u.x = x1; u.down = y1, u.up = y2, u.inout = 1;
		line[ ++cnt ] = u;//给入边赋值
		yy[cnt] = y1;//获得y值

		u.x = x2; u.down = y1, u.up = y2, u.inout = -1;
		line[ ++cnt ] = u;
		yy[cnt] = y2;
	};

	for (i64 i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		get(0, y - 1, x, y);
		get(x - 1, 0, x, y);
	}

	sort( yy + 1, yy + cnt + 1); //给yy排个序
	sort( line + 1, line + cnt + 1, cmp ); //给line按照x轴方向从左到右排序
	i64 length = unique( yy + 1, yy + cnt + 1 ) - (yy + 1);
	//进行离散化操作,unique返回重复位置指针,减去(头指针+1)是数组开始的地方得到数组长度
	memset( cover, 0, sizeof( cover ) );
	memset( len, 0, sizeof(len) );

	i64 ans = 0;
	for (i64 i = 1; i <= cnt; i++) {
		ans += len[1] * ( line[i].x - line[i - 1].x );
		i64 yl = lower_bound( yy + 1, yy + length + 1, line[i].down ) - yy;
		i64 yr = lower_bound( yy + 1, yy + length + 1, line[i].up ) - yy;
		i64 pd = line[i].inout;
		update( yl, yr, pd, 1, length, 1 );
	}
	cout << ans << '\n';

	return 0;
}

标签:rt,yy,cnt,int,len,i64,扫描线,模板
From: https://www.cnblogs.com/Kescholar/p/18199853

相关文章

  • template之变参模板学习
    转自:https://www.cnblogs.com/qicosmos/p/4325949.html,讲的很好1.介绍C++11的新特性--可变模版参数(variadictemplates)对参数进行了高度泛化,它能表示0到任意个数、任意类型的参数。 要用三个点来定义:template<class...T>voidf(T...args); 省略号的作用有两个:1.声明......
  • 低开开发笔记(七): 换引擎,点击跳转模板样式
    好家伙, 完整代码已开源https://github.com/Fattiger4399/ph-questionnaire.git 1.思路现在,我们的需求是,点击对应的模板,更换对应的模板数据   2.上代码<el-menudefault-active="2"class="el-menu-vertical-demo"@open="handleOpen"@close="handleClose"......
  • Django自定义模板标签与过滤器
    title:Django自定义模板标签与过滤器date:2024/5/1718:00:02updated:2024/5/1718:00:02categories:后端开发tags:Django模版自定义标签过滤器开发模板语法Python后端前端集成Web组件Django模板系统基础1.Django模板语言概述Django模板语言(DTL)是一种用......
  • JAVA KMP 纯模板
    纯模板记忆使用~classMain{staticchar[]s1;staticchar[]s2;staticint[]next;publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);s1=in.nextLine().toCharArray();s2=in.nextLine().to......
  • 界面组件DevExpress WPF中文教程 - 如何从CRTX模板文件导入图表设置
    DevExpressWPF 拥有120+个控件和库,将帮助您交付满足甚至超出企业需求的高性能业务应用程序。通过DevExpressWPF能创建有着强大互动功能的XAML基础应用程序,这些应用程序专注于当代客户的需求和构建未来新一代支持触摸的解决方案。无论是Office办公软件的衍伸产品,还是以数据为中......
  • CrushFTP服务器端模板注入
    漏洞描述由于CrushFTP存在服务器端模板注入漏洞,未经身份验证的远程攻击者可以逃避虚拟文件系统(VFS)沙箱,绕过身份验证获得管理访问权限,泄露敏感信息或执行代码。Fofa:server="CrushFTP"||header="/WebInterface/login.html"||banner="/WebInterface/login.html"||header="......
  • 字典树模板
    码:点击查看代码structNode{boolisend;intson[26];intnum;}tir[N];inttircnt=1;voidtir_insert(strings){intnow=0;for(inti=0;i<s.size();i++){intch=s[i]-'a';if(tir[now].son[ch]==0)......
  • 逆向 | 驱动IRP通信模板
    逆向|驱动IRP通信模板踩了很多坑,比如说IoCreateDevice以后要删除,符号链接也要在卸载的时候删除啥的。反正存个模板在这儿下次就能套了:#include<ntddk.h>#include<stdio.h>#include<stdlib.h>//0-2047是保留的,可以用2048-4095#defineOPER1CTL_CODE(FILE_DEVICE_UN......
  • 微信开发-主动推送模板消息给特定用户
    其实也比较简单,设置模板后推送即可,具体官方说明文档如下:接口调用请求说明http请求方式:POSThttps://api.weixin.qq.com/cgi-bin/template/del_private_template?access_token=ACCESS_TOKENPOST数据说明如下:{"template_id":"Dyvp3-Ff0cnail_CDSzk1fIc6-9lOkxsQE7ex......
  • C++模板编程-enable_if
    std::enable_if的使用对于重载的函数或者函数模板的选择上,编译器内部有一个自己的规则,并不是简单粗暴的对函数就优先选择,对函数模板就靠后选择替换失败并不是一个错误(SFINAE):SubstitutionFailureIsNotAnError,SFINAE看成是C++语言的一种特性或者说一种模板设计中要遵循的......