当前位置: 首页 > article >正文

A - 整数的简单问题/A - A Simple Problem with Integers

 

你有 N 个整数,A1、A2、... 、AN。您需要处理两种作。一种类型的作是在给定的时间间隔内将一些给定的数字添加到每个数字。另一种是询问给定区间内的数字之和。

输入

第一行包含两个数字 N 和 Q。1 ≤ N,Q ≤ 100000。
第二行包含 N 个数字,初始值为 A1、A2、... 、AN。-10000000000 ≤ Ai ≤ 1000000000。
接下来的 Q 行中的每一行都表示一个作。
“C a b c” 是指将 c 添加到 AaAa+1、... 、Ab 中的每一个。-10000 ≤ c ≤ 10000。
“Q a b” 表示查询 Aa, Aa+1, ... , Ab 之和。

输出

您需要按顺序回答所有 Q 命令。一行中只有一个答案。

样本

输入复制输出复制
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
4
55
9
15

提示

总和可能超出 32 位整数的范围。

注意:查询的返回值为long long 型

代码:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct ss {
	long long sum ;
	long long lazy ;
	int x ;
	int y ;
};
struct ss zong[400005];
long long a[400005];
int n, m;
char v;
int f, g;
long long h;
void build(int i, int l, int r) {
	zong[i].x = l, zong[i].y = r;
	zong[i].sum = a[r] - a[l - 1];
	zong[i].lazy = 0;
	if (l == r) {
		return;
	}
	int mid = l + (r - l) / 2;
	build(i * 2, l, mid);
	build(i * 2 + 1, mid + 1, r);
}
void yidong(int i, int q, int w) {
	if (zong[i].y<q || zong[i].x>w || (zong[i].x >= q && zong[i].y <= w))
		return;
	zong[i * 2].lazy += zong[i].lazy;
	zong[i * 2 + 1].lazy += zong[i].lazy;
	zong[i].sum += zong[i].lazy * (zong[i].y - zong[i].x + 1);
	zong[i].lazy = 0;
	yidong(i * 2, q, w);
	yidong(i * 2 + 1, q, w);
}
long long chaxun(int i,int q, int w) {
	if (zong[i].x >= q && zong[i].y <= w) {
		return zong[i].sum + zong[i].lazy * (zong[i].y - zong[i].x + 1);
	}
	else if ((zong[i].x < q && zong[i].y>=q) || (zong[i].x <= w &&zong[i].y > w)) {
		if (zong[i].lazy != 0) {
			yidong(i, q, w);
		}
		return chaxun(i * 2, q, w) + chaxun(i * 2 + 1, q, w);
	}
	else {
		return 0;
	}
}
void tianjia(int i, int q,int w,int e) {
	if (zong[i].y<q || zong[i].x>w )
		return;
	else if (zong[i].x >= q && zong[i].y <= w) {
		zong[i].lazy += e;
		return;
	}
	else{
		if (zong[i].lazy != 0) {
			zong[i * 2].lazy += zong[i].lazy;
			zong[i * 2 + 1].lazy += zong[i].lazy;
			zong[i].sum += zong[i].lazy * (zong[i].y - zong[i].x + 1);
			zong[i].lazy = 0;
		}
		if (zong[i].x < q && zong[i].y >= q) {
			zong[i].sum += e * ((zong[i].y > w ? w : zong[i].y) - q + 1);
			tianjia(i * 2, q, w, e);
			tianjia(i * 2 + 1, q, w, e);
		}
		else  {
			zong[i].sum += e * (w - zong[i].x + 1);
			tianjia(i * 2, q, w, e);
			tianjia(i * 2 + 1, q, w, e);
		}
	}
}
int main(){
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		a[i] += a[i - 1];
	}
	build(1, 1, n);
	while (m--) {
		do{
			scanf("%c", &v);
		} while (v != 'Q' && v != 'C');
		if (v == 'Q') {
			scanf("%d %d", &f, &g);
			long long t=chaxun(1,f, g);
			printf("%lld\n", t);
		}
		else {
			scanf("%d %d %lld", &f, &g, &h);
			tianjia(1,f, g, h);
		}
	}
	return 0;
}


http://www.kler.cn/a/589356.html

相关文章:

  • Linux centos7误删/boot拯救方法
  • 【系统架构设计师】操作系统 - 文件管理 ③ ( 树形目录结构 | 文件属性 | 绝对路径 与 相对路径 )
  • 大型智慧城市、交通枢纽、跨区域联网监控视频平台使用LiveGBS国标GB28181平台如何实现分布式集群及负载均衡
  • 线性表的顺序表示
  • Mock接口编写教程-axios-mock-adapter(React)
  • react18 核心知识点杂记1
  • 需要使用新应用以打开此ms-gamingoverlay链接怎么解决
  • list及其模拟实现
  • 如何管理需求变更
  • Elasticsearch:为推理端点配置分块设置
  • 深入理解蒸馏、Function Call、React、Prompt 与 Agent
  • Redis安装与基础配置:单节点离线部署与配置解析
  • 量子计算助力智能制造:未来工业的加速器
  • 【测试篇】关于allpairs实现正交测试用例保姆级讲解,以及常见的错误问题
  • 相对论之光速
  • 联想拯救者 M600 无线游戏鼠标|自定义驱动程序安装说明
  • 【C++经典例题】反转字符串中单词的字符顺序:两种实现方法详解
  • CMake学习笔记(三):静态库,动态库的生成和使用
  • Python基础入门掌握(十三)
  • Spring源码解析