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. bool prime(ll n) 
  21. { 
  22.     if (n <= 1)  return false; 
  23.     if (n <= 3)  return true; 
  24.     if (n%2 == 0 || n%3 == 0) return false; 
  25.  
  26.     for (ll i=5; i*i<=n; i=i+6) 
  27.         if (n%i == 0 || n%(i+2) == 0) 
  28.            return false; 
  29.  
  30.     return true; 
  31. }
  32. ll power(ll x,ll y) 
  33. { 
  34.     ll temp; 
  35.     if(y==0) 
  36.         return 1; 
  37.     temp=power(x,y/2); 
  38.     if (y%2==0) 
  39.         return temp*temp; 
  40.     else
  41.         return x*temp*temp; 
  42. } 
  43. ll no_of_factors(ll n) 
  44. { 
  45.     ll cnt = 0; 
  46.     for (ll i = 1; i <= sqrt(n); i++) 
  47.     { 
  48.         if (n % i == 0) 
  49.         { 
  50.             if (n / i == i) 
  51.                 cnt++; 
  52.  
  53.             else 
  54.                 cnt = cnt + 2; 
  55.         } 
  56.     } 
  57.     return cnt; 
  58. } 
  59. ll gcd(ll a,ll b) 
  60. { 
  61.     if (b==0) 
  62.         return a; 
  63.     return gcd(b,a%b);      
  64. } 
  65. bool subsequence_checker(string str1, string str2, ll m, ll n) 
  66. { 
  67.     if (m == 0) return true; 
  68.     if (n == 0) return false; 
  69.     if (str1[m-1] == str2[n-1]) 
  70.         return subsequence_checker(str1, str2, m-1, n-1); 
  71.     return subsequence_checker(str1, str2, m, n-1); 
  72. }
  73. bool isPowerOfTwo (ll x)  
  74. {  
  75.     return x && (!(x&(x-1)));  
  76. }  
  77. bool incs(ll *a,ll n)
  78. {
  79.     if(n==1)
  80.         return true;
  81.     for(ll i=0;i<n-1;i++)
  82.     {
  83.         if(a[i+1]<=a[i])
  84.             return false;
  85.     }
  86.     return true;
  87. }
  88. bool decs(ll *a,ll n)
  89. {
  90.     if(n==1)
  91.         return true;
  92.     for(ll i=0;i<n-1;i++)
  93.     {
  94.         if(a[i+1]>=a[i])
  95.             return false;
  96.     }
  97.     return true;
  98. }
  99. struct test
  100. {
  101. public:
  102.     ll x,y,z;
  103. };
  104. bool compare(const test &aa,const test &bb)
  105. {
  106.     if(aa.x==bb.x)
  107.     {
  108.         if(aa.y==bb.y)
  109.         {
  110.             return aa.z<bb.z;
  111.         }
  112.         return aa.y<bb.y;
  113.     }
  114.     return aa.x<bb.x;
  115. }
  116.  
  117. ll mm(ll a, ll m=mod) 
  118. { 
  119.     ll m0 = m; 
  120.     ll y = 0, x = 1; 
  121.  
  122.     if (m == 1) 
  123.       return 0; 
  124.  
  125.     while (a > 1) 
  126.     { 
  127.         // q is quotient 
  128.         ll q = a / m; 
  129.         ll t = m; 
  130.  
  131.         // m is remainder now, process same as 
  132.         // Euclid's algo 
  133.         m = a % m, a = t; 
  134.         t = y; 
  135.  
  136.         // Update y and x 
  137.         y = x - q * y; 
  138.         x = t; 
  139.     } 
  140.  
  141.     // Make x positive 
  142.     if (x < 0) 
  143.        x += m0; 
  144.  
  145.     return x; 
  146. } 
  147. ll bs=1357;
  148. ll cnt=0;
  149. ll f[1000001]={0};
  150. ll a[200001];
  151. vector<pair<pair<ll,ll>,ll>> upd;
  152. unordered_map<ll,pair<ll,ll>> mp;
  153. struct query
  154. {
  155.     ll l,r,i,up;
  156. };
  157. query qu[200001];
  158. ll ans[200001];
  159. bool comp(query a,query b)
  160. {
  161.     if(a.l/bs!=b.l/bs)
  162.     {
  163.         return a.l/bs<b.l/bs;
  164.     }
  165.     if(a.r/bs!=b.r/bs)
  166.         return a.r<b.r;
  167.     return a.up<=b.up;
  168. }
  169. void add(ll pos)
  170. {
  171.     ll ele=a[pos];
  172.     f[ele]++;
  173.     if(f[ele]==1)
  174.         cnt+=ele;
  175. }
  176. void remove(ll pos)
  177. {
  178.     //cout<<a[pos]<<endl;
  179.     ll ele=a[pos];
  180.     f[ele]--;
  181.     if(f[ele]==0)
  182.         cnt-=ele;
  183. }
  184. void updatekaro(ll ct,ll left,ll right)
  185. {
  186.     ll x=upd[ct].first.first;
  187.     ll y=upd[ct].first.second;
  188.     ll oldvalue=mp[x].second;
  189.     a[x]=y;
  190.     mp[x].second=y;
  191.     //cout<<x<<y<<oldvalue<<endl;
  192.     if(x>=left && x<=right)
  193.     {
  194.         f[oldvalue]--;
  195.         if(f[oldvalue]==0)
  196.             cnt-=oldvalue;
  197.         f[y]++;
  198.         if(f[y]==1)
  199.             cnt+=y;
  200.     }
  201. }
  202. void updatehatao(ll ct,ll left,ll right)
  203. {
  204.     ll x=upd[ct].first.first;
  205.     ll y=upd[ct].first.second;
  206.     ll oldvalue=mp[x].second;
  207.     a[x]=y;
  208.     mp[x].second=y;
  209.     if(x>=left && x<=right)
  210.     {
  211.         f[oldvalue]--;
  212.         if(f[oldvalue]==0)
  213.             cnt-=oldvalue;
  214.         f[y]++;
  215.         if(f[y]==1)
  216.             cnt+=y;
  217.     }
  218.  
  219. }
  220. void AcDegaYe()
  221. {
  222.     ll n,q;
  223.     cin>>n>>q;
  224.     for(ll i=0;i<n;i++)
  225.         cin>>a[i];
  226.     ll no;
  227.     ll updtillnow=0,x,y,in=0;
  228.     for(ll i=0;i<q;i++)
  229.     {
  230.         char ch;
  231.         cin>>ch;
  232.         if(ch=='Q')
  233.         {
  234.             cin>>qu[in].l>>qu[in].r;
  235.             qu[in].l--;
  236.             qu[in].r--;
  237.             qu[in].i=in;
  238.             qu[in].up=updtillnow;
  239.             in++;
  240.         }
  241.         else
  242.         {
  243.             cin>>x>>y;
  244.             x--;
  245.             upd.pb(mkp(mkp(x,y),a[x]));
  246.             mp[x]=mkp(y,a[x]);
  247.             updtillnow++;
  248.         }
  249.     }
  250.     sort(qu,qu+in,comp);
  251.     ll ml=0,mr=-1,currenttime=0;
  252.     for(ll i=0;i<in;i++)
  253.     {
  254.         ll left=qu[i].l;
  255.         ll right=qu[i].r;
  256.         while(ml>left)
  257.         {
  258.             ml--;
  259.             add(ml);
  260.         }
  261.         while(mr<right)
  262.         {
  263.             mr++;
  264.             add(mr);
  265.         }
  266.         while(ml<left)
  267.         {
  268.             remove(ml);
  269.             ml++;
  270.         }
  271.         while(mr>right)
  272.         {
  273.             remove(mr);
  274.             mr--;
  275.         }
  276.         while(currenttime<qu[i].up)
  277.         {
  278.             updatekaro(currenttime,left,right);
  279.             currenttime++;
  280.         }
  281.         while(currenttime>qu[i].up)
  282.         {
  283.             updatehatao(currenttime,left,right);
  284.             currenttime--;
  285.         }
  286.         ans[qu[i].i]=cnt;
  287.     //     for(ll i=0;i<n;i++)
  288.     //     cout<<a[i]<<" ";
  289.     // cout<<endl;
  290.     }
  291.     for(ll i=0;i<in;i++)
  292.     {
  293.         cout(ans[i]);
  294.     }
  295. }
  296.  
  297. int main()
  298. {   
  299.     fastio;
  300.     //ll t;
  301.     //cin>>t;
  302.     ll t=1;
  303.     while(t--)
  304.     {
  305.         AcDegaYe();
  306.     }
  307.     cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  308.     return 0;
  309. }
Runtime error #stdin #stdout 0s 4408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/13oYrG
problem XXXXXXXX, based on SPOJ submission 25432616 (CPP14), 2020-02-21 11:58:56
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!