【HDU1166】敌兵布阵(树状数组或线段树)

是一道树状数组的裸题,也可以说是线段树的对于单点维护的裸题。多做这种题目可以提高自己对基础知识的理解程度,很经典。

 #include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <string>
using namespace std; const int N = ;
int C[N]; struct peo {
int x, v;
}P[N]; int lowbit (int x) {
return x & -x;
} int sum (int x) {
int ret = ;
while (x > ) {
ret += C[x]; x -= lowbit(x);
}
return ret;
} void add (int x, int d) {
while (x <= ) {
C[x] += d; x += lowbit(x);
}
} int _sum (int d, int u) {
return sum(u) - sum(d - );
} int main () {
int T, n, cur = ; scanf("%d", &T);
char op[];
while (T --) {
memset(C, , sizeof(C));
memset(P, , sizeof(P));
scanf("%d", &n);
for (int i = ; i < n; ++ i) {
scanf("%d", &P[i].v);
P[i].x = i + ;
add (P[i].x, P[i].v);
}
//cout << sum(3) << endl;
printf("Case %d:\n", ++ cur);
while (scanf("%s", op)) {
if (op[] == 'E') {
break;
} else if (op[] == 'Q') {
int x, y;
scanf("%d %d", &x, &y);
cout << _sum(x, y) << endl;
} else if (op[] == 'S') {
int x, y;
scanf("%d %d", &x, &y);
add (x, -y);
} else if (op[] == 'A') {
int x, y;
scanf("%d %d", &x, &y);
add (x, y);
}
}
}
return ;
}
 #include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <numeric> using namespace std; struct P{
int sum, l, r;
} node[]; int n, num[] = {}; void build (int k, int l, int r) {
node[k].l = l, node[k].r = r;
if (l == r) {
node[k].sum = num[l];
} else {
build( * k, l, (l + r) / );
build( * k + , ((l + r) / ) + , r);
node[k].sum = node[ * k].sum + node[ * k + ].sum;
}
} void update(int k, int i, int x) {
if (node[k].l <= i && node[k].r >= i) {
node[k].sum += x;
}
if (node[k].l == node[k].r) {
return ;
}
if (i <= node[ * k].r) {
update( * k, i, x);
}
else update( * k + , i, x);
} int query (int k, int l, int r) {
if (l == node[k].l && r == node[k].r) {
return node[k].sum;
}
if (r <= node[ * k].r) {
return query( * k, l, r);
}
if (l >= node[ * k + ].l) {
return query( * k + , l, r);
} else {
return query( * k, l, node[ * k].r) + query( * k + , node[ * k + ].l, r);
}
} int main(){
int T;
scanf("%d",&T);
for (int z = ; z <= T; ++ z) {
memset(num, , sizeof(num));
scanf("%d", &n);
for (int i = ; i <= n; ++ i) {
scanf("%d",&num[i]);
}
build(, , n);
char s[];
printf("Case %d:\n",z);
while (scanf("%s", s)){
if (s[] == 'E') break;
if (s[] == 'Q'){
int a, b;
scanf("%d%d" ,&a ,&b);
printf("%d\n",query(, a, b));
}
if (s[] == 'A'){
int a,x;
scanf("%d%d", &a, &x);
update(, a, x);
}
if (s[] == 'S') {
int a,x;
scanf("%d%d", &a, &x);
update(, a, -x);
}
}
}
return ;
}
上一篇:浅谈:javascript的面向对象编程之基础知识的介绍


下一篇:FL Studio音频混音教程