读《思想道德修养与法律基础》


图片 1

title: 敌兵布阵

敬服博士活,开辟新的程度,大家大学生是国家的人才财富,是名族的想望,祖国的以后,担当着人民的重托,历史的责任。大学生的读书生涯,是人生发掘的首要等第,是世界观、人生观、价值观造成的关键时代。

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

主题材料链接

Problem Description

C国的死对头A国这段时光正在进展军事练习,所以C国间谍头子Derek和他手下Tidy又起来忙乎了。A国在海岸线沿直线布署了N个工兵营地,德里克和Tidy的天职正是要监视这一个工兵营地的移位场合。由于使用了某种先进的监测花招,所以每种工兵集散地的人头C国都调节的一五一10,每一种工兵集散地的人口都有希望产生转移,可能扩展或收缩几人手,但这么些都逃不过C国的监视。
中心境报局要切磋仇人毕竟演练什么战术,所以Tidy要时刻向Derek汇报某一段连接的工兵基地1共有个别许人,比方德里克问:“Tidy,立即上报第叁个集散地到第十个集散地共有几人!”Tidy将要及时发轫妄图那壹段的总人数并申报。但敌兵集散地的总人口日常改换,而德里克每便询问的段都不雷同,所以Tidy不得不每回都一个二个本部的去数,异常的快就疲倦了,德里克对Tidy的测算速度更是不满:”你个死肥仔,算得那样慢,作者炒你鱿鱼!”Tidy想:“你协和来总括看,那可真是1项累人的做事!我心向往之你炒小编鱿鱼呢!”无奈之下,Tidy只能打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥仔,叫您日常做多点acm题和看多点算法书,未来尝到苦果了吗!”Tidy说:”作者知错了。。。”但Windbreaker已经挂掉电话了。Tidy很搅扰,这么算他确实会崩溃的,聪明的读者,你能写个程序帮他做到这项专门的学问呢?可是假使你的程序作用非常的矮的话,Tidy依旧会惨遭德里克的责难的.

 

Input

首先行2个整数T,表示有T组数据。
每组数据第2行3个正整数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);
(三)Query i j ,i和j为正整数,i<=j,表示领悟第i到第j个集散地的总人数;
(肆)End 表示停止,这条命令在每组数据最后出现;
每组数据最多有50000条命令

 

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

图片 2

分析

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

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

有如下数组: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化为贰进制,从右向左找到第二个一的职位,那些职位所表示的10进制的数字k就象征sum[x]=a[x]+a[x-1]+a[x-2]+…+a[x-k-1];

倘使x=陆 把陆化为二进制:1拾 ,从右向左找到第2个一的岗位 正是 十,拾进制正是2: sum[6]=a[6]+a[5]

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

一经用1个函数lowbit(int x)来落到实处 lowbit(6)=二 lowbit(捌)=8的意义,那么对于sum[x] 他的求和

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

图片 3

如图: 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;
}

送别了中学生活,迈进大高校门,生活到了3个新的生活,新的品级,莘莘学子满怀希望和恋慕。

代码

#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;
}

图片 4

高档高校生涯是大家都期盼的,不过当大家到了高校的校门时,大家会经受新的良师、新的学生,还要接受新的情况。在这几个处处充满活力的学校,大家得以在此处大展身手,能够在此处把大家在初春天高中没有显示出来的才具统统都突显出来。

图片 5

在高校生涯中,大家进去了这么些小社会,大家要到位大多的社会活动,进入大学后,党组织、团组织、学生会、班级委员会等协会活动日增,同学们方可依靠自身的表征和喜好,时间和生命力,积极参与各类运动,合理安插自身的课余时间,训练集体和接触才具,也是对团结本事的1种必然。

图片 6

可是在大家的那些高校中,我们的同校在上政治课时大家都以在玩手提式有线电话机,睡觉,还有的在1道聊天,并且聊的相当的慢意,丰富多彩的事都有,那就是我们的大学生,大家还有如何可抱怨的了,当我们到全校时,大家抱怨学校倒霉,专门的学业糟糕等,可是大家都不从友好的随身找原因,来了说那倒霉,那倒霉,大家要思索我们怎么来此处,只因为大家那儿未曾好好学习,今后还想学一门技能,大家便是因为如此的心态来到了此间,大家既然来了,那就白玉无瑕发挥大家的后天。

笔者们欢聚一堂在此间是机缘,俗话说得好,有缘千里来会见,无缘对面不相逢,正是因为这么的姻缘,所以我们在那里共聚,大家都平等,未有怎么分歧的,分裂的就是大家后天的拼命,大家的大团圆,正是大家的缘分,便是大家在后头的互联,我们的明天会越来越好。

图片 7

图片 8

发表评论

电子邮件地址不会被公开。 必填项已用*标注