敌兵布阵

作者: 金沙澳门官网  发布:2019-11-15

1166-敌兵布阵,1166-敌兵

陈说:C国的死对头A国这段时日正在开展军事演练,所以C国窥探头子德里克和她手下Tidy又开端忙乎了。A国在海岸线沿直线安插了N个工兵营地,德里克和Tidy的任务就是要监视那么些工兵营地的运动景况。由于应用了某种先进的监测花招,所以每一种工兵集散地的食指C国都驾驭的一清二楚,各类工兵营地的总人口都有十分的大可能率发生更正,只怕扩展或减弱多少人士,但那一个都逃可是C国的监视。
主题绪报局要钻探冤家究竟演练什么战略,所以Tidy要随即向德里克汇报某大器晚成段连接的工兵营地后生可畏共有多少人,举例德里克问:“Tidy,立时报告第三个营地到第拾一个集散地共有几个人!”Tidy将要立即开端计算那生龙活虎段的总人数并上报。但敌兵营地的人口平时转移,而德里克每趟询问的段都不相仿,所以Tidy不能不每回都二个二个驻地的去数,相当的慢就疲劳了,德里克对Tidy的测算速度更加的不满:"你个死肥仔,算得那般慢,小编炒你生鱼!”Tidy想:“你自个儿来总计看,那可就是风流浪漫项累人的劳作!作者心心念念你炒小编章鱼呢!”无助之下,Tidy只能打电话向Computer行家Windbreaker求救,Windbreaker说:“死肥仔,叫您日常做多点acm题和看多点算法书,今后尝到苦果了呢!”Tidy说:"小编知错了。。。"但Windbreaker已经挂掉电话了。Tidy很压抑,这么算他当真会崩溃的,聪明的读者,你能写个程序帮他做到那项专门的学业吧?然而倘使你的次第成效相当的矮的话,Tidy还是会遭逢德里克的责备的.

输入:第后生可畏行叁个整数T,表示有T组数据。
每组数据第风度翩翩行多个正整数N(N<=50000卡塔 尔(英语:State of Qatar),表示敌人有N个工兵集散地,接下去有N个正整数,第i个正整数ai代表第i个工兵营地里开端时有ai个人(1<=ai<=50卡塔尔。
接下去每行有一条命令,命令有4种情势:
(1) Add i j,i和j为正整数,表示第i个集散地扩展j个人(j不超越30卡塔 尔(英语:State of Qatar)
(2)Sub i j ,i和j为正整数,表示第i个营地收缩j个人(j不超过30卡塔尔国;
(3)Query i j ,i和j为正整数,i<=j,表示理解第i到第j个营地的总人数;
(4)End 代表结束,那条命令在每组数据最后现身;
每组数据最多有40000条命令

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

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

 

描述:C国的死对头A国这段时光正在展开军事演练,所以C国眼线头子德里克和她手下Tidy又起来忙乎了。A国在海岸线沿...

本文由金沙澳门官网送注册58发布于金沙澳门官网,转载请注明出处:敌兵布阵

关键词: