敌兵布阵 HDU - 1166 - 单点修改,区间查询:树状数组/线段树
C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动,而Derek每次询问的段都不一样,所以Tidy不得不每次都一个一个营地的去数,很快就精疲力尽了,Derek对Tidy的计算速度越来越不满:"你个死肥仔,算得这么慢,我炒你鱿鱼!”Tidy想:“你自己来算算看,这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下,Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥仔,叫你平时做多点acm题和看多点算法书,现在尝到苦果了吧!”Tidy说:"我知错了。"但Windbreaker已经挂掉电话了。Tidy很苦恼,这么算他真的会崩溃的,聪明的读者,你能写个程序帮他完成这项工作吗?不过如果你的程序效率不够高的话,Tidy还是会受到Derek的责骂的.
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以内。
Input Sample
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 Sample
Case 1:
6
33
59
分析
- 树状数组
#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
const int N=5e4+10,INF=0x3f3f3f3f;
int n,m,a[N],tree[N];
void add(int x,int y){
while(x<=n) tree[x]+=y, x+=lowbit(x);
}
int sum(int x){
int res=0;
while(x) res+=tree[x],x-=lowbit(x);
return res;
}
int main(){
ios::sync_with_stdio(0);
int t,idx=0; cin>>t; string op; int I,J;
while(t--){
memset(tree,0,sizeof(tree));
cout<<"Case "<<++idx<<":\n";
cin>>n;
for(int i=1; i<=n; i++)cin>>I, add(i,I);
while(cin>>op) {
if(op[0]=='E') break;
cin>>I>>J;
if(op[0]=='Q') cout<<sum(J)-sum(I-1)<<endl;
if(op[0]=='A') add(I,J);
if(op[0]=='S') add(I,-J);
}
}
}
- 线段树
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e4+10, INF=0x3f3f3f3f;
int n,m,a[N];
struct Node {
int l,r;
int v;
} tr[N<<2];
void pushup(Node&u, Node&l, Node&r) {
u.v = l.v + r.v;
}
void pushup(int u) {
pushup(tr[u],tr[u<<1], tr[u<<1|1]);
}
void build(int u,int l,int r) {
if(l==r) tr[u]= {l,l,a[l]};
else {
tr[u]= {l,r};
int mid = l+r >> 1;
build(u<<1,l,mid), build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int x,int v) {
if(tr[u].l==x && tr[u].r==x) tr[u].v += v;
else {
int mid = tr[u].l + tr[u].r >> 1;
if(x<=mid) modify(u<<1,x,v);
else modify(u<<1|1,x,v);
pushup(u);
}
}
int query(int u,int l,int r) {
if(tr[u].l>=l && tr[u].r<=r) return tr[u].v;
else {
int mid = tr[u].l+tr[u].r >> 1;
LL res=0;
if(l<=mid) res += query(u<<1,l,r);
if(r>mid) res += query(u<<1|1,l,r);
return res;
}
}
void pr(int u) {
if(tr[u].l==0 && tr[u].r==0) return;
if(tr[u].l < tr[u].r) {
printf("%d [%d,%d]: %d\n",u,tr[u].l,tr[u].r,tr[u].v);
}
pr(u<<1), pr(u<<1|1);
}
int main() {
ios::sync_with_stdio(0);
int t,idx=0; string op; int I,J;
cin>>t;
while(t--) {
cout<<"Case "<<++idx<<":\n";
cin>>n;
for(int i=1; i<=n; i++)cin>>a[i];
build(1,1,n);
while(cin>>op) {
if(op[0]=='E') break;
cin>>I>>J;
if(op[0]=='Q') cout<<query(1,I,J)<<endl;
else {
if(op[0]=='S') J=-J;
modify(1,I,J);
}
}
}
return 0;
}
最新文章
- 基于keepalived双主模型的高可用LVS
- Double 数据保留两位小数二:直接截取小数后面两位,不进行四舍五入
- 数论只会GCD。。。
- [转]A Guide To using IMU (Accelerometer and Gyroscope Devices) in Embedded Applications.
- SNF开发平台WinForm之十二-发送手机短信功能调用-金笛-SNF快速开发平台3.3-Spring.Net.Framework
- BZOJ 2007 海拔(平面图最小割-最短路)
- Python2.x与3​​.x版本区别
- 两个C++对象是否相等,要程序员自己下定义,通常是覆盖==操作符
- [转] npm 模块安装机制简介
- Ajax应用常见的HTTP ContentType设置
- dedecms 获取描述信息限制字数
- matlab中同一文件定义子函数的方法
- 201521123057 《Java程序设计》第2周学习总结
- Codeforces 839E Mother of Dragons【__builtin_popcount()的使用】
- C# 操作Session、Cookie,Url 编码解码工具类WebHelper
- redis安装教程 windows环境
- 一、Selenium 工作原理
- ASP.NET Core Web API处理HttpResponseMessage类型返回值的问题
- net 表格控件
- Android入门-新手如何成功创建一个Android小应用