Mo's Algorithm

#include<bits/stdc++.h>
using namespace std;
const int N = 3e4, Q = 2e5;
int n, k, q, block;
struct QE
{
    int l, r, id;
    bool operator < (const QE & other) const
    {
        return l/k < other.l/k || (l/k == other.l/k && r < other.r);
    }
};
QE Query[Q + 1];
int a[N + 1], ans[Q + 1], res, Left, Right;
map<int, int> Container;
void read()
{
   cin >> n; k = sqrt(n); block = -1;
   for (int i = 1; i <= n; ++ i)
   {
       cin >> a[i];
   }
   cin >> q;
   for (int i = 1; i <= q; ++ i)
   {
       cin >> Query[i].l >> Query[i].r;
       Query[i].id = i;
   }
   sort(Query + 1, Query + q + 1);
}
void Refresh(int i)
{
    Left = Query[i].l; Right = Query[i].r;
    res = 0;
    Container.clear();
    block = Query[i].l/k;
    for (int j = Query[i].l; j <= Query[i].r; ++ j)
    {
        ++Container[a[j]];
        if (Container[a[j]] == 1)
        {
            ++res;
        }
    }
}
void solve()
{
   for (int i = 1; i <= q; ++ i)
   {
       if (Query[i].l / k != block)
       {
           Refresh(i);
       }
       else
       {
           while (Left < Query[i].l)
           {
               --Container[a[Left]];
               if (Container[a[Left]] == 0)
               {
                   --res;
               }
               ++Left;
           }
           while (Left > Query[i].l)
           {
               --Left;
               ++Container[a[Left]];
               if (Container[a[Left]] == 1)
               {
                   ++res;
               }
           }
           while (Right > Query[i].r)
           {
               --Container[a[Right]];
               if (Container[a[Right]] == 0)
               {
                   --res;
               }
               --Right;
           }
           while (Right < Query[i].r)
           {
               ++Right;
               ++Container[a[Right]];
               if (Container[a[Right]] == 1)
               {
                   ++res;
               }
           }
       }
       ans[Query[i].id] = res;
   }
   for (int i = 1; i <= q; ++ i)
   {
       cout << ans[i] << '\n';
   }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read();
    solve();
}