[1166 敌兵布阵]
题意：
给出一些命令..要求可以：
随时增加或减少某个位置上的数
随时查询某段区间上的和..
输入：
一个T 表示有T组样例
每组样例一个n 表示有n个位置
输入命令:
Add a b 表示在 a 位置上增加 b
Sub a b 表示在 a 位置上减少 b
Query a b 表示求 a 到 b 的和
思路：
因为数据量很大..所以无法靠暴力来遍历求和..
所以用线段树..
Tips：
更新的时候注意sum数组开到节点的4倍
Code：
View Code 1 #include2 #include 3 4 const int MAXN = 50010; 5 int a[MAXN], sum[MAXN*4]; 6 7 void creat(int l, int r, int rt) 8 { 9 if(l == r) {10 scanf("%d", &sum[rt]);11 return;12 }13 int m = (l+r)>>1;14 creat(l, m, rt<<1);15 creat(m+1, r, rt<<1|1);16 sum[rt] = sum[rt<<1]+sum[rt<<1|1];17 }18 19 void update(int p, int w, int l, int r, int rt)20 {21 if(l == r) {22 sum[rt] += w;23 return;24 }25 int m = (l+r)>>1;26 if(p <= m) update(p, w, l, m, rt<<1);27 else update(p, w, m+1, r, rt<<1|1);28 sum[rt] = sum[rt<<1]+sum[rt<<1|1];29 }30 31 int query(int l, int r, int L, int R, int rt)32 {33 if(l <= L && R <= r) {34 return sum[rt];35 }36 int m = (L+R)>>1;37 int res = 0;38 if(l <= m) res += query(l, r, L, m, rt<<1);39 if(r > m) res += query(l, r, m+1, R, rt<<1|1);40 return res;41 }42 43 int main()44 {45 int i, j, k = 0;46 int T, n;47 char opt[10];48 int a, b;49 while(scanf("%d", &T) != EOF)50 while(T--)51 {52 printf("Case %d:\n", ++k);53 scanf("%d", &n);54 creat(1, n, 1);55 while(scanf("%s", opt), opt[0] != 'E') {56 scanf("%d %d", &a, &b);57 if(opt[0] == 'A')58 update(a, b, 1, n, 1);59 else if(opt[0] == 'S')60 update(a, -1*b, 1, n, 1);61 else if(opt[0] == 'Q')62 printf("%d\n", query(a, b, 1, n, 1));63 }64 65 }66 return 0;67 }
题目链接：
[1754 i hate it]
题意：
给出一些数值根据命令更新或查询区间最大值
思路：
向上更新的时候找最大值
Tips：
可以用函数实现更新操作
Code：
View Code 1 #include2 #include 3 #include 4 using namespace std; 5 6 const int MAXN = 200010; 7 int ma[MAXN<<2]; 8 9 void creat(int l, int r, int rt)10 {11 if(l == r) {12 scanf("%d", &ma[rt]);13 return;14 }15 int mid = (l+r)>>1;16 creat(l, mid, rt<<1);17 creat(mid+1, r, rt<<1|1);18 ma[rt] = max(ma[rt<<1], ma[rt<<1|1]);19 }20 21 void modify(int p, int w, int l, int r, int rt)22 {23 if(l == r) {24 ma[rt] = w;25 return;26 }27 int mid = (l+r)>>1;28 if(p <= mid) modify(p, w, l, mid, rt<<1);29 else modify(p, w, mid+1, r, rt<<1|1);30 ma[rt] = max(ma[rt<<1], ma[rt<<1|1]);31 }32 33 int query(int l, int r, int L, int R, int rt)34 {35 if(l <= L && r >= R) {36 return ma[rt];37 }38 int mid = (L+R)>>1;39 int res = 0;40 if(l <= mid) res = max(res, query(l, r, L, mid, rt<<1));41 if(r > mid) res = max(res, query(l, r, mid+1, R, rt<<1|1));42 return res;43 }44 45 int main()46 {47 int i, j, k;48 int n, m;49 char opt[2];50 int a, b;51 while(scanf("%d %d", &n, &m) != EOF)52 {53 creat(1, n, 1);54 while(m--) {55 scanf("%s", &opt);56 scanf("%d %d", &a, &b);57 if(opt[0] == 'Q')58 printf("%d\n", query(a, b, 1, n, 1));59 else if(opt[0] == 'U') modify(a, b, 1, n, 1);60 }61 }62 return 0;63 }
题目链接：