题意 ：HDU的中文题也不常见。。。。这道题我就不详述了。。。。。
思路 ：这个题用线段树用树状数组都可以，用线段树的时候要注意输入那个地方，输入一个字符串的时候不要紧接着输入两个数字，因为我就是这样贡献了好几个RE。。。。
不要用cin，cout，因为也是这样我又贡献了好几个TLE。。。。血一般的教训啊，这道题是水题，模板题。
这个是线段树的代码
#include#include #include #include using namespace std;const int maxn = 500005 ;int a[maxn] ;int ans ;struct node{ int l,r,value ;} Node[4*maxn] ;void build(int v ,int l,int r){ Node[v].l = l ; Node[v].r = r ; if(l == r) { Node[v].value = a[r] ; return ; } int mid = (l+r)>>1 ; build(v*2,l,mid) ; build(v*2+1,mid+1,r) ; Node[v].value = Node[v*2].value+Node[v*2+1].value ;}int query(int v,int l,int r){ if(Node[v].l == l && Node[v].r == r) return Node[v].value ; int mid = (Node[v].l+Node[v].r) >> 1 ; if(r <= mid) return query(v*2,l,r) ; else { if(l > mid) return query(v*2+1,l,r) ; else return query(v*2,l,mid)+query(v*2+1,mid+1,r) ; }}void update(int v,int n,int m){ Node[v].value += m ; if(Node[v].l == n && Node[v].r == n) return ; else { int mid = (Node[v].l+Node[v].r)>>1 ; if(n <= mid) update(2*v,n,m) ; else if(n > mid) update(2*v+1,n,m) ; }}void sub(int v,int n,int m){ Node[v].value -= m ; if(Node[v].l == n && Node[v].r == n) return ; else { int mid = (Node[v].l+Node[v].r)>>1 ; if(n <= mid) sub(2*v,n,m) ; else if(n > mid) sub(2*v+1,n,m) ; }}int main(){ int T ,x=1; scanf("%d",&T) ; while(T--) { int n ; ans = 0; scanf("%d",&n) ; for(int i = 1 ; i <= n ; i++) scanf("%d",&a[i]) ; build(1,1,n) ; printf("Case %d:\n",x++) ; char ch[31] ; while(true) { scanf("%s",ch) ; int a,b ; if(ch[0] == 'Q') { scanf("%d %d",&a,&b) ; printf("%d\n",query(1,a,b)) ; } else if(ch[0] == 'A'){ scanf("%d %d",&a,&b) ; update(1,a,b) ; } else if(ch[0] == 'S'){ scanf("%d %d",&a,&b) ; sub(1,a,b) ; } if(ch[0] == 'E') break ; } // printf("\n") ; } return 0;}
这个是树状数组的
#include#include #include using namespace std ;const int maxn = 500003 ;int ch[maxn] ;int data ;int n ;int lowbit(int i){ return i&(-i) ;}int sum(int i){ int ans = 0 ; while(i > 0) { ans += ch[i] ; i -= lowbit(i) ; } return ans ;}void add(int x,int value){ while(x <= n) { ch[x] += value ; x += lowbit(x) ; }}int main(){ int T ; scanf("%d",&T) ; for(int i = 1 ; i <= T ; i++) { scanf("%d",&n) ; memset(ch,0,sizeof(ch)) ; for(int j = 1 ; j <= n ; j++) { scanf("%d",&data) ; add(j,data) ; } printf("Case %d:\n",i) ; char sh[31] ; int a,b ; while(~scanf("%s",sh)) { if(sh[0] == 'E') break ; if(sh[0] == 'A') { scanf("%d %d",&a,&b) ; add(a,b) ; } if(sh[0] == 'Q') { scanf("%d %d",&a,&b) ; printf("%d\n",sum(b)-sum(a-1)) ; } if(sh[0] == 'S') { scanf("%d %d",&a,&b); add(a,-b) ; } } } return 0 ;}
当时初学时代码太乱，跟崔老师学习了一点，现在重新刷了一遍
1 #include2 #include 3 #include 4 #include 5 6 using namespace std ; 7 8 int p[50010*4],a ; 9 //string sh ;10 char sh[452] ;11 //void pushdown(int rt, int m)12 //{13 //14 //}15 void pushup(int rt)16 {17 p[rt] = p[rt << 1] + p[rt << 1 | 1] ;18 }19 void build(int l,int r,int rt)20 {21 if(l == r)22 {23 cin >> a ;24 p[rt] = a ;25 return ;26 }27 int mid = (l + r) >> 1 ;28 build(l,mid,rt << 1) ;29 build(mid + 1 , r , rt << 1 | 1) ;30 pushup(rt) ;31 }32 void update(int l , int r,int sc,int rt,int flag,int x)33 {34 if(l == r)35 {36 if(flag > 0)37 p[rt] += sc ;38 else p[rt] -= sc ;39 return ;40 }41 int mid = (l+r) >> 1 ;42 if(mid >= x)43 update(l,mid,sc,rt << 1,flag,x) ;44 if(mid < x)45 update(mid+1,r,sc,rt << 1 | 1 ,flag,x) ;46 pushup(rt) ;47 }48 int query(int L,int R,int l,int r,int rt)49 {50 int sum = 0;51 if(l >= L && r <= R)52 {53 return p[rt] ;54 }55 int mid = (l+r) >> 1 ;56 if(mid >= L)57 sum += query(L,R,l,mid,rt << 1) ;58 if(mid < R)59 sum += query(L,R,mid+1,r,rt << 1 | 1) ;60 return sum ;61 }62 int main()63 {64 int T,N ,x,y;65 // cin >> T ;66 scanf("%d",&T) ;67 for(int i = 1 ; i <= T ; i++)68 {69 scanf("%d",&N) ;70 build(1,N,1) ;71 printf("Case %d:\n",i) ;72 while(~scanf("%s",sh))73 {74 if(sh[0] == 'E')75 break ;76 // cin >> x >> y ;77 scanf("%d %d",&x,&y) ;78 if(sh[0] == 'Q')79 {80 int ans = query(x,y,1,N,1) ;81 // cout << ans << endl ;82 printf("%d\n",ans) ;83 }84 else if(sh[0] == 'A')85 {86 update(1,N,y,1,1,x) ;87 }88 else if(sh[0] == 'S')89 {90 update(1,N,y,1,-1,x) ;91 }92 }93 }94 return 0;95 }
推荐文章