fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define task "B"
  3. using namespace std;
  4. #define ll long long
  5. #define ld long double
  6. #define vi vector<int>
  7. #define vl vector<ll>
  8. #define pii pair<int,int>
  9. #define pll pair<ll, ll>
  10. #define fi first
  11. #define se second
  12. #define pb push_back
  13. #define ep emplace_back
  14. #define pf push_front
  15. #define For(i,a,b) for(int i=a; i<=b; ++i)
  16. #define rof(i,b,a) for(int i=b; i>=a; --i)
  17. const int N=1e5+100;
  18. int n,q;
  19. ll a[N+10],b[N+10],f1[N+10],f2[N+10];
  20.  
  21. void up(int id, ll x, ll f[])
  22. {
  23.     for(++id; id<N; id+= id & -id) f[id]+=x;
  24. }
  25. ll kq(int l, int r, ll f[]){
  26.     ll res=0;
  27.     for(++r;r;r-= r & -r){
  28.         res+=f[r];
  29.     }
  30.     for(; l; l-= l & -l) res-=f[l];
  31.     return res;
  32. }
  33.  
  34. int main(){
  35.     ios::sync_with_stdio(0);
  36.     cin.tie(0);
  37.     cin>>n>>q;
  38.     For(i,1,n)
  39.     {
  40.         cin>>a[i];
  41.     }
  42.     For(i,1,n) up(i,a[i],f1);
  43.     int l=n, r=0;
  44.     while(q--)
  45.     {
  46.         char c;
  47.         cin>>c;
  48.         if(c=='A'){
  49.             ll x;
  50.             cin>>x;
  51.             a[++l]=x;
  52.             up(l,x,f1);
  53.         }
  54.         else if(c=='D'){
  55.             up(l,-a[l],f1);
  56.             --l;
  57.         }
  58.         else if(c=='L'){
  59.             up(l,-a[l],f1);
  60.             b[++r]=a[l];
  61.             --l;
  62.             up(r,b[r],f2);
  63.         }
  64.         else if(c=='R'){
  65.             up(r,-b[r],f2);
  66.             a[++l]=b[r];
  67.             --r;
  68.             up(l,a[l],f1);
  69.         }
  70.         else{
  71.             int L, R;
  72.             cin>>L>>R;
  73.             if(R<=l){
  74.                 cout<<kq(L,R,f1)<<'\n';
  75.             }
  76.  
  77.             else{
  78.                 cout<<kq(L,l,f1)+kq(l+r-R+1,r,f2)<<'\n';
  79.             }
  80.         }
  81.     }
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/M7J5ez
language:
C++ (gcc 8.3)
created:
10 days 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!