「HDU1166」敌兵布阵

前言

题目好多废话

大意

有一个序列，开始时每一位都有一个值，然后是若干个命令：

1. Add i j，表示第\(i\)位增加\(j\)；
2. Sub i j，表示第\(i\)位减少\(j\)；
3. Query i j，表示从第\(i\)位到地\(j\)位的总和；
4. End，表示结束，在每组数据最后出现。

思路

这题一眼盯真，可以用线段树或者树状数组解决，都是单点修改，区间查询，然后直接套模板就行了。

\(Code\)

线段树：

#include<bits/stdc++.h>
char q[10];
int t,tot,n,v1,v2,segment[200005];
inline void pushUp(int root){segment[root]=segment[root*2]+segment[root*2+1];}
inline void built(int root,int left,int right){if(left==right){scanf("%d",&segment[root]);return;}int mid=(left+right)/2;built(root*2,left,mid);built(root*2+1,mid+1,right);pushUp(root);}
inline void update(int root,int pos,int add_num,int left,int right){if(left==right){segment[root]+=add_num;return;}int mid=(left+right)/2;if(pos<=mid)update(root*2,pos,add_num,left,mid);else update(root*2+1,pos,add_num,mid+1,right);pushUp(root);}//更新
inline int sum(int root,int left,int right,int L,int R){if(left==L&&right==R)return segment[root];int mid=(L+R)/2,res=0;if(left>mid)res+=sum(root*2+1,left,right,mid+1,R);else if(right<=mid)res+=sum(root*2,left,right,L,mid);else res+=sum(root*2,left,mid,L,mid)+sum(root*2+1,mid+1,right,mid+1,R);return res;}//求和
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		built(1,1,n);//建树
		printf("Case %d:\n",++tot);
		while(scanf("%s",q)){
			if(q[0]=='E')break;
			scanf("%d%d",&v1,&v2);
			if(q[0]=='A')update(1,v1,v2,1,n);//单点修改
			else if(q[0]=='S')update(1,v1,-v2,1,n);//单点修改
			else printf("%d\n",sum(1,v1,v2,1,n));//区间查询
		}
	}
}

树状数组：

#include<bits/stdc++.h>
int t,tot,v1,v2,a[50005],n;
char q[8];
int lowbit(int i){return i&-i;}
inline void update(int i, int v){while(i<=n)a[i]+=v,i+=lowbit(i);}//更新
inline int sum(int i){int sum=0;while(i>0)sum+=a[i],i-=lowbit(i);return sum;}//求和
int main(){
	scanf("%d",&t);
	while(t--){
		memset(a,0,sizeof(a));//初始化
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d",&v1);
			update(i,v1);//初始值
		}
		printf("Case %d:\n",++tot);
		while(~scanf("%s",q)){
			if(q[0]=='E')break;
			scanf("%d%d",&v1,&v2);
			if(q[0]=='A')update(v1,v2);//单点修改
			else if(q[0]=='S')update(v1,-v2);//单点修改
			else if(q[0]=='Q')printf("%d\n",sum(v2)-sum(v1-1));//区间查询
		}
	}
}