永利官方网站敌兵布阵,种种工兵营地的人数皆有不小或许产生更换


汇报:C国的死对头A国这段时光正在开展军事演练,所以C国间谍头子德里克和她手下Tidy又起来忙乎了。A国在海岸线沿直线安顿了N个工兵营地,德里克和Tidy的天职正是要监视这一个工兵营地的运动场馆。由于采用了某种先进的监测手段,所以每个工兵营地的食指C国都驾驭的明明白白,每一个工兵营地的总人口都有望发生变动,或许扩充或调整和裁减多少人手,但这一个都逃不过C国的监视。
核情绪报局要商量敌人毕竟演习什么战术,所以Tidy要每天向德里克陈诉某一段连接的工兵营地一共有稍许人,举个例子德里克问:“Tidy,立即上报第1个集散地到第11个营地共有几个人!”Tidy就要立时初步总结这一段的总人数并上报。但敌兵集散地的总人口平日退换,而德里克每回询问的段都不一样,所以Tidy不得不每一遍都贰个叁个驻地的去数,一点也不慢就疲倦了,德里克对Tidy的测算速度更是不满:”你个死肥仔,算得如此慢,我炒你八爪鱼!”Tidy想:“你本人来计量看,那可就是一项累人的行事!作者期盼你炒我章鱼呢!”万般无奈之下,Tidy只能打电话向Computer专家Windbreaker求救,Windbreaker说:“死肥仔,叫您常常做多点acm题和看多点算法书,今后尝到苦果了吗!”Tidy说:”笔者知错了。。。”但Windbreaker已经挂掉电话了。Tidy很烦恼,这么算他实在会崩溃的,聪明的读者,你能写个程序帮她达成那项工作呢?不过假设您的次第效能非常矮的话,Tidy还是会境遇德里克的责问的.

title: 敌兵布阵

输入:第一行三个整数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 代表甘休,那条命令在每组数据最后现身;
每组数据最多有50000条命令

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

难点链接

Problem Description

C国的死对头A国这段时光正在开展军事练习,所以C国间谍头子Derek和她手下Tidy又开首忙乎了。A国在海岸线沿直线安插了N个工兵营地,德里克和Tidy的任务正是要监视那么些工兵营地的运动情形。由于采用了某种先进的监测手腕,所以每一种工兵营地的食指C国都了解的一览无遗,每一个工兵营地的总人口都有望发生变动,大概扩大或调整和裁减几个职员,但那个都逃然则C国的监视。
核心理报局要斟酌仇人毕竟演练什么计谋,所以Tidy要天天向德里克陈说某一段连接的工兵营地一共有稍许人,譬喻德里克问:“Tidy,登时上报第一个营地到第13个集散地共有多少人!”Tidy将在立时起始计算这一段的总人数并反映。但敌兵营地的总人口平常改动,而德里克每一趟询问的段都不均等,所以Tidy不得不每回都四个贰个大学本科营的去数,异常快就疲倦了,Derek对Tidy的总括速度更是不满:”你个死肥仔,算得如此慢,小编炒你乌鱼永利官方网站,!”Tidy想:“你和煦来计量看,那可就是一项累人的干活!小编期盼你炒作者乌里黑呢!”无可奈何之下,Tidy只可以打电话向Computer专家Windbreaker求救,Windbreaker说:“死肥仔,叫您日常做多点acm题和看多点算法书,以往尝到苦果了吗!”Tidy说:”笔者知错了。。。”但Windbreaker已经挂掉电话了。Tidy很窝火,这么算他着实会崩溃的,聪明的读者,你能写个程序帮她完结那项职业吗?不过倘使您的主次效用相当的矮的话,Tidy依然会遭逢德里克的呵斥的.

 

Input

率先行贰个子弹头T,表示有T组数据。
每组数据第一行一个正整数N(N<=60000),表示敌人有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 表示截止,那条命令在每组数据最后出现;
每组数据最多有60000条命令

 

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];

今昔用叁个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的岗位 就是1000,十进制正是8 那么
sum[8]=a[8]+a[7]+a[6]+a[5]+a[4]+a[3]+a[2]+a[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 }

 

相关文章