HackerEarth Mathison and the exceptional list solution

In this HackerEarth Mathison and the exceptional list problem solution Mathison has practiced different operations that can be performed on lists. Unfortunately, he has found a set of operations that he cannot perform efficiently so he asks for your help.

You start with an empty list, on which you perform N operations. In one operation (e, L, R) you add e to the back of the list and print the number of exceptional subarrays with the length between L and R inclusive, in the current version of the list. An exceptional subarray is defined to be a subarray of the list that contains only unique elements (i.e. no two elements share the same value).

HackerEarth Mathison and the exceptional list problem solution.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <numeric>
#include <cassert>

using namespace std;

constexpr int MAX_N = 500'000 + 2;
array<long long, MAX_N> fenwick1, fenwick2;

inline constexpr int lsb(int x){
  return x & -x;
}

void update(array<long long, MAX_N> &fenwick, int pos, long long value){
  while (pos < MAX_N){
    fenwick[pos] += value;
    pos += lsb(pos);
  }
}

void update_range(int a, int b, long long value){
  update(fenwick1, a, value);
  update(fenwick1, b + 1, -value);
  update(fenwick2, a, value * (a - 1));
  update(fenwick2, b + 1, -value * b);
}

long long query(const array<long long, MAX_N> &fenwick, int pos){
  long long sum = 0;

  while (pos > 0){
    sum += fenwick[pos];
    pos -= lsb(pos);
  }

  return sum;
}

long long query(int b){
  return 1LL * query(fenwick1, b) * b - query(fenwick2, b);
}

long long query_range(int a, int b){
  if (a > b)
    return 0;
  else
    return query(b) - query(a - 1);
}

int main(){
  ios_base::sync_with_stdio(false);

  int N;
  cin >> N;
  assert(1 <= N && N <= 500'000);

  unordered_map<int, int> umap;
  umap.reserve(4096);
  umap.max_load_factor(0.25);

  int last_pos = -1;

  for (int i = 0; i < N; i++){
    int e;
    cin >> e;
    assert(0 <= e && e <= 1'000'000'000);

    int L, R;
    cin >> L >> R;
    assert(1 <= L && L <= N);
    assert(1 <= R && R <= N);

    auto it = umap.find(e);

    if (it != umap.end())
      last_pos = max(last_pos, it->second);

    umap[e] = i;
    int lg = i - last_pos;

    update_range(1, lg, +1);

    auto s = query_range(L, R);
    assert(s >= 0);
    cout << s << "n";
  }

  return 0;
}

Second solution

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 5;
long long lazy[4 * MAXN];
long long seg[4 * MAXN];
pair<int, int> temp[MAXN];
int e[MAXN], l[MAXN], r[MAXN];
int MX[MAXN];
int dp[MAXN];

void update(int node, int start, int end, int qs, int qe) {
    if(lazy[node]) {
        seg[node] += 1LL * lazy[node] * (end - start + 1);
        if(start != end) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    if(start > end or qe < start or qs > end) return;
    if(start >= qs and end <= qe) {
        seg[node] += 1LL * (end - start + 1);
        if(start != end) {
            lazy[2 * node]++;
            lazy[2 * node + 1]++;
        }
        return;
    }
    int mid = (start + end) >> 1;
    update(2 * node, start, mid, qs, qe);
    update(2 * node + 1, mid + 1, end, qs, qe);
    seg[node] = seg[2 * node] + seg[2 * node + 1];
}

long long query(int node, int start, int end, int qs, int qe) {
    if(lazy[node]) {
        seg[node] += 1LL * lazy[node] * (end - start + 1);
        if(start != end) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    if(start > end or qe < start or qs > end) return 0;
    if(start >= qs and end <= qe) {
        return seg[node];
    }
    int mid = (start + end) >> 1;
    long long ret = query(2 * node, start, mid, qs, qe) + query(2 * node + 1, mid + 1, end, qs, qe);
    seg[node] = seg[2 * node] + seg[2 * node + 1];
    return ret;
}
int main() {
    int q;
    scanf("%d", &q);
    assert(q <= 500000 and q >= 1);
    for(int i = 1; i <= q; i++) {
        scanf("%d%d%d", &e[i], &l[i], &r[i]);
        assert(e[i] >= 1 and e[i] <= 1000000000);
        assert(l[i] >= 1 and l[i] <= q);
        assert(r[i] >= 1 and r[i] <= q);
        temp[i].first = e[i];
        temp[i].second = i;
    }
    sort(temp + 1, temp + 1 + q);
    int cur = 1;
    e[temp[1].second] = cur;
    for(int i = 2; i <= q; i++) {
        if(temp[i].first != temp[i - 1].first) ++cur;
        e[temp[i].second] = cur;
    }
    for(int i = 1; i <= q; i++) {
        int mx = MX[e[i]];
        mx = max(mx, dp[i - 1]);
        MX[e[i]] = i;
        dp[i] = mx;
        update(1, 1, q, 1, i - mx);
        printf("%lldn", query(1, 1, q, l[i], r[i]));
    }
    return 0;
}

HackerEarth Mathison and the exceptional list problem solution.

Second solution

Related Tutorials