各种工兵营地的食指都有恐怕产生变动,敌兵布阵


讲述:C国的死对头A国那段日子正在进展军事演习,所以C国间谍头子德里克和他手下Tidy又起来忙乎了。A国在海岸线沿直线布署了N个工兵集散地,德里克和Tidy的职务正是要监视那些工兵集散地的移动状态。由于接纳了某种先进的监测手段,所以每个工兵基地的人口C国都控制的一清二楚,每一种工兵营地的食指都有恐怕爆发变更,或者扩张或回落几个人口,但这一个都逃然而C国的监视。
核心理报局要切磋仇人毕竟练习什么战术,所以Tidy要随时向德里克汇报某一段连接的工兵营地一共有稍许人,例如德里克问:“Tidy,立即上报第四个营地到第⑩个集散地共有多少人!”Tidy就要立即起首总结这一段的总人数并申报。但敌兵集散地的总人口平时改变,而德里克每一次询问的段都不均等,所以Tidy不得不每趟都二个3个驻地的去数,非常的慢就疲劳了,德里克对Tidy的估测计算速度越来越不满:”你个死肥仔,算得那般慢,小编炒你鱿鱼!”Tidy想:“你协调来测算看,那可便是一项累人的办事!笔者渴望你炒作者鱿鱼呢!”无奈之下,Tidy只能打电话向电脑专家Windbreaker求救,Windbreaker说:“死肥仔,叫你平时做多点acm题和看多点算法书,现在尝到苦果了呢!”Tidy说:”笔者知错了。。。”但Windbreaker已经挂掉电话了。Tidy很窝心,这么算他着实会崩溃的,聪明的读者,你能写个程序帮他实现那项工作吧?不过只要您的主次效能非常的矮的话,Tidy依旧会受到德里克的责骂的.

title: 敌兵布阵

输入:第①行八个平头T,表示有T组数据。
每组数据第①行3个正整数N(N<=50000),表示敌人有N个工兵营地,接下去有N个正整数,第i个正整数ai代表第i个工兵集散地里开始时有ai个人(1<=ai<=50)。
接下去每行有一条命令,命令有4种方式:
(1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30)
(2)Sub i j ,i和j为正整数,表示第i个营地收缩j个人(j不超越30);
(3)Query i j ,i和j为正整数,i<=j,表示了然第i到第j个营地的总人数;
(4)End 代表停止,那条命令在每组数据最后出现;
每组数据最多有四千0条命令

tags: [线段树,树状数组]

题材链接

Problem Description

C国的死对头A国这段时光正在进展军事练习,所以C国间谍头子Derek和她手下Tidy又起来忙乎了。A国在海岸线沿直线安顿了N个工兵营地,Derek和Tidy的天职正是要监视那个工兵营地的移动地方。由于使用了某种先进的监测手段,所以各种工兵营地的人口C国都控制的一五一十,每一种工兵营地的食指都有大概发生转移,也许扩大或缩短几个人手,但这个都逃可是C国的监视。
宗旨绪报局要研究仇敌究竟演练什么战术,所以Tidy要时时向Derek汇报某一段连接的工兵营地一共有个别许人,例如Derek问:“Tidy,即刻上报第一个驻地到第8个驻地共有几人!”Tidy就要及时初步盘算这一段的总人数并报告。但敌兵集散地的人数平常转移,而德里克每回询问的段都不同,所以Tidy不得不每趟都一个三个营地的去数,非常的慢就疲劳了,德里克对Tidy的乘除速度越来越不满:”你个死肥仔,算得这么慢,笔者炒你鱿鱼!”Tidy想:“你协调来计量看,那可正是一项累人的行事!小编期盼你炒作者鱿鱼呢!”无奈之下,Tidy只能打电话向电脑专家Windbreaker求救,Windbreaker说:“死肥仔,叫你日常做多点acm题和看多点算法书,今后尝到苦果了呢!”Tidy说:”小编知错了。。。”但Windbreaker已经挂掉电话了。Tidy很闹心,这么算他着实会崩溃的,聪明的读者,你能写个程序帮她达成这项工作啊?然而只要您的先后功能非常矮的话,Tidy仍然会遭到德里克的责骂的.

 

Input

率先行1个平头T,表示有T组数据。
每组数据第三行一个正整数N(N<=四千0),表示仇敌有N个工兵集散地,接下去有N个正整数,第i个正整数ai代表第i个工兵集散地里初叶时有ai个人(1<=ai<=50)。
接下去每行有一条命令,命令有4种形式:

(1) Add i j,i和j为正整数,表示第i个驻地扩张j个人(j不超过30)
(2)Sub i j ,i和j为正整数,表示第i个集散地裁减j个人(j不超过30);
(3)Query i j ,i和j为正整数,i<=j,表示精晓第i到第j个集散地的总人数;
(4)End 代表结束,那条命令在每组数据最后现身;
每组数据最多有四千0条命令

 

Output

对第i组数据,首先输出“Case i:”和回车,
对于各样Query询问,输出多少个整数并回车,表示了然的段中的总人数,那些数保持在int以内。

 

Sample Input

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End 

 

Sample Output

Case 1:
6
33
59

出口:对第i组数据,首先输出“Case
i:”和回车,对于每一种Query询问,输出二个整数并回车,表示精通的段中的总人数,那几个数保持在int以内。

分析

那道题能够用线段树来解,只需把区间求最大值得越发代码稍加改动就行。那里最主要讲树状数组的写法,

树状数组的经文应用:区间求和,

有如下数组:a []= [ 1, 2, 3, 4, 5, 6, 7, 8, 9,10];

现今用1个sum[]来保存如下的音信,至于为什要如此保存,请继续往下看

sum[1] = a[1];
sum[2] = a[1] + a[2];
sum[3] = a[3];
sum[4] = a[1] + a[2] + a[3] + a[4];
sum[5] = a[5];
sum[6] = a[5] + a[6];
sum[7] = a[7];
sum[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8];
sum[9] = a[9];

那时sum数组正是其一树状数组了,sum[x]封存的是从下标x初阶a[x]+a[x-1]+a[x-2]+a[x-k]
,至于有多少个a[]相加,那里有三个测算形式,把x化为二进制,从右向左找到第三个1的职位,那几个地方所代表的十进制的数字k就代表sum[x]=a[x]+a[x-1]+a[x-2]+…+a[x-k-1];

假若x=6 把6化为二进制:110 ,从右向左找到第二个1的地方 正是 10
,十进制正是2: sum[6]=a[6]+a[5]

只要x=8 的二进制是一千 ,从右向左找到第1个1的职位 正是一千,十进制正是8 那么
sum[8]=a[8]+a[7]+a[6]+a[5]+a[4]+a[3]+a[2]+a[1];

设若用1个函数lowbit(int x)来贯彻 lowbit(6)=2 lowbit(8)=8
的成效,那么对于sum[x] 他的求和

区间是(x-lowbit(x),x];

图片 1

如图: c[4]的父节点是c[8] c[8]=4+lowbit(4);

lowbit(int x)函数可写成

int lowbit(int x)
{
    return x&(-x);
}

确立树状数组

void Build(int n)
{
    for (int i=1; i<=n; i++)
        for (int j=i; j>=i-lowbit(i)+1; j--)
            build[i]+=a[j];
}

更新树状数组

void update(int id,int value)
{
    for (int i=id; i<=MAX; i+=lowbit(i))//i+=lowbit(i)得到的是i的父节点
        build[i]+=value;
}

求和(从1到n的和)

int SUM(int n)
{
    int sum=0;
    for (int i=n; i>0; i-=lowbit(i))//i-=lowbit(i) 得到是i的子节点
        sum+=build[i];
    return sum;
}

input:

代码

#include<bits/stdc++.h>
using namespace std;
const int MAX=50000+50;
int a[MAX];
int build[MAX];
int lowbit(int x)
{
    return x&(-x);
}
void Build(int n)
{
    for (int i=1; i<=n; i++)
        for (int j=i; j>=i-lowbit(i)+1; j--)
            build[i]+=a[j];
}
int SUM(int n)
{
    int sum=0;
    for (int i=n; i>0; i-=lowbit(i))
        sum+=build[i];
    return sum;
}
void update(int id,int value,int n)
{
    for (int i=id; i<=n; i+=lowbit(i))
        build[i]+=value;
}
int main()
{

    //freopen("1.txt","r",stdin);
    int t,k=1;
    scanf("%d",&t);
    while (k<=t)
    {
        memset(a,0,sizeof(a));
        memset(build,0,sizeof(build));
        int n;
        scanf("%d",&n);
        for (int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        Build(n);
        char c[10];
        int a,b;
        printf("Case %d:\n",k);
        while (1)
        {
            scanf(" %s",c);
            if (strcmp(c,"End")==0)
                break;
            scanf("%d%d",&a,&b);
            if (strcmp(c,"Query")==0)
            {
                printf("%d\n",SUM(b)-SUM(a-1));
            }
            else  if (strcmp(c,"Add")==0)
            {
                update(a,b,n);
            }
            else  if (strcmp(c,"Sub")==0)
            {
                update(a,-1*b,n);
            }

        }
        k++;

    }

    return 0;
}

  1

  10

  1 2 3 4 5 6 7 8 9 10

  Query 1 3

  Add 3 6

  Query 2 7

  Sub 10 2

  Add 6 3

  Query 3 10

  End

 

output:

  Case 1:

  6

  33

  59

剖析:本题难题在于对多量数码求和的题材,若是老是用循环求和必定会超时,那里就须求用到树状数组,树状数组专门用来大气数据的拍卖。另一篇博文仲对树状数组做详细表达,那里只交给代码。

 1 #include<iostream>
 2 #include<stdio.h>            //用scanf读入效率更高,用cin依旧会超时 
 3 #include<string.h>
 4 using namespace std;
 5 
 6 static int a[50014],b[50014],N;
 7 int lowbit(int t)     //求该点管辖范围 
 8 {
 9     return t&(-t);
10 }
11 void upDate(int x,int num)  //修改树状数组 
12 {
13     while(x<=N)
14     {
15         b[x]+=num;
16         x+=lowbit(x); 
17     }
18 }
19 int getSum(int x)        //求0-x的和 
20 {
21     int s=0;
22     while(x>0)
23     {
24         s+=b[x];
25         x-=lowbit(x); 
26     } 
27     return s;
28 } 
29 
30 int main()
31 {
32     int n, num;
33     scanf("%d",&n);
34     for(int i=0;i<n;i++)
35     {
36         cout<<"Case "<<i+1<<":"<<endl;
37         scanf("%d",&num);N=num;
38         for(int i=1;i<=num;i++) 
39             b[i]=0;
40         for(int i=1;i<=num;i++)        //建立树状数组b[]
41         {
42             scanf("%d",&a[i]);
43             upDate(i, a[i]);
44         }
45         char str[10]; 
46         while((scanf("%s",str))&&(strcmp(str,"End")))
47         {
48             int i,j;
49             scanf("%d%d", &i, &j);
50             switch(str[0])
51             {
52                 case'A':upDate(i,j);break;
53                 case'S':upDate(i,-j);break;
54                 case'Q':cout<<getSum(j)-getSum(i-1)<<endl;break;
55             }
56         }
57     }
58     return 0;
59 }