首页 > 代码库 > 【线段树】hdu1166敌兵布阵
【线段树】hdu1166敌兵布阵
/* 水水的线段树点修改: ---------------------------------------------------------------- void build(int l,int r,int o)建树 { int mid = (l + r) / 2; a[o].left = l; a[o].right = r; a[o].num = 0; if(a[o].left == a[o].right)到达叶子节点 return ; build(l, mid, lc);向左走 build(mid + 1, r, rc);向右走 } -------------------------------------------------------------------------------- void update(int l, int r, int o)//L营增加R个人 { if(a[o].left <= l && a[o].right >= l)在该区间则更新num a[o].num += r; if(a[o].left == a[o].right)叶子结点返回 return ; int mid = (a[o].left + a[o].right) / 2; if(l <= mid) update(l, r, lc);左走 else update(l, r, rc);右走 } ----------------------------------------------------------------------------------- void query(int l, int r, int o)//在id处加L到R的和 { int mid = (a[o].left + a[o].right) / 2; if(a[o].left == l && a[o].right == r)找到区间更新sum的值 { sum += a[o].num; return ; } if(r <= mid) query(l, r, lc);左走 else if(l > mid) query(l, r, rc);右走 else { query(l, mid, lc); query(mid+1, r, rc); } } ------------------------------------------------------------------------------------- */ #include <iostream> #include <cstdio> #include <cstring> #define INF 0x3f3f3f3f #define lc o*2 #define rc o*2+1 using namespace std; const int N = 50050*3; struct node{ int left,right; int num; }a[N]; int n,sum; void build(int l,int r,int o) { int mid = (l + r) / 2; a[o].left = l; a[o].right = r; a[o].num = 0; if(a[o].left == a[o].right) return ; build(l, mid, lc); build(mid + 1, r, rc); } void update(int l, int r, int o)//L营增加R个人 { if(a[o].left <= l && a[o].right >= l) a[o].num += r; if(a[o].left == a[o].right) return ; int mid = (a[o].left + a[o].right) / 2; if(l <= mid) update(l, r, lc); else update(l, r, rc); } void query(int l, int r, int o)//在id处加L到R的和 { int mid = (a[o].left + a[o].right) / 2; if(a[o].left == l && a[o].right == r) { sum += a[o].num; return ; } if(r <= mid) query(l, r, lc); else if(l > mid) query(l, r, rc); else { query(l, mid, lc); query(mid+1, r, rc); } } int main() { //freopen("input.txt","r",stdin); int T; int kase = 1; int num; int l,r; char s[10]; cin>>T; while(T--) { sum = 0; printf("Case %d:\n",kase++); scanf("%d",&n); build(1, n, 1); for(int i = 1; i <= n; i++) { scanf("%d",&num); update(i, num, 1); } while(scanf("%s",s)) { if(s[0] == 'E') break; if(s[0] == 'Q') { scanf("%d%d",&l,&r); query(l, r, 1); printf("%d\n",sum); sum = 0; } if(s[0] == 'A') { scanf("%d%d",&l,&r); update(l, r, 1); } if(s[0] == 'S') { scanf("%d%d",&l,&r); update(l, -r, 1); } } } return 0; }
----------------------------------------
wuwuwuwuuwuwuwu.....................
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。