HackerEarth Length of arithmetic progressions solution

In this HackerEarth Length of arithmetic progressions problem solution, You are given an integer array A of size N. You are also given Q queries. In each query, you are given three integers L, R, and D respectively.

You are required to determine the length of the largest contiguous segment in the indices range [L, R] of A that forms an arithmetic progression with a common difference of D.

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const ll N = 400005;
char en = 'n';
ll inf = 1e16;
ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
  ll res = 1;
  x %= mod;
  while (n) {
    if (n & 1)
      res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
}

struct data {
  // Use required attributes
  int sum, left, right;
  int len;
  // Default Values
  data() : sum(0), left(0), right(0), len(1){};
};

struct SegTree {
  int N;
  vector<data> st;
  vector<bool> cLazy;
  vector<int> lazy;

  void init(int n) {
    N = n;
    st.resize(4 * N + 5);
    cLazy.assign(4 * N + 5, false);
    lazy.assign(4 * N + 5, 0);
  }

  // Write reqd merge functions
  void merge(data &cur, data &l, data &r) {
    cur.sum = max(l.sum, r.sum);
    cur.sum = max(cur.sum, l.right + r.left);

    cur.left = max(l.left, ((l.sum == l.len) ? (l.sum + r.left) : 0ll));
    cur.right = max(r.right, ((r.sum == r.len) ? (r.sum + l.right) : 0ll));
    cur.len = l.len + r.len;
  }

  // Handle lazy propagation appriopriately
  void propagate(int node, int L, int R) {
    if (L != R) {
      cLazy[node * 2] = 1;
      cLazy[node * 2 + 1] = 1;
      lazy[node * 2] = lazy[node];
      lazy[node * 2 + 1] = lazy[node];
    }
    st[node].sum = st[node].left = st[node].right = lazy[node];

    cLazy[node] = 0;
    lazy[node] = 0;
  }

  void build(int node, int L, int R) {
    if (L == R) {
      // st[node].mn = 1e9;
      return;
    }
    int M = (L + R) / 2;
    build(node * 2, L, M);
    build(node * 2 + 1, M + 1, R);
    merge(st[node], st[node * 2], st[node * 2 + 1]);
  }

  data Query(int node, int L, int R, int i, int j) {
    if (cLazy[node])
      propagate(node, L, R);
    if (j < L || i > R)
      return data();
    if (i <= L && R <= j)
      return st[node];
    int M = (L + R) / 2;
    data left = Query(node * 2, L, M, i, j);
    data right = Query(node * 2 + 1, M + 1, R, i, j);
    data cur;
    merge(cur, left, right);
    return cur;
  }

  data pQuery(int node, int L, int R, int pos) {
    if (cLazy[node])
      propagate(node, L, R);
    if (L == R)
      return st[node];
    int M = (L + R) / 2;
    if (pos <= M)
      return pQuery(node * 2, L, M, pos);
    else
      return pQuery(node * 2 + 1, M + 1, R, pos);
  }

  void Update(int node, int L, int R, int i, int j, int val) {
    if (cLazy[node])
      propagate(node, L, R);
    if (j < L || i > R)
      return;
    if (i <= L && R <= j) {
      cLazy[node] = 1;
      lazy[node] = val;
      propagate(node, L, R);
      return;
    }
    int M = (L + R) / 2;
    Update(node * 2, L, M, i, j, val);
    Update(node * 2 + 1, M + 1, R, i, j, val);
    merge(st[node], st[node * 2], st[node * 2 + 1]);
  }

  void pUpdate(int node, int L, int R, int pos, int val) {
    if (cLazy[node])
      propagate(node, L, R);
    if (L == R) {
      cLazy[node] = 1;
      lazy[node] = val;
      propagate(node, L, R);
      return;
    }
    int M = (L + R) / 2;
    if (pos <= M)
      pUpdate(node * 2, L, M, pos, val);
    else
      pUpdate(node * 2 + 1, M + 1, R, pos, val);
    merge(st[node], st[node * 2], st[node * 2 + 1]);
  }

  data query(int pos) { return pQuery(1, 1, N, pos); }

  data query(int l, int r) {
    if (l > r)
      return data();
    return Query(1, 1, N, l, r);
  }

  void update(int pos, int val) { pUpdate(1, 1, N, pos, val); }

  void update(int l, int r, int val) { Update(1, 1, N, l, r, val); }
};

// Problem 1 (Max Query - Point Update with Coordinate Compression):
// http://codeforces.com/gym/100733/problem/F Solution 1:
// http://codeforces.com/gym/100733/submission/41643795

// Problem 2 (Min Query - Offline processing):
// https://codeforces.com/problemset/problem/522/D Solution 2:
// https://codeforces.com/contest/522/submission/45493164

struct Query {
  ll L, R;
  ll D;
  ll indx;
  Query() {}
  Query(ll L, ll R, ll D, ll indx) : L(L), R(R), D(D), indx(indx) {}
};
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll n, q;
  cin >> n >> q;

  ll A[n + 5];

  for (int i = 1; i <= n; i++) {
    cin >> A[i];
  }

  ll diff[n + 5];

  ll offset = 200000;

  vector<ll> indicesList[400005];

  for (ll i = 1; i < n; i++) {
    diff[i] = A[i + 1] - A[i];
    indicesList[offset + diff[i]].push_back(i);
  }

  vector<Query> queryEvent[400005];

  for (ll i = 1; i <= q; i++) {
    ll L, R, D;
    cin >> L >> R >> D;

    queryEvent[D + offset].push_back(Query(L, R, D, i));
  }

  ll ans[q + 5];

  SegTree obj;
  obj.init(n - 1);

  for (ll i = 0; i <= 400000; i++) {
    for (int indx : indicesList[i]) {
      obj.update(indx, 1);
    }
    for (Query &query : queryEvent[i]) {
      int indx = query.indx;
      ans[indx] = obj.query(query.L, query.R - 1).sum + 1;
    }
    for (int indx : indicesList[i]) {
      obj.update(indx, 0);
    }
  }

  for (int i = 1; i <= q; i++)
    cout << ans[i] << en;

  return 0;
}