AcWing242. 一个简单的整数问题()
给定长度为N的数列A,然后输入M行操作指令。
第一类指令形如“C l r d”,表示把数列中第l~r个数都加d。
第二类指令形如“Q X”,表示询问数列中第x个数的值。
对于每个询问,输出一个整数表示答案。
输入格式
第一行包含两个整数N和M。
第二行包含N个整数A[i]。
接下来M行表示M条指令,每条指令的格式如题目描述所示。
输出格式
对于每个询问,输出一个整数表示答案。
每个答案占一行。
数据范围
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<algorithm> #include<vector> #include<utility> #include<deque> #include<unordered_map> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 100010; int n, m; int a[N], tr[N]; void add(int x, int c) { for (int i = x;i <= n;i += lowbit(i))tr[i] += c; } LL sum(int x) { LL res = 0; for (int i = x;i;i -= lowbit(i))res += tr[i]; return res; } int main() { scanf("%d%d", &n, &m); for (int i = 1;i <= n;++i)scanf("%d", &a[i]); for (int i = 1;i <= n;++i)add(i, a[i] - a[i - 1]); while (m--) { char op[2]; int l, r, d; scanf("%s%d", op, &l); if (op[0] == 'C') { scanf("%d%d", &r, &d); add(l, d), add(r + 1, -d); } else { printf("%lld\n", sum(l)); } } return 0; }