daily pastebin goal
55%
SHARE
TWEET

Untitled

a guest Feb 14th, 2018 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
Top