Mo_algorithm.cpp

const int N = 50002;
int len, n, q;
int vis[N], ans[N];
int a[N], ans_mo;

struct Query{int l, r, in;} Q[N];

bool cmp(const Query& p, const Query& q){
  return p.r/len < q.r/len or p.r/len == q.r/len and p.l > q.l;
}

void add(int x){
  if(vis[x]) return;
  vis[x] = 1;
  ans_mo += a[x];
}

void remove(int x){
  if(not vis[x]) return;
  vis[x] = 0;
  ans_mo -= a[x];
}

int mo_query(){
  return ans_mo; 
}

void solve(){
  len = (int) sqrt(n + .0) + 1;
  sort(Q, Q+q, cmp);

  int l = 0, r = 0;
  for(int i = 0; i < q; ++i){
      while(l < Q[i].l) remove(l++);
      while(l > Q[i].l) add(--l);
      r = max(l, r);
      while(r <= Q[i].r) add(r++);
      while(r > Q[i].r+1) remove(--r);
      ans[Q[i].in] = mo_query();
  }
}