hdu1166敌兵布阵
建树、单点修改、查询
1 #include2 #include 3 #include 4 #include 5 #include 6 #define lson l, m, rt<<1 7 #define rson m+1, r, rt<<1|1 8 #define IO ios::sync_with_stdio(false);cin.tie(0); 9 #define INF 1e910 typedef long long ll;11 using namespace std;12 int t, n, sum[50010<<2], a, b, ans;13 char s[20];14 void PushUP(int rt)15 {16 sum[rt] = sum[rt<<1]+sum[rt<<1|1];17 }18 void build(int l, int r, int rt)19 {20 if(l == r){21 cin >> sum[rt];22 return ;23 }24 int m = (l+r)>>1;25 build(lson);26 build(rson);27 PushUP(rt);28 }29 void update(int p, int add, int l, int r, int rt)30 {31 if(l == r){32 sum[rt] += add;33 return ;34 }35 int m = (l+r)>>1;36 if(p <= m){37 update(p, add, lson);38 }39 else{40 update(p, add, rson);41 }42 PushUP(rt);43 }44 int query(int L, int R, int l, int r, int rt)45 {46 if(L <= l&&R >= r){47 return sum[rt];48 }49 int m = (l+r)>>1;50 int res = 0;51 if(L <= m){52 res += query(L, R, lson);53 }54 if(R > m){55 res += query(L, R, rson);56 } 57 return res;58 }59 int main()60 {61 IO;62 int kase=0;63 cin >> t; 64 while(t--){65 cout << "Case " << ++kase << ":" << endl;66 cin >> n;67 build(1, n, 1); 68 while(cin >> s){69 if(s[0] == 'E'){70 break;71 }72 cin >> a >> b;73 if(s[0] == 'A'){74 update(a, b, 1, n, 1);75 }76 else if(s[0] == 'S'){77 update(a, -b, 1, n, 1);78 }79 else if(s[0] == 'Q'){80 cout << query(a, b, 1, n, 1) << endl;81 }82 }83 }84 return 0;85 }
hdu1698 Just a hook
区间更新，更新值存在lazy数组里
1 #include2 #include 3 #include 4 #include 5 #include 6 #define lson l, m, rt<<1 7 #define rson m+1, r, rt<<1|1 8 #define IO ios::sync_with_stdio(false);cin.tie(0); 9 #define INF 1e910 typedef long long ll;11 using namespace std;12 int t, n, m;13 int sum[100010<<2], lazy[100010<<2];14 void PushUP(int rt)15 {16 sum[rt] = sum[rt<<1]+sum[rt<<1|1]; 17 }18 void build(int l, int r, int rt)19 {20 lazy[rt] = 0;//一定要写在if外面作初始化 21 if(l == r){22 sum[rt] = 1;23 return ;24 }25 int m = (l+r)>>1;26 build(lson);27 build(rson);28 PushUP(rt);29 }30 void PushDown(int rt, int m)31 {32 if(lazy[rt]){33 lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];34 sum[rt<<1] = (m - (m>>1))*lazy[rt];35 sum[rt<<1|1] = (m>>1)*lazy[rt];36 lazy[rt] = 0;37 }38 }39 void update(int L, int R, int v, int l, int r, int rt)40 {41 if(L <= l && R >= r){42 lazy[rt] = v;43 sum[rt] = v*(r-l+1);44 return ;45 }46 PushDown(rt, r-l+1);47 int m = (l+r)>>1;48 if(L <= m){49 update(L, R, v, lson);50 }51 if(R > m){52 update(L, R, v, rson);53 }54 PushUP(rt);55 }56 int main()57 {58 IO;59 int x, y, z, kase=0;60 while(cin >> t){61 kase=0;62 while(t--){63 cin >> n;64 build(1, n, 1);65 cin >> m; 66 for(int i = 0; i < m; i++){67 cin >> x >> y >> z;68 update(x, y, z, 1, n, 1);69 }70 cout << "Case " << ++kase << ": The total value of the hook is ";71 cout << sum[1] << "." << endl;72 }73 }74 return 0;75 }
线段树区间更新（lazy数组）模板题
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include