[Spoj] XXXXXXXX - Sum of Distinct Numbers

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : XXXXXXXX - Sum of Distinct Numbers
Source            : Spoj 
Category          : Data Structure
Algorithm         : MOs Algorithm with Update
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll          long long
 
static const int N = 6e4 + 5;
static const int BLOCK = 230;
static const int maxn = 2e6 + 5;
 
struct MO
{
    int l, r, id, t;
    MO(int l = 0, int r = 0, int id = 0, int t = 0)
    {
           this->l = l;
           this->r = r;
           this->id = id;
           this->t = t;
    }
    friend bool operator < (MO A, MO B)
    {
        int AL = A.l / BLOCK;
        int BL = B.l / BLOCK;
        int AR = A.r / BLOCK;
        int BR = B.r / BLOCK;
        if (AL == BL)
        {
            if (AR == BR) return A.t < B.t;
            return AR < BR;
        }
        return AL < BL;
    }
} Q[maxn];
 
struct NODE
{
    int pos;
    ll pre, now;
    NODE(int pos = 0, ll pre = 0, ll now = 0)
    {
           this->pos = pos;
           this->pre = pre;
           this->now = now;
    }
} U[maxn];
 
ll arr[maxn], last[maxn], ANS[maxn];
ll f[maxn], dammy[maxn];
ll sum, SUM[maxn];
 
int l, r, t;
 
inline void ADD(int pos)
{
    ll num = arr[pos];
    f[num]++;
    if (f[num] == 1) sum += dammy[num];
}
 
inline void REMOVE(int pos)
{
    ll num = arr[pos];
    f[num]--;
    if (f[num] == 0) sum -= dammy[num];
}
 
 
inline void APPLY(int pos, ll val)
{
    if (l <= pos && pos <= r)
    {
        REMOVE(pos);
        arr[pos] = val;
        ADD(pos);
    }
    else
    {
        arr[pos] = val;
    }
}
 
map <ll, ll> MAP;
ll temp[maxn];
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    int tNum, tQuery;
    scanf("%d", &tNum);
    for (int i = 1; i <= tNum; i++)
    {
        scanf("%lld", &arr[i]);
        last[i] = arr[i];
        temp[i] = arr[i];
    }
    sort(temp+1, temp+tNum+1);
    ll cnt = 0;
    for (int i = 1; i <= tNum; i++)
    {
        ll val = temp[i];
        if (MAP.find(val) == MAP.end())
        {
            cnt++;
            MAP[val] = cnt;
            dammy[cnt] = val;
        }
    }
    for (int i = 1; i <= tNum; i++)
    {
        last[i] = arr[i] = MAP[arr[i]];
    }
    int u = 0;
    int q = 0;
    scanf("%d", &tQuery);
    for (int i = 0; i < tQuery; i++)
    {
        char type[4];
        scanf("%s", type);
        if (type[0] == 'U')      // update
        {
            int pos;
            ll value;
            scanf("%d %lld", &pos, &value);
            ll tempValue;
            if (MAP.find(value) == MAP.end())
            {
                cnt++;
                MAP[value] = cnt;
                tempValue = cnt;
                dammy[cnt] = value;
            }
            tempValue = MAP[value];
            U[++u] = {pos, last[pos], tempValue};
            last[pos] = tempValue;
        }
        else
        {
            int a, b;
            scanf("%d %d", &a, &b);
            Q[q] = {a, b, q, u};
            q++;
        }
    }
    sort(Q, Q+q);
    l = 1;
    r = 0;
    t = 0;
    sum = 0;
    for (int i = 0; i < q; i++)
    {
        int L = Q[i].l;
        int R = Q[i].r;
        int T = Q[i].t;
        while (t < T)
        {
            t++;
            APPLY(U[t].pos, U[t].now);
        }
        while (t > T)
        {
            APPLY(U[t].pos, U[t].pre);
            t--;
        }
        while (l > L)          ADD(--l);
        while (r < R)          ADD(++r);
        while (l < L)          REMOVE(l++);
        while (r > R)          REMOVE(r--);
        ANS[Q[i].id] = sum;
    }
    for (int i = 0; i < q; i++)
    {
        printf("%lld\n", ANS[i]);
    }
}