《算法竞赛进阶指南》0x42 T2 A Tiny Problem with Integers

本文主要是介绍《算法竞赛进阶指南》0x42 T2 A Tiny Problem with Integers，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目传送门

题目描述

给定长度为 N N N 的数列 A A A，然后输入 M M M 行操作指令。
第一类指令形如 C C C l l l r r r d d d，表示把数列中第 l ∼ r l∼r l∼r 个数都加 d d d。
第二类指令形如 Q Q Q x x x，表示询问数列中第 x x x 个数的值。
对于每个询问，输出一个整数表示答案。

输入格式

第一行包含两个整数 N N N 和 M M M。
第二行包含 N N N 个整数 A [ i ] A[i] A[i]。
接下来 M M M 行表示 M M M 条指令，每条指令的格式如题目描述所示。

输出格式

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

数据范围

1 ≤ N , M ≤ 1 0 5 , 1≤N,M≤10^5, 1≤N,M≤105,
∣ d ∣ ≤ 10000 , |d|≤10000, ∣d∣≤10000,
∣ A [ i ] ∣ ≤ 1 0 9 |A[i]|≤10^9 ∣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

题解

显然是一道树状数组的板子题
对于每个点，通过树状数组记录它更改的值
用一个类似于差分的思想
将 x − n x-n x−n抬高一格，再将 y + 1 − n y+1-n y+1−n降低一格
就等价于将 x − y x-y x−y抬高一格
单点查询只需要将原数加上它改变过的值即可

code

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int n,a[N],c[N],m,maxn=-1;
void add(int x,int y)
{
	for(;x<=n;x+=x&-x) c[x]+=y;
}
int ask(int x)
{
	int ans=0;
	for(;x;x-=x&-x) ans+=c[x];
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
	{
		char x;
		scanf("%s",&x);
		if(x=='C')
		{
			int y,z,w;
			scanf("%d%d%d",&y,&z,&w);
			add(y,w);
			add(z+1,-w);
		}
		else
		{
			int y;
			scanf("%d",&y);
			printf("%d\n",a[y]+ask(y));
		}		
	}
	return 0;
}

这篇关于《算法竞赛进阶指南》0x42 T2 A Tiny Problem with Integers的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！