您的位置:澳门402永利com > 计算机 网络 > 敌兵布阵

敌兵布阵

发布时间:2019-09-23 20:45编辑:计算机 网络浏览(141)

    难题链接

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

     

    Problem Description

    Problem Description

    C国的死对头A国这段时日正在开展军事练习,所以C国间谍头子德里克和他手下Tidy又起来忙乎了。A国在海岸线沿直线布署了N个工兵营地,德里克和Tidy的职责正是要监视这么些工兵集散地的活动情状。由于使用了某种先进的监测手腕,所以每一个工兵营地的人数C国都调整的显著,各种工兵营地的人口皆有一点都不小希望爆发更动,可能增添或裁减多少个职员,但这么些都逃可是C国的监视。
    宗旨思报局要切磋仇人毕竟练习什么战术,所以Tidy要每一日向Derek陈说某一段连接的工兵集散地一共有微微人,比方德里克问:“Tidy,立刻报告第一个集散地到第十一个驻地共有多少人!”Tidy就要立时早先计算这一段的总人数并陈说。但敌兵集散地的总人口常常转移,而德里克每一次询问的段都分裂样,所以Tidy不得不每回都四个二个营地的去数,比十分的快就疲倦了,德里克对Tidy的估测计算速度更是不满:"你个死肥仔,算得这般慢,小编炒你蛇头鱼!”Tidy想:“你本人来测算看,那可真是一项累人的办事!笔者耿耿于怀你炒小编八爪鱼呢!”无可奈何之下,Tidy只能打电话向Computer专家Windbreaker求救,Windbreaker说:“死肥仔,叫你经常做多点acm题和看多点算法书,未来尝到苦果了吗!”Tidy说:"小编知错了。。。"但Windbreaker已经挂掉电话了。Tidy很闹心,这么算他确实会崩溃的,聪明的读者,你能写个程序帮他实现那项职业吧?不过只要您的顺序功效相当的矮的话,Tidy仍旧会遭到德里克的攻讦的.

    C国的死对头A国这段时日正在进展军事练习,所以C国间谍头子德里克和他手下Tidy又起来忙乎了。A国在海岸线沿直线布署了N个工兵营地,德里克和Tidy的天职正是要监视那些工兵基地的运动场所。由于使用了某种先进的监测手腕,所以各类工兵营地的总人口C国都调控的清晰,每一种工兵集散地的人头都有一点都不小可能率产生改动,也许扩充或减弱多少人手,但这个都逃可是C国的监视。
    中心境报局要钻探敌人毕竟演练什么攻略,所以Tidy要每天向德里克陈述某一段连接的工兵集散地一共有微微人,举例德里克问:“Tidy,立时报告第4个营地到第拾二个集散地共有几个人!”Tidy将要马上最初预计这一段的总人数并报告。但敌兵集散地的总人口常常转移,而德里克每便询问的段都差异,所以Tidy不得不每一次都一个八个本部的去数,十分的快就疲倦了,德里克对Tidy的一个钱打二17个结速度越来越不满:"你个死肥仔,算得那般慢,小编炒你枪乌贼!”Tidy想:“你和睦来计量看,那可正是一项累人的职业!笔者期盼你炒小编乌鱼呢!”无语之下,Tidy只可以打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥仔,叫您平日做多点acm题和看多点算法书,今后尝到苦果了呢!”Tidy说:"作者知错了。。。"但Windbreaker已经挂掉电话了。Tidy很烦心,这么算他确实会崩溃的,聪明的读者,你能写个程序帮她不负职分那项专门的工作啊?可是只要您的次序效能相当矮的话,Tidy照旧会受到德里克的指斥的.

     

     

     

    Input

    Input

    先是行一个整数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条命令

    先是行一个整数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 代表甘休,那条命令在每组数据最后出现;
    每组数据最多有60000条命令

     

     

    Output

     

    对第i组数据,首先输出“Case i:”和回车,
    对此各样Query询问,输出贰个整数并回车,表示精通的段中的总人数,这几个数保持在int以内。

    Output

     

    对第i组数据,首先输出“Case i:”和回车,
    对此各类Query询问,输出二个整数并回车,表示领会的段中的总人数,那些数保持在int以内。

    Sample Input

     

    1

     

    10

    Sample Input

    1 2 3 4 5 6 7 8 9 10

    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

    Query 1 3

     

    Add 3 6

     

    Query 2 7

    Sample Output

    Sub 10 2

    Case 1: 6 33 59

    Add 6 3

     

    Query 3 10

     

    End

    Author

     

    Windbreaker

    Sample Output

     

    Case 1:

    树状数组裸题 

    6

    屠龙宝刀点击就送

    33

    #include <ctype.h>
    #include <cstring>
    #include <cstdio>
    #define N 50005
    
    void read(int &x)
    {
        x=0;bool f=0;
        char ch=getchar();
        while(!isdigit(ch)) {if(ch=='-') f=1;ch=getchar();}
        while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
        x=f?(~x)+1:x;
    }
    int lowbit(int x) 
    {
        return x&(-x);
    }
    int Case,T,n,a[N],tag[N];
    void add(int x,int y)
    {
        for(;x<=n;x+=lowbit(x)) tag[x]+=y;
    }
    int query(int x)
    {
        int ans=0;
        for(;x;x-=lowbit(x)) ans+=tag[x];
        return ans;
    }
    int main()
    {
        read(T);
        for(;T--;)
        {
            memset(tag,0,sizeof(tag));
            printf("Case %d:n",++Case);
            read(n);
            for(int i=1;i<=n;i++) read(a[i]);
            for(int i=1;i<=n;i++) add(i,a[i]);
            char str[10];
            for(int x,y;;)
            {
                scanf("%s",str+1);
                if(str[1]=='Q') read(x),read(y),printf("%dn",query(y)-query(x-1));
                else if(str[1]=='A') read(x),read(y),add(x,y);
                else if(str[1]=='S') read(x),read(y),add(x,-y);
                else if(str[1]=='E') break;
            }
        }
        return 0;
    }
    

    59

     

    题意:标题汉语陈说,不再赘述。

    思路:线段树单点更新。

     

    代码如下:

    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    const int N=50005;
    int tr[4*N];
    
    void build(int i,int l,int r)
    {
        if(l==r) {
            scanf("%d",&tr[i]);
            return ;
        }
        int mid=(l+r)>>1;
        build(i*2,l,mid);
        build(i*2+1,mid+1,r);
        tr[i]=tr[i*2]+tr[i*2+1];
    }
    
    void update(int i,int l,int r,int x,int y)
    {
        if(l==r) {
            tr[i]+=y;
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid) update(i*2,l,mid,x,y);
        else       update(i*2+1,mid+1,r,x,y);
        tr[i]=tr[i*2]+tr[i*2+1];
    }
    
    int query(int i,int l,int r,int x,int y)
    {
        int sum=0;
        if(x<=l&&r<=y){
           sum+=tr[i];
           return sum;
        }
        int mid=(l+r)>>1;
        if(x<=mid) sum+=query(i*2,l,mid,x,y);
        if(y>mid)  sum+=query(i*2+1,mid+1,r,x,y);
        return sum;
    }
    
    int main()
    {
        int T,Case=1;
        cin>>T;
        while(T--){
           int n;
           printf("Case %d:n",Case++);
           scanf("%d",&n);
           build(1,1,n);
           while(1){
              char s[10];
              int x,y;
              scanf("%s",s);
              if(s[0]=='E') break;
              scanf("%d%d",&x,&y);
              if(s[0]=='A') update(1,1,n,x,y);
              else if(s[0]=='S') update(1,1,n,x,-y);
              else printf("%dn",query(1,1,n,x,y));
           }
        }
        return 0;
    }
    

    本文由澳门402永利com发布于计算机 网络,转载请注明出处:敌兵布阵

    关键词:

上一篇:图像旋转翻调换换

下一篇:43:相关月