概述
1166 敌兵布阵
题解
单点更新,区间查询。
线段树:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define Avg(x, y) ((x & y) + ((x ^ y) >> 1))
const int maxn = 50000 + 5;
int tree[3 * maxn];
int n, t;
void build(int l, int r, int num){
if(l == r){
scanf("%d", &tree[num]);
return;
}
int mid = Avg(l, r);
build(l, mid, num << 1);
build(mid + 1, r, num << 1 | 1);
tree[num] = tree[num << 1] + tree[num << 1 | 1];
}
void update(int l, int r, int num, int pos, int val){
if(l == r){
tree[num] += val;
return;
}
int mid = Avg(l, r);
if(pos <= mid) update(l, mid, num << 1, pos, val);
else update(mid + 1, r, num << 1 | 1, pos, val);
tree[num] = tree[num << 1] + tree[num << 1 | 1];
}
int query(int l, int r, int L, int R, int num){
if(L <= l && r <= R) return tree[num];
int mid = Avg(l, r);
int ret = 0;
if(L <= mid) ret += query(l, mid, L, R, num << 1);
if(R > mid) ret += query(mid + 1, r, L, R, num << 1 | 1);
return ret;
}
int main(){
#ifdef EXMY
freopen("data.in", "r", stdin);
#endif // EXMY
scanf("%d", &t);
for(int Case = 1; Case <= t; ++Case){
printf("Case %d:n", Case);
memset(tree, 0, sizeof(tree));
scanf("%d", &n);
build(1, n, 1);
char op[10];
int x, y;
while(scanf("%s", op) && op[0] != 'E'){
if(op[0] == 'A'){
scanf("%d %d", &x, &y);
update(1, n, 1, x, y);
}
else if(op[0] == 'S'){
scanf("%d %d", &x, &y);
update(1, n, 1, x, -y);
}
else if(op[0] == 'Q'){
scanf("%d %d", &x, &y);
printf("%dn", query(1, n, x, y, 1));
}
}
}
return 0;
}
树状数组:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 50000 + 5;
int n, t;
int c[maxn];
int lowbit(int x) {
return x & -x;
}
void add(int x, int v) {
for(int i = x; i <= n; i += lowbit(i))
c[i] += v;
}
int sum(int x) {
int s = 0;
for(int i = x; i ; i -= lowbit(i))
s += c[i];
return s;
}
int main() {
#ifdef EXMY
freopen("data.in", "r", stdin);
#endif // EXMY
scanf("%d", &t);
for(int Case = 1; Case <= t; ++Case){
printf("Case %d:n", Case);
memset(c, 0, sizeof(c));
scanf("%d", &n);
int a;
for(int i = 1; i <= n; ++i){
scanf("%d", &a);
add(i, a);
}
char op[10];
int x, y;
while(scanf("%s", op) && op[0] != 'E'){
if(op[0] == 'A'){
scanf("%d %d", &x, &y);
add(x, y);
}
else if(op[0] == 'S'){
scanf("%d %d", &x, &y);
add(x, -y);
}
else if(op[0] == 'Q'){
scanf("%d %d", &x, &y);
printf("%dn", sum(y) - sum(x - 1));
}
}
}
return 0;
}
最后
以上就是眼睛大小土豆为你收集整理的hdoj--1166 敌兵布阵(树状数组or线段树)的全部内容,希望文章能够帮你解决hdoj--1166 敌兵布阵(树状数组or线段树)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复