fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3. #define ll long long int
  4. #define ull unsigned long long int
  5. #define ld long double
  6. #define cout(var) cout<<var<<endl
  7. #define endl '\n'
  8. #define loop(a,b,c) for(ll i=a;i<=b;i+=c)
  9. #define intarr(arr,n) ll arr[n];for(ll i=0;i<n;i++)cin>>arr[i]
  10. #define inparr(arr,n) for(ll i=0;i<n;i++)cin>>arr[i]
  11. #define inpvec(vec,n) for(ll i=0;i<n;i++){ll var;cin>>var;vec.push_back(var);}
  12. #define pb push_back
  13. #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
  14. #define mod 1000000007
  15. #define newline cout<<endl
  16. #define ump unordered_map<ll,ll>
  17. #define vec vector<ll>
  18. #define mkp make_pair
  19. #define disp(var) cout<<var<<" "
  20. ll bs=1357;
  21. ll cnt=0;
  22. ump f;
  23. ll a[50005];
  24. ll pvh[50005];
  25. vector<pair<pair<ll,ll>,ll>> upd;
  26. struct query
  27. {
  28.     ll l,r,i,up;
  29. };
  30. query qu[100005];
  31. ll ans[100005];
  32. bool comp(query a,query b)
  33. {
  34.     if(a.l/bs!=b.l/bs)
  35.     {
  36.         return a.l/bs<b.l/bs;
  37.     }
  38.     if(a.r/bs!=b.r/bs)
  39.         return a.r<b.r;
  40.     return a.up<b.up;
  41. }
  42. void add(ll pos)
  43. {
  44.     ll ele=a[pos];
  45.     f[ele]++;
  46.     if(f[ele]==1)
  47.         cnt+=ele;
  48. }
  49. void remove(ll pos)
  50. {
  51.     //cout<<a[pos]<<endl;
  52.     ll ele=a[pos];
  53.     f[ele]--;
  54.     if(f[ele]==0)
  55.         cnt-=ele;
  56. }
  57. void updatekaro(ll ct,ll left,ll right)
  58. {
  59.     ll x=upd[ct].first.first;
  60.     ll oldvalue=a[x];
  61.     //cout<<x<<y<<oldvalue<<endl;
  62.     if(x>=left && x<=right)
  63.     {
  64.         f[oldvalue]--;
  65.         if(f[oldvalue]==0)
  66.             cnt-=oldvalue;
  67.     }
  68.     a[x]=upd[ct].first.second;
  69.     ll y=a[x];
  70.     if(x>=left && x<=right)
  71.     {
  72.         f[y]++;
  73.         if(f[y]==1)
  74.             cnt+=y;
  75.     }
  76. }
  77. void updatehatao(ll ct,ll left,ll right)
  78. {
  79.     ll x=upd[ct].first.first;
  80.     ll oldvalue=a[x];
  81.     if(x>=left && x<=right)
  82.     {
  83.         f[oldvalue]--;
  84.         if(f[oldvalue]==0)
  85.             cnt-=oldvalue;
  86.     }
  87.     a[x]=upd[ct].second;
  88.     ll y=a[x];
  89.     if(x>=left && x<=right)
  90.     {
  91.         f[y]++;
  92.         if(f[y]==1)
  93.             cnt+=y;
  94.     }
  95.  
  96. }
  97. void AcDegaYe()
  98. {
  99.     ll n,q;
  100.     cin>>n;
  101.     for(ll i=0;i<n;i++)
  102.     {
  103.         cin>>a[i];
  104.         pvh[i]=a[i];
  105.     }
  106.     ll no;
  107.     ll updtillnow=0,x,y,in=0;
  108.     cin>>q;
  109.     for(ll i=0;i<q;i++)
  110.     {
  111.         char ch;
  112.         cin>>ch;
  113.         if(ch=='Q')
  114.         {
  115.             cin>>qu[in].l>>qu[in].r;
  116.             qu[in].l--;
  117.             qu[in].r--;
  118.             qu[in].i=in;
  119.             qu[in].up=updtillnow;
  120.             in++;
  121.         }
  122.         else
  123.         {
  124.             cin>>x>>y;
  125.             x--;
  126.             upd.pb(mkp(mkp(x,y),pvh[x]));
  127.             pvh[x]=y;
  128.             updtillnow++;
  129.         }
  130.     }
  131.     sort(qu,qu+in,comp);
  132.     ll ml=0,mr=-1,currenttime=0;
  133.     for(ll i=0;i<in;i++)
  134.     {
  135.         ll left=qu[i].l;
  136.         ll right=qu[i].r;
  137.         while(currenttime<qu[i].up)
  138.         {
  139.             updatekaro(currenttime,left,right);
  140.             currenttime++;
  141.         }
  142.         while(currenttime>qu[i].up)
  143.         {
  144.             updatehatao(currenttime,left,right);
  145.             currenttime--;
  146.         }
  147.         while(ml>left)
  148.         {
  149.             ml--;
  150.             add(ml);
  151.         }
  152.         while(mr<right)
  153.         {
  154.             mr++;
  155.             add(mr);
  156.         }
  157.         while(ml<left)
  158.         {
  159.             remove(ml);
  160.             ml++;
  161.         }
  162.         while(mr>right)
  163.         {
  164.             remove(mr);
  165.             mr--;
  166.         }
  167.         ans[qu[i].i]=cnt;
  168.     //     for(ll i=0;i<n;i++)
  169.     //     cout<<a[i]<<" ";
  170.     // cout<<endl;
  171.     }
  172.     for(ll i=0;i<in;i++)
  173.     {
  174.         cout(ans[i]);
  175.     }
  176. }
  177.  
  178. int main()
  179. {   
  180.     fastio;
  181.     //ll t;
  182.     //cin>>t;
  183.     ll t=1;
  184.     while(t--)
  185.     {
  186.         AcDegaYe();
  187.     }
  188.     cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  189.     return 0;
  190. }
Success #stdin #stdout #stderr 0s 4448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time elapsed: 4ms
https://ideone.com/0E4iB4
problem XXXXXXXX, based on SPOJ submission 25442011 (CPP14), 2020-02-23 09:44:18
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!