网站质量需求,做框架模板的网站,竞价推广渠道,建设银行官网站查询Problem A 发布时间: 2017年6月28日 09:29 最后更新: 2017年6月28日 13:03 时间限制: 1000ms 内存限制: 32M 描述 给定一个长度为n的序列a1, a2, ..., an给出q个操作, 操作分为两种 对于形如1xyz的操作, 将下标介于[x,y]的元素加上z, 满足1≤x≤y≤n, 1≤z≤105对于形如2… Problem A 发布时间: 2017年6月28日 09:29 最后更新: 2017年6月28日 13:03 时间限制: 1000ms 内存限制: 32M 描述 给定一个长度为n的序列a1, a2, ..., an 给出q个操作, 操作分为两种 对于形如1 x y z的操作, 将下标介于[x,y]的元素加上z, 满足1≤x≤y≤n, 1≤z≤105 对于形如2 x的操作, 输出ax, 满足1≤x≤n 9×104≤n≤105, 9×104≤q≤105, 1≤ai≤105 输入 第一行两个整数n, q, 意义如上所述。 第二行n个整数, 表示序列a。 接下来q行, 每行第一个数为opt, 如果opt1, 则后面紧跟三个数, 意义如上所述; 如果opt2, 则后面紧跟一个数, 意义如上所述。 输出 对于所有操作2, 输出答案, 一行一个。 样例输入1 8 3
3 1 4 1 5 9 2 6
2 3
1 2 3 6
2 3 样例输出1 4
10 题解
由于树状数组的求和功能是可以在LOG(N)的时间复杂度内完成现在我们考虑把求某一个点的值划归到求某一段区间和的问题这样我们就可以构造序列
b[i] a[i] - a[i-1],b[1] a[i]
这样的话如果我要把某段区间[l,r]的值增加val,那么我只需要把b[l]增加val然后b[r1]减去val,就可以了
代码 #include iostream
#include cstdio
using namespace std;
#define int long long
const int MAX 1e57;
int a[MAX];
int b[MAX];
int n,q;
int lowbit(int x){return x(-x);
}
int sum(int pos){int ans 0;while(pos){ans b[pos];pos - lowbit(pos);}return ans;
}
void add(int pos,int val){while(pos n){b[pos] val;pos lowbit(pos);}
}
main(){scanf(%lld%lld,n,q);for(int i 1;i n;i){scanf(%lld,a[i]);add(i,a[i]-a[i-1]);}while(q--){int op;scanf(%lld,op);if(op 1){int a,b,c;scanf(%lld%lld%lld,a,b,c);add(a,c);add(b 1,-c);}else{int a;scanf(%lld,a);printf(%lld\n,sum(a));}}return 0;
}
