Problem Description
C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:"你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说："我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.
第二次尝试
// hdu1166c.cpp : Defines the entry point for the console application.
//
#include "stdafx.h" //这里是vs加的，评判时要把这里去掉
#include<iostream>
#include<string> //c++与g++不同，g++要把这里改成string.h,不然里面没有memset
#include<cstdio>
using namespace std;
const int MAX_LENGTH = 70001;
int a[MAX_LENGTH];
int c[MAX_LENGTH];
int N;
int getSum(int index){
int sum = 0;
while (index>0)
{
sum += c[index];
index -= index&-index;
}
return sum;
}
void update(int index, int addNum)
{
c[index] += addNum;
while (index<N+1)
{
index += index&-index;
c[index] += addNum;
}
}
void init(){
for (int i = 0; i < N; i++)
{
update(i + 1, a[i + 1]); //前提是所有c都为0
}
}
int _tmain(int argc, _TCHAR* argv[]) //oj评判这里会有问题
{
int T,m,n,result;
string command;
scanf("%d", &T);
for (int i = 0; i < T; i++)
{
scanf("%d", &N);
memset(c, 0, sizeof(int) * (N+1));//别太关注调试，想想哪里出问题了看代码，多个样例，初始化一定要注意
for (int j = 0; j < N; j++)
{
scanf("%d", &a[j + 1]);//树状数组一定要从1开始
}
init();
printf("Case %d:\n", i + 1); //换行
while (cin>>command)
{
if (command[0] == 'E') break;
scanf("%d %d", &m, &n);//
switch (command[0]-'A')
{
case 'A'-'A':
update(m, n);
break;
case 'S' - 'A':
update(m, -n);
break;
case 'Q' - 'A':
result = getSum(n) - getSum(m - 1);
printf("%d\n", result);
break;
default:
break;
}
}
}
return 0;
}
第一次尝试
#include <cstdio>
#include <string> //cstring,string中在G++中不包含memset
#include <iostream>
using namespace std;
const int MAX_LENGTH = 70002;
int a[MAX_LENGTH];
int c[MAX_LENGTH];
int N;
int getSum(int i){
int sum = 0;
while (i>0)
{
sum += c[i];
i -= (i&-i);
}
return sum;
}
void update(int index, int addNum){
c[index] += addNum;
while (index<=N)
{
index += (index&-index);
c[index] += addNum;
}
}
void init(){
for (int i = 1; i <= N; i++) //由于从1开始，for又是系统生成，下标很容易错
{
update(i, a[i]);
}
}
int main(){
int T,m,n;
scanf("%d", &T);
string command;
for (int i = 1; i <= T; i++) //i一定要从1开始
{
scanf("%d", &N);
memset(c, 0, sizeof(int)*(N + 2));
for (int i = 1; i <= N; i++)
{
scanf("%d", &a[i]);
}
printf("Case %d:\n",i); //Case 这里不能忘了
init();
while (cin>>command)
{
if (command == "End") break;
scanf("%d", &m); //竟然是这里出错了。。。输入输出太多。。。End后面不读取数字
scanf("%d", &n);
if (command == "Add") update(m, n);
if (command == "Sub") update(m, -n);
if (command == "Query") {
int result=getSum(n)-getSum(m - 1);
printf("%d\n", result);
}
}
}
return 0; //vs不会自动生成，这句不能忘
}
线段树（非递归实现，叶子节点全在最底层）
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
using namespace std;
#define lson root <<1, left, mid
#define rson root << 1 | 1, mid + 1, right
#define lsonu left, mid ,root <<1
#define rsonu mid + 1, right,root << 1 | 1
const int MAX_LEGTH =70000 ;
int c[MAX_LEGTH<<2];//这里忘了开辟4倍内存空间，导致总是TimeLimitExceed，浪费了n多时间
int N,LowN;
int Sum;
void init(){
LowN = 1;
while (LowN<N)
{
LowN = LowN << 1;
}
for (int i = 0; i < N; i++)
{
scanf("%d", &c[LowN + i]);//从1开始读，最底层LowN开始
}
int start = (LowN + N) >> 1, end = LowN >> 1;
while (start>0)
{
for (int i = start; i >end - 1; i--)
{
c[i] = c[i << 1] + c[i << 1 | 1];
}
start >>= 1;
end >>= 1;
}
}
void update(int index, int addVal){
int k = LowN - 1 + index;
while (k>0)//注意顺序和退出条件
{
c[k] += addVal;
k /= 2;
}
}
void query(int root, int a, int b, int left, int right){//right对不同的组织方式含义不同
if (a > right || b < left) return;
if (left >= a&&right <= b) {
Sum += c[root];
return;//表示当前节点的全部都在查询范围中
}
else
{
int mid = (left + right) / 2;
query(root << 1, a, b, left, mid);
query(root << 1 | 1, a, b, mid + 1, right);//右子树，找最简单的1234调试得来
}
}
void print(){
int num = 1, location = 1;
for (int i = 0; i < 2 * LowN - 1; i++)
{
if (i == location){
num *= 2;
location += num;
printf("\n");
}
printf("%d ", c[i + 1]);
}
}
int main(){
int T;
scanf("%d", &T);
for (int i = 0; i < T; i++)
{
scanf("%d", &N);
init();
char command[10];
printf("Case %d:\n", i + 1);
while (scanf("%s",command))
{
if (command[0] == 'E') break;
int A, B;
scanf("%d %d", &A, &B);
if (command[0] == 'A'){
update(A, B);
}
if (command[0] == 'S'){
update(A, -B);
}
if (command[0] == 'Q'){
Sum = 0;
query(1, A, B,1, LowN);
printf("%d\n", Sum);
}
}
}
return 0;
}
线段树（递归实现，叶子节点在最底层以及倒数第二层）
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
using namespace std;
#define lson root <<1, left, mid
#define rson root << 1 | 1, mid + 1, right
#define lsonu left, mid ,root <<1
#define rsonu mid + 1, right,root << 1 | 1
const int MAX_LEGTH =70000 ;
int c[MAX_LEGTH<<2];
int N,LowN;
int Sum;
void init(int root,int left,int right){
if (left == right) scanf("%d", &c[root]);
else
{
int mid = (left + right) /2;
init(lson);
init(rson);
c[root] = c[root << 1] + c[root <<1 | 1];
}
}
void print(int root, int left, int right){
if (left == right) printf("%d ", c[root]);
else
{
int mid = (left + right) / 2;
print(root << 1, left, mid);
print(root << 1 | 1, mid + 1, right);
}
}
void update(int index,int addVal,int left,int right,int root){
if (left == right) c[root] += addVal;
else{
int mid = (left + right) / 2;
if (index <= mid) update(index, addVal, lsonu);
else update(index, addVal, rsonu);
c[root] = c[root << 1] + c[root << 1 | 1];
}
}
void query(int a, int b, int root, int left, int right){
if (a > right || b < left) return;
if (left >= a&&right <= b) {
Sum += c[root];
return ;//表示当前节点的全部都在查询范围中
}
else
{
int mid = (left + right) / 2;
if(a<=mid) query( a, b, lson);
if(b>mid)query( a, b, rson);//右子树，找最简单的1234调试得来
}
}
int main(){
int T;
scanf("%d", &T);
for (int i = 0; i < T; i++)
{
scanf("%d", &N);
init(1,1,N);
char command[10];
printf("Case %d:\n", i + 1);
while (scanf("%s",command))
{
if (command[0] == 'E') break;
int A, B;
scanf("%d %d", &A, &B);
if (command[0] == 'A'){
update(A, B, 1, N, 1);
}
if (command[0] == 'S'){
update(A, -B, 1, N, 1);
}
if (command[0] == 'Q'){
Sum = 0;
query( A, B,1, 1, N);
printf("%d\n", Sum);
}
}
}
return 0;
}
网友评论