fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. #define endl "\n"
  5. ll P=1000000007;
  6. ll MAX=P*(P-7);
  7. ll MIN=-1*MAX;
  8. const int sizes=200001;
  9. ll BIT1[200011],BIT2[200011], n, a[200011];
  10. void update1(ll x, ll v)
  11. {
  12.     while(x <= n)
  13.     {
  14.         BIT1[x] += v;
  15.         x += x & -x;
  16.     }
  17. }
  18. ll query1(ll k)
  19. {
  20.     ll s = 0;
  21.     while(k > 0)
  22.     {
  23.         s += BIT1[k];
  24.         k -= k & -k;
  25.     }
  26.     return s;
  27. }
  28. void update2(ll x, ll v)
  29. {
  30.     while(x <= n)
  31.     {
  32.         BIT2[x] += v;
  33.         x += x & -x;
  34.     }
  35. }
  36. ll query2(ll k)
  37. {
  38.     ll s = 0;
  39.     while(k > 0)
  40.     {
  41.         s += BIT2[k];
  42.         k -= k & -k;
  43.     }
  44.     return s;
  45. }
  46. void solve()
  47. {
  48.     ll t,i,j,k,l,m,o,p,q,r,s=0;
  49.     cin>>n>>q;
  50.     for(i=1;i<=n;i++)
  51.     cin>>a[i];
  52.     memset(BIT1,0,sizeof(ll)*(n+4));
  53.     memset(BIT2,0,sizeof(ll)*(n+4));
  54.     for(i=1;i<=n;i++)
  55.     {
  56.         if(i%2==1)
  57.         {
  58.             update1(i,a[i]);
  59.             update2(i,a[i]*i);
  60.         }
  61.         else 
  62.         {
  63.             update1(i,-1*a[i]);
  64.             update2(i,-1*i*a[i]);
  65.         }
  66.     }
  67.     //cout<<query1(2)-query1(0)<<endl;
  68.     //cout<<query2(2)-query2(0)<<endl;
  69.     ll zz=0;
  70.     while(q--)
  71.     {
  72.         char c;
  73.         cin>>c;
  74.         if(c=='U')
  75.         {
  76.            // cout<<c<<endl;
  77.               ll index,value;
  78.               cin>>index>>value;
  79.               ll prev=a[index];
  80.               ll n_val1,n_val2;
  81.               if(index%2==0)
  82.               {
  83.                   n_val1=-1*value;
  84.                   n_val1=n_val1-(-1*prev);
  85.  
  86.                   n_val2=-1*index*value;
  87.                   n_val2=n_val2-(-1*index*prev);
  88.               }
  89.               else if(index%2==1)
  90.               {
  91.                   n_val1=1*value;
  92.                   n_val1=n_val1-(1*prev);
  93.  
  94.                   n_val2=1*index*value;
  95.                   n_val2=n_val2-(1*index*prev);
  96.               }
  97.               update1(index,n_val1);
  98.               update2(index,n_val2);
  99.               a[index]=value;
  100.         }
  101.         else 
  102.         {
  103.               cin>>l>>r;
  104.               if(l%2==1)
  105.               {
  106.                   ll offset=l-1;
  107.                   ll val1=query2(r)-query2(l-1);
  108.                   ll val2=query1(r)-query1(l-1);
  109.                   ll ans=(val1-val2*offset);
  110.                   zz+=ans;
  111.               }
  112.               else 
  113.               {
  114.                   ll offset=l-1;
  115.                   ll val1=query2(r)-query2(l-1);
  116.                   ll val2=query1(r)-query1(l-1);
  117.                   ll ans=(val1-val2*offset); 
  118.                   ans*=-1;
  119.                   zz+=ans;
  120.               } 
  121.         }
  122.     }
  123.     cout<<zz<<endl;
  124. }
  125. int main()
  126. {
  127.     ios_base::sync_with_stdio(false);
  128.     cin.tie(0);
  129.     ll t,n,i,j,k,l,m,o,p,q,r,a[sizes];
  130.     cin>>t;
  131.     for(i=1;i<=t;i++)
  132.     {
  133.     cout<<"Case #"<<i<<": ";
  134.     solve();
  135.     }
  136.     return 0;
  137. }
Runtime error #stdin #stdout 0s 4508KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RYr6tQ
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!