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 n;
  21. ll bs=1357;
  22. ll cnt=0;
  23. ump f;
  24. ll a[200005];
  25. ll pvh[200005];
  26. ll orig[200005];
  27. vector<pair<pair<ll,ll>,ll>> upd;
  28. struct query
  29. {
  30.     ll l,r,i,up;
  31. };
  32. query qu[200005];
  33. ll ans[200005];
  34. vector<pair<ll,ll*>> compress;
  35.  
  36. bool comp(query a,query b)
  37. {
  38.     if(a.l/bs!=b.l/bs)
  39.     {
  40.         return a.l/bs<b.l/bs;
  41.     }
  42.     if(a.r/bs!=b.r/bs)
  43.         return a.r<b.r;
  44.     return a.up<b.up;
  45. }
  46. bool comp1(pair<ll,ll*> aa,pair<ll,ll*> bb)
  47. {
  48.     return aa.first<bb.first;
  49. }
  50. void add(ll pos)
  51. {
  52.     ll ele=a[pos];
  53.     f[ele]++;
  54.     if(f[ele]==1)
  55.         cnt+=orig[ele];
  56. }
  57. void remove(ll pos)
  58. {
  59.     //cout<<a[pos]<<endl;
  60.     ll ele=a[pos];
  61.     f[ele]--;
  62.     if(f[ele]==0)
  63.         cnt-=orig[ele];
  64. }
  65. void updatekaro(ll ct,ll left,ll right)
  66. {
  67.     ll x=upd[ct].first.first;
  68.     ll oldvalue=a[x];
  69.     //cout<<x<<y<<oldvalue<<endl;
  70.     if(x>=left && x<=right)
  71.     {
  72.         f[oldvalue]--;
  73.         if(f[oldvalue]==0)
  74.             cnt-=orig[oldvalue];
  75.     }
  76.     a[x]=upd[ct].first.second;
  77.     ll y=a[x];
  78.     if(x>=left && x<=right)
  79.     {
  80.         f[y]++;
  81.         if(f[y]==1)
  82.             cnt+=orig[y];
  83.     }
  84. }
  85. void updatehatao(ll ct,ll left,ll right)
  86. {
  87.     ll x=upd[ct].first.first;
  88.     ll oldvalue=a[x];
  89.     if(x>=left && x<=right)
  90.     {
  91.         f[oldvalue]--;
  92.         if(f[oldvalue]==0)
  93.             cnt-=orig[oldvalue];
  94.     }
  95.     a[x]=upd[ct].second;
  96.     ll y=a[x];
  97.     if(x>=left && x<=right)
  98.     {
  99.         f[y]++;
  100.         if(f[y]==1)
  101.             cnt+=orig[y];
  102.     }
  103.  
  104. }
  105. void compression()
  106. {
  107.     sort(compress.begin(),compress.end());
  108.     ll curr = compress[0].first;
  109.     ll idx = 0;
  110.     for(ll i = 0; i < compress.size(); i++)
  111.     {
  112.         if(curr != compress[i].first) idx++;
  113.         curr = compress[i].first;
  114.         orig[idx] = curr;
  115.         *compress[i].second = idx;
  116.     }
  117. }
  118. void AcDegaYe()
  119. {
  120.     ll q;
  121.     cin>>n;
  122.     for(ll i=0;i<n;i++)
  123.     {
  124.         cin>>a[i];
  125.         pvh[i]=a[i];
  126.         compress.pb(mkp(a[i],&a[i]));
  127.     }
  128.     ll no;
  129.     ll updtillnow=0,x,y,in=0;
  130.     cin>>q;
  131.     for(ll i=0;i<q;i++)
  132.     {
  133.         char ch;
  134.         cin>>ch;
  135.         if(ch=='Q')
  136.         {
  137.             cin>>qu[in].l>>qu[in].r;
  138.             qu[in].l--;
  139.             qu[in].r--;
  140.             qu[in].i=in;
  141.             qu[in].up=updtillnow;
  142.             in++;
  143.         }
  144.         else
  145.         {
  146.             cin>>x>>y;
  147.             x--;
  148.             upd.pb(mkp(mkp(x,y),pvh[x]));
  149.             compress.pb(mkp(y,&y));
  150.             pvh[x]=y;
  151.             updtillnow++;
  152.         }
  153.     }
  154.     compression();
  155.     for(ll i=0;i<n;i++)
  156.     {
  157.         a[i]=compress[i].first;
  158.         pvh[i]=compress[i].first;
  159.     }
  160.     for(ll i=0;i<updtillnow;i++)
  161.     {
  162.         upd[i].first.second=compress[i].first;
  163.         upd[i].second=pvh[x];
  164.         pvh[x]=compress[i].first;
  165.     }
  166.     sort(qu,qu+in,comp);
  167.     ll ml=0,mr=-1,currenttime=0;
  168.     for(ll i=0;i<in;i++)
  169.     {
  170.         ll left=qu[i].l;
  171.         ll right=qu[i].r;
  172.         while(ml>left)
  173.         {
  174.             ml--;
  175.             add(ml);
  176.         }
  177.         while(mr<right)
  178.         {
  179.             mr++;
  180.             add(mr);
  181.         }
  182.         while(ml<left)
  183.         {
  184.             remove(ml);
  185.             ml++;
  186.         }
  187.         while(mr>right)
  188.         {
  189.             remove(mr);
  190.             mr--;
  191.         }
  192.         while(currenttime<qu[i].up)
  193.         {
  194.             updatekaro(currenttime,left,right);
  195.             currenttime++;
  196.         }
  197.         while(currenttime>qu[i].up)
  198.         {
  199.             updatehatao(currenttime-1,left,right);
  200.             currenttime--;
  201.         }
  202.         ans[qu[i].i]=cnt;
  203.     //     for(ll i=0;i<n;i++)
  204.     //     cout<<a[i]<<" ";
  205.     // cout<<endl;
  206.     }
  207.     for(ll i=0;i<in;i++)
  208.     {
  209.         cout(ans[i]);
  210.     }
  211. }
  212.  
  213. int main()
  214. {   
  215.     fastio;
  216.     //ll t;
  217.     //cin>>t;
  218.     ll t=1;
  219.     while(t--)
  220.     {
  221.         AcDegaYe();
  222.     }
  223.     cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  224.     return 0;
  225. }
Runtime error #stdin #stdout 0s 4296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OtbP1g
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!