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. ll f[100005]={0};
  23. ll a[50005];
  24. vector<pair<pair<ll,ll>,ll>> upd;
  25. unordered_map<ll,pair<ll,ll>> mp;
  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 y=upd[ct].first.second;
  61.     ll oldvalue=mp[x].second;
  62.     a[x]=y;
  63.     mp[x].second=y;
  64.     //cout<<x<<y<<oldvalue<<endl;
  65.     if(x>=left && x<=right)
  66.     {
  67.         f[oldvalue]--;
  68.         if(f[oldvalue]==0)
  69.             cnt-=oldvalue;
  70.         f[y]++;
  71.         if(f[y]==1)
  72.             cnt+=y;
  73.     }
  74. }
  75. void updatehatao(ll ct,ll left,ll right)
  76. {
  77.     ll x=upd[ct].first.first;
  78.     ll y=upd[ct].first.second;
  79.     ll oldvalue=mp[x].second;
  80.     a[x]=y;
  81.     mp[x].second=y;
  82.     if(x>=left && x<=right)
  83.     {
  84.         f[oldvalue]--;
  85.         if(f[oldvalue]==0)
  86.             cnt-=oldvalue;
  87.         f[y]++;
  88.         if(f[y]==1)
  89.             cnt+=y;
  90.     }
  91.  
  92. }
  93. void AcDegaYe()
  94. {
  95.     ll n,q;
  96.     cin>>n;
  97.     for(ll i=0;i<n;i++)
  98.         cin>>a[i];
  99.     ll no;
  100.     ll updtillnow=0,x,y,in=0;
  101.     cin>>q;
  102.     for(ll i=0;i<q;i++)
  103.     {
  104.         char ch;
  105.         cin>>ch;
  106.         if(ch=='Q')
  107.         {
  108.             cin>>qu[in].l>>qu[in].r;
  109.             qu[in].l--;
  110.             qu[in].r--;
  111.             qu[in].i=in;
  112.             qu[in].up=updtillnow;
  113.             in++;
  114.         }
  115.         else
  116.         {
  117.             cin>>x>>y;
  118.             x--;
  119.             upd.pb(mkp(mkp(x,y),a[x]));
  120.             mp[x]=mkp(y,a[x]);
  121.             updtillnow++;
  122.         }
  123.     }
  124.     sort(qu,qu+in,comp);
  125.     ll ml=0,mr=-1,currenttime=0;
  126.     for(ll i=0;i<in;i++)
  127.     {
  128.         ll left=qu[i].l;
  129.         ll right=qu[i].r;
  130.         while(ml>left)
  131.         {
  132.             ml--;
  133.             add(ml);
  134.         }
  135.         while(mr<right)
  136.         {
  137.             mr++;
  138.             add(mr);
  139.         }
  140.         while(ml<left)
  141.         {
  142.             remove(ml);
  143.             ml++;
  144.         }
  145.         while(mr>right)
  146.         {
  147.             remove(mr);
  148.             mr--;
  149.         }
  150.         while(currenttime<qu[i].up)
  151.         {
  152.             updatekaro(currenttime,left,right);
  153.             currenttime++;
  154.         }
  155.         while(currenttime>qu[i].up)
  156.         {
  157.             updatehatao(currenttime,left,right);
  158.             currenttime--;
  159.         }
  160.         ans[qu[i].i]=cnt;
  161.     //     for(ll i=0;i<n;i++)
  162.     //     cout<<a[i]<<" ";
  163.     // cout<<endl;
  164.     }
  165.     for(ll i=0;i<in;i++)
  166.     {
  167.         cout(ans[i]);
  168.     }
  169. }
  170.  
  171. int main()
  172. {   
  173.     fastio;
  174.     //ll t;
  175.     //cin>>t;
  176.     ll t=1;
  177.     while(t--)
  178.     {
  179.         AcDegaYe();
  180.     }
  181.     cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  182.     return 0;
  183. }
Runtime error #stdin #stdout 0s 4400KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dCRkgS
problem XXXXXXXX, based on SPOJ submission 25441824 (CPP14), 2020-02-23 08:42:49
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!