fork download
copy 
  1. #include <bits/stdc++.h>
  2. #ifndef _WIN32
  3. #define getchar getchar_unlocked
  4. #endif
  5. #define ll long long
  6. #define MAGIC 32
  7. using namespace std;
  8. inline int ri()
  9. {
  10.     register char c;
  11.     register bool sgn = 0;
  12.     while(1)
  13.     {
  14.         c=getchar();
  15.         if(c == '-')
  16.         {
  17.             sgn = 1;
  18.             c = getchar();
  19.             break;
  20.         }
  21.         if(c>='0' && c<='9')break;
  22.     }
  23.     register int x=0;
  24.     while(1)
  25.     {
  26.         x=x*10+c-48;
  27.         c=getchar();
  28.         if(c<'0' || c>'9')return sgn?-x:x;
  29.     }
  30. }
  31. int n, q, a[50010];
  32. map<int, set<int> > occ;
  33. map<int, ll> bit[50010];
  34. ll realbit[50010 / MAGIC + 1][50010];
  35. void update(int i, int j, int v)
  36. {
  37.     while(i <= n)
  38.     {
  39.         if((i & -i) >= MAGIC)
  40.         {
  41.             int b = i / MAGIC;
  42.             for(int k=j; k<=n; k += k&-k)
  43.                 realbit[b][k] += v;
  44.         }
  45.         else for(int k=j; k<=n; k += k&-k)
  46.             bit[i][k] += v;
  47.         i += i&-i;
  48.     }
  49. }
  50. ll query(int i, int j)
  51. {
  52.     ll sum = 0;
  53.     while(i > 0)
  54.     {
  55.         if((i & -i) >= MAGIC)
  56.         {
  57.             int b = i / MAGIC;
  58.             for(int k=j; k>0; k -= k&-k)
  59.                 sum += realbit[b][k];
  60.         }
  61.         else for(int k=j; k>0; k -= k&-k)
  62.             sum += bit[i][k];
  63.         i -= i&-i;
  64.     }
  65.     return sum;
  66. }
  67. int32_t main()
  68. {
  69.     n = ri();
  70.     n++;
  71.     for(int i=2; i<=n; i++)
  72.         a[i] = ri();
  73.     for(int i=2; i<=n; i++)
  74.     {
  75.         set<int> &cur = occ[a[i]];
  76.         if(cur.size() == 0)
  77.         {
  78.             update(i, 1, a[i]);
  79.         }
  80.         else
  81.         {
  82.             update(i, *cur.rbegin(), a[i]);
  83.         }
  84.         cur.insert(i);
  85.     }
  86.     q = ri();
  87.     for(int i=0; i<q; i++)
  88.     {
  89.         char op = getchar();
  90.         int x, y;
  91.         while(op != 'U' && op != 'Q')
  92.             op = getchar();
  93.         x = ri(), y = ri();
  94.         x++;
  95.         if(op == 'Q')
  96.         {
  97.             y++;
  98.             printf("%lld\n", query(y, x-1) - query(x-1, x-1));
  99.         }
  100.         else
  101.         {
  102.             //erase old element
  103.             set<int> &cur = occ[a[x]];
  104.             auto j = cur.find(x);
  105.             int prv;
  106.             if(j != cur.begin())
  107.             {
  108.                 j--;
  109.                 prv = *j;
  110.                 j++;
  111.             }
  112.             else
  113.             {
  114.                 prv = 1;
  115.             }
  116.             update(x, prv, -a[x]);
  117.             j = cur.erase(j);
  118.             if(j != cur.end())
  119.             {
  120.                 update(*j, x, -a[x]);
  121.                 update(*j, prv, a[x]);
  122.             }
  123.             //insert new element
  124.             a[x] = y;
  125.             set<int> &cur2 = occ[y];
  126.             j = cur2.insert(x).first;
  127.             if(j != cur2.begin())
  128.             {
  129.                 j--;
  130.                 prv = *j;
  131.                 j++;
  132.             }
  133.             else
  134.             {
  135.                 prv = 1;
  136.             }
  137.             update(x, prv, y);
  138.             j++;
  139.             if(j != cur2.end())
  140.             {
  141.                 update(*j, x, y);
  142.                 update(*j, prv, -y);
  143.             }
  144.         }
  145.     }
  146.     return 0;
  147. }
Time limit exceeded #stdin #stdout 5s 628224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/X7kA9M
language:
C++14 (gcc 8.3)
created:
6 years 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!