敌兵布阵 HDU-1166

参见https://blog.csdn.net/flushhip/article/details/79165701

https://blog.csdn.net/forever_kirito/article/details/78694203 

//树状数组

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
#define lowbit(x) (x&(-x)) //计算2^k
const int Max = 50000+5;
int c[Max];//c[i] = a[i – 2^k + 1] + … + a[i]，k为i在二进制下末尾0的个数
void Update(int x, int y, int MAX)
{
while(x <= MAX){
c[x] += y;
x += lowbit(x);
}
}
int Sum(int x)
{
int sum = 0;
while(x > 0){
sum += c[x];
x -= lowbit(x);
}
return sum;
}
void SumSQ(int y, int x)
{
int sum = 0;
while(y > 0){
sum += c[y];
y -= lowbit(y);
}
while(x > 0){
sum -= c[x];
x -= lowbit(x);
}
//	cout << sum << endl;
printf("%dn", sum);
}
int main()
{
int T, cnt = 1;
string s;
//cin >> T;
scanf("%d", &T);
while(T--){
int N;
//	cin >> N;
scanf("%d", &N);
memset(c, 0, sizeof(c));
for(int i=1; i<=N; i++){
int x;
//	cin >> x;
scanf("%d", &x);
Update(i, x, N);
}
//
cout << "Case " << cnt++ << ":" << endl;
printf("Case %d:n", cnt++);
//
while(cin >> s && s != "End"){
while(cin >> s && s != "End"){
int x, y;
//
cin >> x >> y;
scanf("%d%d", &x, &y);
if(s == "Add"){
Update(x, y, N);
}
else if(s == "Sub"){
Update(x, -y, N);
}
else if(s == "Query"){
SumSQ(y, x-1);
//
cout << Sum(y)-Sum(x-1) << endl;
}
}
}
return 0;
} 

线段树  //有个比较坑的就是结构体数组的大小问题，，，如果小了的话RE，觉得2倍就可以了，，，结果是TLE。。。。开了3倍或者4倍就过了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//const int INF = 0x3f3f3f3f;
//const int MOD = 1000000007;
#define LL long long
#define MAXN 50010
struct Node
{
int l, r, val;
}t[MAXN*3];
int ans, c[MAXN];
void Build(int x, int y, int num)
{
t[num].l = x;
t[num].r = y;
if(x == y) t[num].val = c[y];
else
{
int mid = (x+y) >> 1;
Build(x, mid, num*2);
Build(mid+1, y, num*2+1);
t[num].val = t[num*2].val + t[num*2+1].val;
}
}
void Add(int x, int y, int num)
{
if(t[num].l == x && t[num].r == x)
{
t[num].val += y;
return ;
}
int mid = (t[num].l + t[num].r) >> 1;
if(x > mid)
Add(x, y, num*2+1);
else
Add(x, y, num*2);
t[num].val = t[num*2].val + t[num*2+1].val;
}
void Query(int x, int y, int num)
{
if(t[num].l == x && t[num].r == y)
{
ans += t[num].val;
return ;
}
int mid = (t[num].l+t[num].r)>>1;
if(y <= mid)
Query(x, y, num*2);
else if(x >= mid+1)
Query(x, y, num*2+1);
else {
Query(x, mid, num*2);
Query(mid+1, y, num*2+1);
}
}
int main()
{
int T, n;
char str[6];
scanf("%d", &T);
for(int i=1; i<=T; i++)
{
int x, y;
scanf("%d", &n);
memset(c, 0, sizeof(c));
for(int j=1; j<=n; j++)
scanf("%d", &c[j]);
Build(1, n, 1);
printf("Case %d:n", i);
while(~scanf("%s", str))
{
if(strcmp(str, "End")==0)
break;
else if(strcmp(str, "Add")==0)
{
scanf("%d%d", &x, &y);
Add(x, y, 1);
}
else if(strcmp(str, "Sub")==0)
{
scanf("%d%d", &x, &y);
Add(x, -y, 1);
}
else if(strcmp(str, "Query") == 0)
{
scanf("%d%d", &x, &y);
ans = 0;
Query(x, y, 1);
printf("%dn", ans);
}
}
}
return 0;
}

最后

以上就是健壮蜜粉为你收集整理的敌兵布阵 HDU-1166的全部内容，希望文章能够帮你解决敌兵布阵 HDU-1166所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。