澳门威利斯人_威利斯人娱乐「手机版」

来自 网络资讯 2019-11-16 06:11 的文章
当前位置: 澳门威利斯人 > 网络资讯 > 正文

威尼斯娱乐手机版网站单点更新线段树

hdu 1166 敌兵布阵(单点更新线段树)

敌兵布阵

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 54411 Accepted Submission(s): 22830

Problem Description C国的死对头A国这段时光正在开展军事演练,所以C国线人头子德里克和她手下Tidy又开头忙乎了。A国在海岸线沿直线铺排了N个工兵营地,德里克和Tidy的职分正是要监视那一个工兵营地的运动状态。由于选用了某种先进的监测手腕,所以各样工兵营地的食指C国都通晓的千古留名,每一种工兵集散地的总人口都有希望产生转移,大概扩充或减少多少个职员,但那个都逃可是C国的监视。
主旨境报局要切磋仇敌究竟练习什么计策,所以Tidy要每一天向德里克陈述某大器晚成段连接的工兵营地一共有稍许人,比方Derek问:“Tidy,立时上报第二个集散地到第11个集散地共有几个人!”Tidy将要登时在这里以前计算那风华正茂段的总人数并报告。但敌兵集散地的食指平常转移,而德里克每回询问的段都不等同,所以Tidy一定要每趟都一个叁个驻地的去数,一点也不慢就疲劳了,Derek对Tidy的乘除速度更加的不满:"你个死肥仔,算得那般慢,作者炒你生鱼!”Tidy想:“你和睦来测算看,那可便是风姿洒脱项累人的办事!笔者渴望你炒笔者墨鱼呢!”万般无奈之下,Tidy只能打电话向计算机行家Windbreaker求救,Windbreaker说:“死肥仔,叫您日常做多点acm题和看多点算法书,现在尝到苦果了啊!”Tidy说:"作者知错了。。。"但Windbreaker已经挂掉电话了。Tidy很忧虑,这么算他实在会崩溃的,聪明的读者,你能写个程序帮他成就那项工作吗?然而假若你的主次功能非常的矮的话,Tidy还是会碰到德里克的挑剔的.

Input 第大器晚成行三个整数T,表示有T组数据。
每组数据第意气风发行二个正整数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 表示截止,那条命令在每组数据最后现身;
每组数据最多有40000条命令

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

 

思路:底工的线条树模板直接套,作为友好线段树做的率先道题,代码回顾一下

 

 

#include 
#include 
#include 
#define lson l,m,rt<<1
#define rson m 1,r,rt<<1|1
using namespace std ;
const int maxn = 555555 ;
int sum[maxn<<2] ;

void pushUp(int rt)
{
    sum[rt] = sum[rt<<1] sum[rt<<1 | 1] ;
}

void build(int l,int r,int rt)    //构建一个线段树
{
    if(l == r)   //递归到最后一层
    {
      scanf("%d",&sum[rt]) ;
      return ;
    }
    int m = (l r)>>1 ;
    build(lson) ;
    build(rson) ;
    pushUp(rt) ;
}

void update(int p,int add,int l,int r,int rt)   //更新操作
{
    if(l == r)
    {
        sum[rt] =add ;
        return ;
    }
    int m = (l r)>>1 ;
    if(p<=m)
    {
        update(p,add,lson) ;
    }
    else
    {
        update(p,add,rson) ;
    }
    pushUp(rt) ;
}


int query(int L,int R,int l,int r,int rt)   //查询操作,L,R代表查询左右区间
{
    if(r<=R && L<=l)
    {
        return sum[rt] ;
    }
    int m = (l r)>>1 ;
    int ret = 0 ;
    if(L <= m)
    {
        ret =query(L,R,lson);
    }
    if(R>m)
    {
        ret =query(L,R,rson) ;
    }
    return ret ;
}



int  main()
{
    int t,n ;
    while(scanf("%d",&t)!=EOF)
    {
        for(int k = 1 ;k<=t ;k  )
        {
            scanf("%d",&n) ;
            build(1,n,1) ;
            char op[10] ;
            printf("Case %d:n",k) ;
            while(scanf("%s",op))
            {
                if(op[0] == 'E')
                    break ;
                int a,b ;
                scanf("%d%d",&a,&b) ;
                if(op[0] == 'Q')
                {
                    printf("%dn",query(a,b,1,n,1)) ;
                }
                else if(op[0] == 'S')
                {
                    update(a,-b,1,n,1) ;
                }
                else update(a,b,1,n,1) ;
            }
       }
    }
    return 0 ;
}

 

 

1166 敌兵布阵(单点更新线段树) 敌兵布阵 Time Limit: 二零零一/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 54411 Accepted Submi...

本文由澳门威利斯人发布于网络资讯,转载请注明出处:威尼斯娱乐手机版网站单点更新线段树

关键词: 澳门威利斯人