您现在的位置是:首页 > 正文

P4145 上帝造题的七分钟2 / 花神游历各国 (线段树区间开方)

2024-02-01 00:51:59阅读 2

题目链接:点击这里

题目大意:
给定一个长度为 n n n 的序列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an ,对序列进行区间开方和区间查询

题目分析:
因为 1 ≤ a i ≤ 1 e 12 1 \le a_i \le 1e12 1ai1e12 1 e 12 1e12 1e12 连续开方 6 6 6 次就会变成 1 1 1 ,所以修改次数实际上是很少的然后我们用线段树维护区间和和区间最值,如果区间最值为 1 1 1 就不开方了否则就对每一个权值不为 1 1 1 的点进行开方

具体细节见代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define ll long long
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define int ll
using namespace std;
ll read()
{
	ll res = 0,flag = 1;
	char ch = getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch == '-') flag = -1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9')
	{
		res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';
		ch = getchar();
	}
	return res*flag;
}
const int maxn = 5e5+5;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-8;
struct sgt{
	int val,maxx;
}a[maxn<<2];
int n,m,sco[maxn];
char s[3];
void pushup(int root)
{
	a[root].val = a[root<<1].val+a[root<<1|1].val;
	a[root].maxx = max(a[root<<1].maxx,a[root<<1|1].maxx);
}
void build(int root,int l,int r)
{
	if(l == r)
	{
		a[root].val = a[root].maxx = read();
		return ;
	}
	int mid = l+r>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	pushup(root);
}
void updat(int root,int l,int r,int ql,int qr)
{
	if(l>qr || r<ql) return ;
	if(l == r)
	{
		a[root].val = sqrt(a[root].val);
		a[root].maxx = sqrt(a[root].maxx);
		return ;
	}
	int mid = l+r>>1;
	if(a[root<<1].maxx != 1) updat(root<<1,l,mid,ql,qr);
	if(a[root<<1|1].maxx != 1) updat(root<<1|1,mid+1,r,ql,qr);
	pushup(root);
}
int query(int root,int l,int r,int ql,int qr)
{
	if(l>qr || r<ql) return 0;
	if(l>=ql && r<=qr) return a[root].val;
	int mid = l+r>>1;
	return query(root<<1,l,mid,ql,qr)+query(root<<1|1,mid+1,r,ql,qr);
}
signed main()
{
	n = read();
	build(1,1,n);
	m = read();
	while(m--)
	{
		int opt = read(),x = read(),y = read();
		if(x > y) swap(x,y);
		if(opt == 0) updat(1,1,n,x,y);
		else printf("%lld\n",query(1,1,n,x,y));
	}
	return 0;
}

网站文章

  • 使用标准输出流(system.out)和打印流 (PrintWriter)来读取txt文件

    在电脑某盘根目录下放一个文本文件.里面写一首诗(内容随意发挥).把诗的内容输出到控制台. 要求: 1.使用标准输出流(system.out)来做。 2.使用打印流; (PrintWriter)来做。 import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReade

    2024-02-01 00:51:29
  • js:输出指定范围内所有自幂数

    4.输出指定范围内所有自幂数

    2024-02-01 00:51:21
  • 解决计算机不能登陆银行网银、邮箱、支付宝、淘宝等问题

    <br />  解决计算机不能登陆银行网银、邮箱、支付宝、淘宝等问题,本人使用了网上多个版本,以下操作才是王道,其余的诸如,重新启动“shell。dll”等,均不能解决,而且降低电脑的安全性。<br /> <br />  开始-运行-输入regsvr32 jscript.dll-确定,然后注册regsvr32 vbscript.dll。

    2024-02-01 00:51:13
  • 移植net-snmp到GSC3280

    移植net-snmp到GSC32801. 概念SNMP 是专门设计用于在 IP 网络管理网络节点(服务器、工作站、路由器、交换机及 HUBS 等)的一种标准协议,它是一种应用层协议。 SNMP 使网络管理员能够管理网络效能,发现并解决网络问题以及规划网络增长。通过 SNMP 接收随机消息(及事件报告)网络管理系统获知网络出现问题。SNMP 管理的网络有三个主要组成部分:管理的设备、代理...

    2024-02-01 00:50:43
  • A5平台eMMC协议分析

    A5平台eMMC协议分析

    目录1.A5平台资源定义1.1 A5平台支持的eMMC协议1.2 8bit方块图1.3 4bit方块图1.4 应用方块图2.eMMC协议2.1术语2.2总线协议2.3 总线模式 3.命令类型3.1命令...

    2024-02-01 00:50:39
  • 用C++实现指数拟合方程的算法

    要用 C 语言实现指数拟合方程的算法,需要按照以下步骤进行: 确定所需的数据。指数拟合方程需要的数据包括至少两组数据,每组数据包含一个自变量和一个因变量。自变量是指可以改变的量,因变量是指随自变量改变...

    2024-02-01 00:50:30
  • 多线程编程-- 线程安全的queue II

    上一篇文章中使用std::mutex 和 条件变量 std::condition_variable 实现了一个线程安全的队列。这个队列是没有边界的, 也就是允许插入无限多的元素的,事实上这是不可能的, 当元素过多时候,插入元素会失效。这是很危险的一种行为。下面来实现一个有边界的线程安全的队列 BoundedBlockingQueuetemplate <typename T>class Bounde

    2024-02-01 00:50:24
  • 英飞凌 AURIX TC3xx 烧录程序后没有反应

    英飞凌 AURIX TC3xx 烧录程序后没有反应

    英飞凌 AURIX TC3xx 烧录程序后没有反应,修改芯片UCBs信息中起始地址与代码中的入口地址相对应

    2024-02-01 00:49:55
  • 灰度部署方式

    灰度部署方式

    一蓝绿发布蓝绿发布要求有两套系统,一套提供系统服务,认为是绿色的,另外一套是准备发布的系统,认为是蓝色的。两套系统提供相同的功能,都能提供全量服务。最初只有绿色系统是对外提供服务的,同时准备好具有新特...

    2024-02-01 00:49:50
  • NVIDIA控制面板进行设置时提示“无法应用选定的设置到您的电脑”的解决办法(更新显卡驱动的方法)

    NVIDIA控制面板进行设置时提示“无法应用选定的设置到您的电脑”的解决办法(更新显卡驱动的方法)

    总的来说就是把自己电脑上的显卡驱动进行更新就可以解决这个问题,别的方法不一定能用,另外装载AMD显卡的电脑也是同样的操作,只不过AMD显卡的驱动要去AMD官网进行下载。7.最后找到下载好的NVIDIA...

    2024-02-01 00:49:42