fork download
copy 
  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #include <stdio.h>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <stdlib.h>
  6. #include <ctime>
  7. #include <set>
  8. #include <map>
  9. #include <queue>
  10. #include <string>
  11. #include <math.h>
  12. #include <queue>
  13. #include <memory.h>
  14. #include <iostream>
  15. #include <fstream>
  16. #include <stack>
  17. #include <complex>
  18. #include <list>
  19.  
  20. using namespace std;
  21.  
  22. void ASS(bool bb)
  23. {
  24.     if (!bb)
  25.     {
  26.         ++*(int*)0;
  27.     }
  28. }
  29.  
  30. #define FOR(i, x) for (int i = 0; i < (int)(x); ++i)
  31. #define CL(x) memset(x, 0, sizeof(x))
  32. #define CLX(x, y) memset(x, y, sizeof(x))
  33.  
  34. #pragma comment(linker, "/STACK:106777216") 
  35.  
  36. typedef vector<int> vi;
  37.  
  38. typedef long long LL;
  39.  
  40. const int K = 200;
  41. const int QK = 400;
  42.  
  43. struct M {
  44.     int x;
  45.     int* p;
  46. };
  47.  
  48. vector<M> mem;
  49. LL TotalSum;
  50.  
  51. struct Revertable {
  52.     Revertable()
  53.         : x(0)
  54.     {
  55.     }
  56.     int Get() const {
  57.         return x;
  58.     }
  59.     void Set(int xx) {
  60.         M m;
  61.         m.x = x;
  62.         m.p = &x;
  63.         mem.push_back(m);
  64.         x = xx;
  65.     }
  66.     void UnRevertableSet(int xx) {
  67.         x = xx;
  68.     }
  69. private:
  70.     int x;
  71. };
  72.  
  73. struct TBackup {
  74.     size_t pos;
  75.     LL sum;
  76.     void Init() {
  77.         pos = mem.size();
  78.         sum = TotalSum;
  79.     }
  80.     void BackUp() {
  81.         while (mem.size() > pos) {
  82.             *mem.back().p = mem.back().x;
  83.             mem.pop_back();
  84.         }
  85.         TotalSum = sum;
  86.     }
  87. };
  88.  
  89. vector<Revertable> ar;
  90. vector<Revertable> cnt;
  91.  
  92. vi values;
  93.  
  94. struct Q {
  95.     int update, x, y, id;
  96. };
  97.  
  98. void Add(int x) {
  99.     if (cnt[x].Get() == 0)
  100.         TotalSum += values[x];
  101.     cnt[x].Set(cnt[x].Get() + 1);
  102. }
  103.  
  104. void Del(int x) {
  105.     if (cnt[x].Get() == 1)
  106.         TotalSum -= values[x];
  107.     cnt[x].Set(cnt[x].Get() - 1);
  108. }
  109.  
  110. vector<LL> Solve(vi a, vector<Q> q) {
  111.     const int n = (int)a.size();
  112.     const int qn = (int)q.size();
  113.  
  114.     values = a;
  115.     FOR(i, qn) {
  116.         q[i].id = i;
  117.         if (q[i].update)
  118.             values.push_back(q[i].y);
  119.     }
  120.  
  121.     sort(values.begin(), values.end());
  122.     values.resize(unique(values.begin(), values.end()) - values.begin());
  123.  
  124.     FOR(i, n)
  125.         a[i] = (int)(lower_bound(values.begin(), values.end(), a[i]) - values.begin());
  126.  
  127.     FOR(i, qn)
  128.         if (q[i].update)
  129.             q[i].y = (int)(lower_bound(values.begin(), values.end(), q[i].y) - values.begin());
  130.  
  131.     ar.resize(n);
  132.     FOR(i, n)
  133.         ar[i].UnRevertableSet(a[i]);
  134.     cnt.resize(values.size());
  135.  
  136.     vector<LL> ans(qn);
  137.     const int c = n / K + (n % K != 0);
  138.     for (int qL = 0; qL < qn; qL += QK) {
  139.         int qR = min(qL + QK, qn);
  140.         vector< vector< vector<Q> > > qq(c + 2, vector< vector<Q> >(c + 2));
  141.         vector<Q> qu;
  142.         qu.reserve(QK);
  143.         for (int i = qL; i < qR; ++i)
  144.             if (q[i].update)
  145.                 qu.push_back(q[i]);
  146.             else
  147.                 qq[q[i].x / K + 1][q[i].y / K].push_back(q[i]);
  148.  
  149.         for (int L = 1, Lk = K; L <= c; ++L, Lk += K) {
  150.             TBackup bL;
  151.             bL.Init();
  152.             for (int R = L - 1, Rk = Lk - K; R <= c; ++R, Rk += K) {
  153.                 TBackup bR;
  154.                 bR.Init();
  155.                 size_t qpos = 0;
  156.                 const vector<Q>& z = qq[L][R];
  157.                 FOR(i, z.size()) {
  158.                     const Q& curQ = z[i];
  159.                     while (qpos < qu.size() && qu[qpos].id < curQ.id) {
  160.                         const Q& u = qu[qpos];
  161.                         if (Lk <= u.x && u.x < Rk)
  162.                             Del(ar[u.x].Get());
  163.                         ar[u.x].Set(u.y);
  164.                         if (Lk <= u.x && u.x < Rk)
  165.                             Add(ar[u.x].Get());
  166.                         ++qpos;
  167.                     }
  168.                     TBackup bQuery;
  169.                     bQuery.Init();
  170.                     if (R == L - 1) {
  171.                         for (int j = curQ.x; j < curQ.y; ++j) {
  172.                             Add(ar[j].Get());
  173.                         }
  174.                     } else {
  175.                         for (int j = curQ.x; j < Lk; ++j)
  176.                             Add(ar[j].Get());
  177.                         for (int j = Rk; j < curQ.y; ++j)
  178.                             Add(ar[j].Get());
  179.                     }
  180.                     ans[curQ.id] = TotalSum;
  181.                     bQuery.BackUp();
  182.                 }
  183.                 bR.BackUp();
  184.                 if (R >= L) {
  185.                     int Rnext = min(n, Rk + K);
  186.                     for (int i = Rk; i < Rnext; ++i)
  187.                         Add(ar[i].Get());
  188.                 }
  189.             }
  190.             bL.BackUp();
  191.         }
  192.         for (int i = qL; i < qR; ++i)
  193.             if (q[i].update)
  194.                 ar[q[i].x].UnRevertableSet(q[i].y);
  195.     }
  196.     return ans;
  197. }
  198.  
  199. vector<LL> SolveV(vi a, vector<Q> q) {
  200.     vector<LL> ans(q.size(), 0);
  201.     FOR(i, q.size()) {
  202.         if (q[i].update)
  203.             a[q[i].x] = q[i].y;
  204.         else {
  205.             map<int, int> m;
  206.             for (int j = q[i].x; j < q[i].y; ++j) {
  207.                 int &t = m[a[j]];
  208.                 if (!t) {
  209.                     t = 1;
  210.                     ans[i] += a[j];
  211.                 }
  212.             }
  213.         }
  214.     }
  215.     return ans;
  216. }
  217.  
  218. int read() {
  219.     int x;
  220.     scanf("%d", &x);
  221.     return x;
  222. }
  223.  
  224. void InputAndSolve() {
  225.     int n = read();
  226.     vi a(n);
  227.     FOR(i, n)
  228.         a[i] = read();
  229.  
  230.     int qn = read();
  231.     vector<Q> q(qn);
  232.  
  233.     FOR(i, qn) {
  234.         static char s[16];
  235.         scanf("%s%d%d", s, &q[i].x, &q[i].y);
  236.         q[i].x--;
  237.         q[i].id = i;
  238.         q[i].update = s[0] == 'U';
  239.     }
  240.  
  241.     vector<LL> ans = SolveV(a, q);
  242.     FOR(i, qn)
  243.         if (!q[i].update) {
  244. //            cout << ans[i] << "\n";
  245.             printf("%lld\n", ans[i]);
  246.         }
  247. }
  248.  
  249. int main()
  250. {
  251.     InputAndSolve();
  252.  
  253.     /*
  254.     FOR(qqq, 1000) {
  255.         int n = rand() % 10 + 10;
  256.         vi a(n);
  257.         FOR(i, n)
  258.             a[i] = rand() % (n / 2);
  259.         int qn = n * 2;
  260.         vector<Q> q(qn);
  261.         FOR(i, qn) {
  262.             q[i].id = i;
  263.             if (rand() & 1) {
  264.                 q[i].update = 1;
  265.                 q[i].x = rand() % n;
  266.                 q[i].y = rand() % (n / 2);
  267.             } else {
  268.                 q[i].update = 0;
  269.                 q[i].x = rand() % n;
  270.                 q[i].y = rand() % n;
  271.                 if (q[i].x > q[i].y)
  272.                     swap(q[i].x, q[i].y);
  273.                 q[i].y++;
  274.             }
  275.         }
  276.         vector<LL> v0 = Solve(a, q);
  277.         vector<LL> v1 = SolveV(a, q);
  278.         if (v0 != v1) {
  279.             cout << "gg" << endl;
  280.         }
  281.     }
  282.     */
  283.  
  284.     return 0;
  285. }
  286.  
Success #stdin #stdout 0s 3444KB
comments (?)
stdin
copy 
5
1 2 4 2 3                                                                              
3
Q 2 4
U 4 7
Q 2 4
stdout
copy 
6
13
https://ideone.com/zDTcuW
language:
C++ (gcc 8.3)
created:
10 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!