题目描述

链接：https://vjudge.net/problem/hdu-1166

思路分析

由于涉及到整个区间的数据修改和查询，所以是一道线段树题目。
这里主要的就是记住模板：
贴个大佬博客：https://blog.csdn.net/queque_heiya/article/details/104166507
然后我就偷懒吧。。

AC代码

#include <iostream>
#include <cstring>
using namespace std;
#define MEM(a) memset(a,0,sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int maxn=50005;
typedef long long ll;
ll sum[maxn<<4]={0};
ll add[maxn<<2]={0};
void pushup(ll rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(ll rt,ll m){
if(add[rt]){
add[rt<<1]+=add[rt];
add[rt<<1|1]+=add[rt];
sum[rt<<1]+=(m-(m>>1))*add[rt];
sum[rt<<1|1]+=(m>>1)*add[rt];
add[rt]=0;
}
}
void build(ll l,ll r,ll rt){
if(l==r){
cin>>sum[rt];
return;
}
ll m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void updata(ll L,ll R,ll num,ll l,ll r,ll rt){
if(L<=l&&R>=r){
sum[rt]+=(r-l+1)*num;
add[rt]+=num;
return;
}
pushdown(rt,l-r+1);
ll m=(r+l)>>1;
if(L<=m) updata(L,R,num,lson);
if(R>m) updata(L,R,num,rson);
pushup(rt);
}
ll query(ll L,ll R,ll l,ll r,ll rt){
if(L<=l&&R>=r){
return sum[rt];
}
pushdown(rt,r-l+1);
ll m=(l+r)>>1;
ll ans=0;
if(L<=m) ans+=query(L,R,lson);
if(R>m) ans+=query(L,R,rson);
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cout.tie(NULL);
//	freopen("data.txt","r",stdin);
//	freopen("me.txt","w",stdout);
int t;
cin>>t;
int kase=0;
while(t--){
MEM(sum);
MEM(add);
printf("Case %d:n",++kase);
ll n;
cin>>n;
build(1,n,1);
char cmd[10];
while(cin>>cmd){
if(!strcmp(cmd,"Query")){
ll l,r;
cin>>l>>r;
printf("%lldn",query(l,r,1,n,1));
}
if(!strcmp(cmd,"Add")){
ll tar,num;
cin>>tar>>num;
updata(tar,tar,num,1,n,1);
}
if(!strcmp(cmd,"Sub")){
ll tar,num;
cin>>tar>>num;
updata(tar,tar,-num,1,n,1);
}
if(!strcmp(cmd,"End")) break;
}
}
return 0;
}

最后

以上就是缓慢天空为你收集整理的HDU - 1166 敌兵布阵（线段树模板）题目描述思路分析AC代码的全部内容，希望文章能够帮你解决HDU - 1166 敌兵布阵（线段树模板）题目描述思路分析AC代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。