The beautiful values of the palace---------------------------思维(树状数组+扫描线)-程序员宅基地

技术标签： 树状数组  套路题  思维  

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

题意:
给定一个n*n的螺旋矩阵，每个方格的权值为当前数字各位之和，现在给出m个宝殿的坐标。再给出q个询问，询问给出的矩形中宝典的权值之和

解析:
这道题最难的地方就是给定坐标求出螺旋矩阵对应的权值

给出对应代码，细节大家自己看

ll getval(ll x, ll y, ll n) {
    
	ll t = min(min(x, y), min(n - x + 1, n - y + 1));
	ll ta = 4 * (t - 1) * (n - t + 1);
	if (x == n - t + 1) ta += n - t - y + 2;//在所在圈层的右侧边
	else if (x == t) ta += 2 * n - 5 * t + y + 3;//左侧边
	else if (y == t) ta += 2 * n - 3 * t - x + 3;//下侧边
	else ta += 3 * n - 7 * t + x + 4;//上侧边
	return ta;
}

第二个难点就在于N的范围太大，我们不能用二维数组来求前缀和(会炸空间)，所以我们要给m个宝殿坐标和q个询问坐标进行离线处理。
对于求二维前缀和的问题，我们把s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]拆解成4个，用flag来标记哪些需要±
之后我们可以运用扫描线的方法，先按照x排序，然后对y进行映射，用树状数组维护映射后y上的值。用一条竖直的扫描线不断向右扫，遇到一个询问点就查询一次。


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+10;
ll c[N*2],cnt;
ll ans[N];
ll t,n,m,p;
ll getval(ll x, ll y, ll n) {
    
	ll t = min(min(x, y), min(n - x + 1, n - y + 1));
	ll ta = 4 * (t - 1) * (n - t + 1);
	if (x == n - t + 1) ta += n - t - y + 2;//在所在圈层的右侧边
	else if (x == t) ta += 2 * n - 5 * t + y + 3;//左侧边
	else if (y == t) ta += 2 * n - 3 * t - x + 3;//下侧边
	else ta += 3 * n - 7 * t + x + 4;//上侧边
	return ta;
}


struct node
{
    
	ll x,y,flag,pos;
	bool operator<(const node &W){
    
		if(x!=W.x) return x<W.x;
		if(y!=W.y) return y<W.y;
		return pos<W.pos;
	}
}a[N*2];
ll lowbit(ll x)
{
    
	return x&(-x);
}
void add(int i,ll val,int n)
{
    
	while(i<=n)
	{
    
		c[i]+=val;
		i+=lowbit(i);
	}
}
ll sum(int i,int n)
{
    
	ll res=0;
	while(i)
	{
    
		res+=c[i];
		i-=lowbit(i);
	}
	return res;
}
int main()
{
    
	scanf("%lld",&t);
	while(t--)
	{
    
		scanf("%lld %lld %lld",&n,&m,&p);
		memset(c,0,sizeof c);
		memset(ans,0,sizeof ans);
		cnt=0;
		for(int i=1;i<=m;i++)
		{
    
			ll x,y;
			scanf("%lld %lld",&x,&y);
			ll tmp=getval(x,y,n);
			ll ans=0;
			while(tmp)
			{
    
				ans+=tmp%10;
				tmp/=10;
			}
			a[++cnt]={
    x,y,ans,i};
		}
		for(int i=m+1;i<=m+p;i++)
		{
    
			ll x1,x2,y1,y2;
			scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);
			a[++cnt]={
    x2,y2,1,i};
			a[++cnt]={
    x1-1,y2,-1,i};
			a[++cnt]={
    x2,y1-1,-1,i};
			a[++cnt]={
    x1-1,y1-1,1,i};
		}
		sort(a+1,a+1+cnt);
		for(int i=1;i<=cnt;i++)
		{
    
			if(a[i].pos<=m) add(a[i].y,a[i].flag,n);
			else
			{
    
				ans[a[i].pos-m]+=sum(a[i].y,n)*a[i].flag;
			}
		}
		for(int i=1;i<=p;i++) printf("%lld\n",ans[i]);
	}
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_43690454/article/details/107272024

智能推荐

关于在simulink中使用s-function后出现State derivatives returned by S-function during flag=1 call must be a rea_state derivatives returned by s-function 'pmsm' in-程序员宅基地

文章浏览阅读5.9k次，点赞9次，收藏16次。解决了在simulink中使用s-function遇到的报错：State derivatives returned by S-function 'demo' in 'test/S-Function' during flag=1 call must be a real vector of length 2 _state derivatives returned by s-function 'pmsm' in 'ipmsm/ipmsm/s-function1

Sublime Text 关闭自动更新 | Mac_mac sublime text 取消更新提示-程序员宅基地

文章浏览阅读3.1k次。1. 打开配置文件Mac 如下图2. 在文件内部添加这段文字，就可以了："update_check":false _mac sublime text 取消更新提示

Linux系统下DNS配置指南_linux 服务器修改网络dns-程序员宅基地

文章浏览阅读548次，点赞10次，收藏6次。Linux系统下DNS配置指南_linux 服务器修改网络dns

Springboot/java/node/python/php基于springboot+vue手机售后管理系统【2024年毕设】-程序员宅基地

文章浏览阅读779次，点赞19次，收藏24次。springboot微信小程序的小疾病问诊服务系统的设计与实现。springboot基于spring的物业管理系统的设计与实现。springboot基于Java的高校学生请假系统。ssm基于Android的购物商场APP设计与实现。springboot基于微信小程序的智慧校园系统。ssm基于Android的英语词典的设计与开发。ssm基于SSM+Vue的学生实践管理平台开发。ssm基于android的企业员工考勤系统。ssm基于web的暗香小店系统的设计与实现。ssm基于Web的高等学校公费医疗管理系统。

css中hover属性的使用技巧_css hover的用法-程序员宅基地

文章浏览阅读2.3w次，点赞15次，收藏63次。hover属性用不同的书写方式，来改变不同关系的元素样式。元素:hover 表示聚焦后改变自己元素:hover 元素 表示聚焦后改变其子元素元素:hover + 元素 表示聚焦后改变其指定的“亲兄弟”（条件是该兄弟元素与其相邻）元素元素:hover ~ 元素 表示聚焦后改变其指定的兄弟元素，两个元素相不相邻都行。示例：.first:hover {color: white;}/* 聚焦我改变自己 */.three:hover .three-son {font-size: 20px._css hover的用法

coursera-斯坦福-机器学习-吴恩达-第8周笔记-无监督学习_pca反向压缩-程序员宅基地

文章浏览阅读6k次，点赞3次，收藏15次。coursera-斯坦福-机器学习-吴恩达-第8周笔记-无监督学习coursera-斯坦福-机器学习-吴恩达-第8周笔记-无监督学习1聚类算法clutering1聚类算法简介2K-means21kmeans的目标函数22随机初始化23选择类别数3考试quiz维数约减 dimensionality reduction1数据压缩2数据可视化3维度约简-主成分分析法PCA1 PCA_pca反向压缩

随便推点

基于Wemos D1 Mini Pro开发板的天气显示器_arduino wemos d1 mini-程序员宅基地

文章浏览阅读226次，点赞2次，收藏3次。本项目设计了一款可以触摸控制的天气显示器。主要由Wemos D1 Mini Pro和TFT显示屏组成，利用Wemos D1 Mini Pro作为设备的主控芯片，发出Wi-Fi信号并接收相应指令,通过调用API将接收到的信息传输到TFT显示屏，TFT显示屏将接收到的信息显示出来。该天气显示器实现对所在地区当前的时间与日期；当日的天气信息，如温度、压力、湿度、降雨量；七天的未来预测等功能的显示。设计采用Wemos D1 Mini Pro，利用API将实时获取的天气信息，通过TFT显示屏显示出来。_arduino wemos d1 mini

Android 双屏异显（兼容android8）_android service 检测是否双屏-程序员宅基地

文章浏览阅读653次。public void initDiffDisplay() { try { DisplayManager displayManager = (DisplayManager) getSystemService(Context.DISPLAY_SERVICE); Display[] presentationDisplays = displayManager.getDisplays(); if (presentationDi._android service 检测是否双屏

【全开源】JAVA婚恋相亲红娘牵线系统源码支持微信小程序+微信公众号+H5+APP-程序员宅基地

文章浏览阅读530次，点赞23次，收藏10次。springboot+mybatisplus+mysql 用户端 uniapp（vue语法）管理后台 vue+elementUi。后台服务 springboot+mybatisplus+mysql。一、我们技术使用JAVA后台服务 前后端分离。管理后台 vue+elementUi。用户端 uniapp（vue语法）适配小程序+H5+公众号。私信客服获取演示地址。私信客服获取演示地址。

6.python输入整数年份，判断对应整数年份是否为闰年并输出结果_判断闰年的python程序直接输入一个代表年份的正整数-程序员宅基地

文章浏览阅读3.3k次，点赞3次，收藏5次。# -*- coding: UTF-8 -*-year = int(input("输入一个年份："))if year % 100 == 0: if year % 400 == 0: print('%d年是闰年' % year) else: print('%d年不是闰年' % year)else: if year % 4 == 0: print('%d年是闰年' % year) else: print('%d_判断闰年的python程序直接输入一个代表年份的正整数

【图像去噪】偏微分方程PDE图像去噪（含SNR）【含Matlab源码 1890期】_pdnet 深度学习 偏微分方程 去噪-程序员宅基地

文章浏览阅读987次，点赞20次，收藏19次。偏微分方程PDE图像去噪（含SNR）完整的代码，方可运行；可提供运行操作视频！适合小白！_pdnet 深度学习 偏微分方程 去噪

Ubuntu18.04安装教程（很详细）_ubuntu18安装-程序员宅基地

文章浏览阅读6.6w次，点赞128次，收藏962次。Ubuntu18.0详尽版安装教程下载Ubuntu18.04下载VMware Workstation安装虚拟机下载Ubuntu18.04官方网站：http://old-releases.ubuntu.com/releases/18.04.4/?_ga=2.44113060.1243545826.1617173008-2055924693.1608557140下载VMware Workstation这个在网上有很多教程下载，这里我就不写了，我用的版本是14 pro。如下图：安装虚拟机1、打开_ubuntu18安装

推荐文章

热门文章

相关标签