• API
• FAQ
• Tools
• Archive
daily pastebin goal
17%
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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top