Hdu 1166

女爷i 2024-04-20 10:27 47阅读 0赞

##  ##

hdu1166-敌兵布阵

### 题意： ###

> 读入一个数组，完成单点加，单点减，和区间求和三种操作。

### 解法： ###

> 明摆着的一颗线段树，SB题。

### CODE: ###

#pragma GCC optimize(2) #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define LL long long #define N 100010 struct Tree { int lson,rson; int sum,tag; }tree[N * 2]; int n,cnt = 1,a[N],ans,T,test; char s[N]; inline int read(){ int x = 0,f = 1; char ch = getchar(); while(ch<'0'||ch>'9') {if(ch == '-') f = -1; ch = getchar();} while(ch>='0'&&ch<='9') {x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();} return x * f; } inline void pushup(int x) { tree[x].sum = tree[tree[x].lson].sum + tree[tree[x].rson].sum; } inline void pushdown(int x,int l,int r) { int mid = (l + r) >> 1; tree[tree[x].lson].sum += (mid - l + 1) * tree[x].tag; tree[tree[x].lson].tag += tree[x].tag; tree[tree[x].rson].sum += (r - mid) * tree[x].tag; tree[tree[x].rson].tag += tree[x].tag; tree[x].tag = 0; } void build(int x,int l,int r) { if(l == r) { tree[x].sum = a[l]; return; } int mid = (l + r) >> 1; tree[x].lson = ++cnt; build(tree[x].lson,l,mid); tree[x].rson = ++cnt; build(tree[x].rson,mid+1,r); pushup(x); } void update(int x,int l,int r,int k,int v) { if(l == r) { tree[x].sum += v; return; } int mid = (l + r) >> 1; if(k <= mid) update(tree[x].lson,l,mid,k,v); else update(tree[x].rson,mid+1,r,k,v); pushup(x); } int query(int x,int l,int r,int ll,int rr) { if(l == ll && r == rr) return tree[x].sum; int mid = (l + r) >> 1; pushdown(x,l,r); if(rr <= mid) return query(tree[x].lson,l,mid,ll,rr); else if(ll > mid) return query(tree[x].rson,mid+1,r,ll,rr); else return query(tree[x].lson,l,mid,ll,mid) + query(tree[x].rson,mid+1,r,mid+1,rr); } int main() { T = read(); while(T--) { test++; n = read(); for(int i = 1 ; i <= n ; i++) a[i] = read(); build(1,1,n); printf("Case %d:\n",test); while(true) { scanf("%s",s+1); if(s[1] == 'E') break; if(s[1] == 'A') { int i = read() , j = read(); update(1,1,n,i,j); } if(s[1] == 'S') { int i = read() , j = read(); update(1,1,n,i,-j); } if(s[1] == 'Q') { int i = read() , j = read(); printf("%d\n",query(1,1,n,i,j)); } } } //system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11396819.html