Advertisement
Guest User

Untitled

a guest
Feb 14th, 2018
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.18 KB | None | 0 0
  1. # include <iostream>
  2. # define ll long long
  3. using namespace std;
  4. ll n,k,l,r,x,a[1000001],t[1000005];
  5. void build ( ll v, ll tl, ll tr ) {
  6. if ( tl==tr ) {
  7. t[v] = a[tl];
  8. }
  9. else {
  10. ll mid = (tl+tr)/2;
  11. build (v*2,tl,mid);
  12. build (v*2+1,mid+1,tr);
  13. t[v] = t[v*2]+t[v*2+1];
  14. }
  15. }
  16. ll sum ( ll v, ll tl, ll tr, ll l, ll r ) {
  17. if ( l>r ) {
  18. return 0;
  19. }
  20. if ( l==tl && r==tr ) {
  21. return t[v];
  22. }
  23. ll mid = (tl+tr)/2;
  24. return sum(v*2,tl,mid,l,min(r,mid))+sum(v*2+1,mid+1,tr,max(l,mid+1),r);
  25. }
  26. void upd ( ll v, ll tl, ll tr, ll pos, ll val ) {
  27. if ( tl==tr ) {
  28. t[v] = val;
  29. }
  30. else {
  31. ll mid = (tl+tr)/2;
  32. if ( pos<=mid ) {
  33. upd (v*2,tl,mid,pos,val);
  34. }
  35. else {
  36. upd (v*2+1,mid+1,tr,pos,val);
  37. }
  38. t[v] = t[v*2]+t[v*2+1];
  39. }
  40. }
  41. int main () {
  42. freopen ("sum.in","r",stdin);
  43. freopen ("sum.out","w",stdout);
  44. scanf ("%I64d%I64d", &n, &k);
  45. for ( ll i=1; i<=n; ++i ) {
  46. a[i] = 0;
  47. }
  48. build (1,1,n);
  49. for ( ll i=1; i<=k; ++i ) {
  50. char q;
  51. scanf("%1s", &q);
  52. if ( q=='A' ) {
  53. ll x,y;
  54. scanf ("%I64d%I64d", &x, &y);
  55. upd(1,1,n,x,y);
  56. }
  57. else {
  58. ll l,r;
  59. scanf ("%I64d%I64d", &l, &r);
  60. cout << sum(1,1,n,l,r) << '\n';
  61. }
  62. }
  63. return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement