首页 > 其他分享 >acwing 242. 一个简单的整数问题

acwing 242. 一个简单的整数问题

时间:2024-06-06 16:01:25浏览次数:23  
标签:int sum tr mid long 整数 242 acwing

https://www.acwing.com/problem/content/248/

给定长度为 N 的数列 A,然后输入 M 行操作指令。

第一类指令形如 C l r d,表示把数列中第 l∼r 个数都加 d。

第二类指令形如 Q x,表示询问数列中第 x个数的值。

对于每个询问,输出一个整数表示答案。

输入格式
第一行包含两个整数 N 和 M。

第二行包含 N个整数 A[i]。

接下来 M行表示 M条指令,每条指令的格式如题目描述所示。

输出格式
对于每个询问,输出一个整数表示答案。

每个答案占一行。

数据范围
1≤N,M≤105
,
|d|≤10000
,
|A[i]|≤109
输入样例:
10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2
输出样例:
4
1
2
5
#include <iostream>
#include <string>

using namespace std;


const int N = 100010;
int n, q;
int a[N];


struct NODE {
	int l, r;
	long long sum, lazy;
	void update(long long x) {
		sum += 1ll * (r - l + 1) * x;
		lazy += x;
	}
}tr[4 * N];


void pushup(int u) {
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r) {
	tr[u].l = l, tr[u].r = r;
	tr[u].sum = tr[u].lazy = 0;
	if (l == r) {
		tr[u].sum = a[l];
	}
	else {
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
		pushup(u);
	}
}

void pushdown(int u) {
	int lazyv = tr[u].lazy;
	if (lazyv) {
		tr[u << 1].update(lazyv);
		tr[u << 1 | 1].update(lazyv);
		tr[u].lazy = 0;
	}
}

long long query(int u, int l, int r) {
	int L = tr[u].l; int R = tr[u].r;
	if (l <= L && r >= R) {
		return tr[u].sum;
	}
	else {
		pushdown(u);
		long long ans = 0;
		int mid = L + R >> 1;
		if (l <= mid) ans += query(u << 1, l, r);
		if (r > mid) ans += query(u << 1 | 1, l, r);
		pushup(u);
		return ans;
	}
}


void modify(int u, int l, int r, long long val) {
	int L = tr[u].l, R = tr[u].r;
	if (l <= L && r >= R) {
		tr[u].update(val);
	}
	else {
		pushdown(u);
		int mid = L + R >> 1;
		if (l <= mid) modify(u << 1, l, r, val);
		if (r > mid) modify(u << 1 | 1, l, r, val);
		pushup(u);
	}
}


int main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	build(1, 1, n);

	for (int i = 1; i <= q; i++) {
		string s;
		int l, r, d, q;
		cin >> s;
		if (s == "Q") {
			cin >> l ;
			cout << query(1, l,l) << endl;
		}
		else {
			cin >> l >> r >> d;
			modify(1, l, r, d);
		}
	}

	return 0;
}

我的视频空间

标签:int,sum,tr,mid,long,整数,242,acwing
From: https://www.cnblogs.com/itdef/p/18235427

相关文章

  • 快速排序——AcWing785.快速排序
    AcWing785.快速排序题目描述785.快速排序-AcWing题库运行代码#include<iostream>#include<algorithm>usingnamespacestd;constintN=1e6+6;intq[N];voidquick_sort(intq[],intl,intr){if(l>=r)return;intm=l+r>>1;//>......
  • //编写一个函数,传入一个整数,将数字反转,检查数字是不是数字的2倍 果是则返回true,否
    思路:比如n=1234;那么如何获取4,应该n%10;那么如何获取3,获取3之前应该删除4,所以n/10;//40+3=43//43*10=430>430+2(432)>432*10(4320)+1r=0怎么获取40:r*10+d看代码:1publicclasstest2{2publicstaticvoidmain(String[]args){3int......
  • 编写一个函数,传入一个整数,获取整数的每一位,将每位相加,返回他们的和
    思路:1publicclasstest{2publicstaticvoidmain(String[]args){3intnumber=1234;4System.out.println(number%10);5System.out.println(number/10);6System.out.println(123%10);7System.out.println(123/......
  • 程序分享--常见算法/编程面试题:整数转罗马数字
    关注我,持续分享逻辑思维&管理思维&面试题;可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导;推荐专栏《10天学会使用asp.net编程AI大模型》,目前已完成所有内容,持续上传中。一顿烧烤不到的费用,让人能紧跟时代的浪潮。从普通网站,到公众号、小程序,再到AI大模型网站。干货满满......
  • 2024-06-05:用go语言,给定三个正整数 n、x 和 y, 描述一个城市中由 n 个房屋和 n 条街道
    2024-06-05:用go语言,给定三个正整数n、x和y,描述一个城市中由n个房屋和n条街道连接的情况。城市中存在一条额外的街道连接房屋x和房屋y。需要计算对于每个街道数(从1到n),有多少房屋对满足从一个房屋到另一个房屋经过的街道数正好为该街道数。在结果数组中,索引k对......
  • 力扣 41.缺少的第一个正整数
    题目描述:给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。示例1:输入:nums=[1,2,0]输出:3解释:范围[1,2]中的数字都在数组中。示例2:输入:nums=[3,4,-1,1]输出:2解释:1......
  • acwing329 围栏障碍训练场 题解
    考试压轴题,意识到这题是线段树优化\(dp\)时追悔莫及。为了简化题目,我将从起点到原点变成了从原点到起点(这样就可以省去两个数组的空间)。想到设\(dp_{i,j}\)表示在第\(i\)层,奶牛们在\(j\)列时的最小移动范围,则转移方程为(设输入为\(l,r\)):\[\begin{cases}dp_{i,j}=dp_{......
  • C语言-----计算两个int(32位)整数m和n的二进制表达中,有多少个位(bit)不同?
    intcountBits(intn){intcount=0;while(n){count+=n&1;//count=count+n&1//n&1的结果只可能是1或者0//如果对应的二进制位上的数字不同,那么n&1的结果就是1,//那么count刚好加一n>>=1;......
  • 输入一个整数,返回这个整数的位数
    /*******************************************************************************************************@filename: :Count*@brief :*@author :[email protected]*@date :2024/06/03*@version1.0 :V1.0*@propert......
  • 1120大整数加法
    没有多组输入 (还得是y总)QAQ//1.大整数加法#include<iostream>#include<vector>usingnamespacestd;vector<int>add(vector<int>&A,vector<int>&B){ vector<int>C; intt=0; for(inti=0;i<A.size()||i<B.size();i......