Cod sursă (job #816117)

#include "bits/stdc++.h"
#define int long long int
const int NMAX = 200005;
struct seg{
  int st, ed, len;
};
seg seg_arr[NMAX];
int seg_id[NMAX];
int arr[NMAX];

struct query{
  int l, r, k, idx, x, y;
};

int bit[NMAX];
int m;

void Bit_Update(int pos, int val, int n){
  for(; pos <= n; pos += pos & -pos){
    bit[pos] += val;
  }
}

int Bit_Query(int pos){
  int sum = 0;
  for(; pos > 0; pos -= pos & -pos){
    sum += bit[pos];
  }
  return sum;
}

int Bit_Range(int l, int r){
  if(l > r) return 0;
  return Bit_Query(r) - Bit_Query(l - 1);
}

void Solve(){
  int n, q;
  std :: cin >> n >> q;
  for(int i = 1; i <= n; i++){
    std :: cin >> arr[i];
  }
  m = 0;
  for(int i = 1; i <= n; i++){
    if(i == 1 or arr[i] != arr[i - 1]){
      m++;
      seg_arr[m].st = i;
    }
    seg_arr[m].ed = i;
  }
  for(int i = 1; i <= m; i++){
    seg_arr[i].len = seg_arr[i].ed - seg_arr[i].st + 1;
    for(int j = seg_arr[i].st; j <= seg_arr[i].ed; j++){
      seg_id[j] = i;
    }
  }
  std :: vector < query > queries;
  std :: vector < int > ans(q, 0);
  for(int i = 0; i < q; i++){
    int l, r, k;
    std :: cin >> l >> r >> k;
    int idl = seg_id[l], idr = seg_id[r];
    if(idl == idr){
      ans[i] = ((r - l + 1) >= k ? 1 : 0);
      continue;
    }
    query qu;
    qu.l = l;
    qu.r = r;
    qu.k = k;
    qu.idx = i;
    qu.x = idl + 1;
    qu.y = idr - 1;
    ans[i] = ((seg_arr[idl].ed - l + 1) >= k ? 1 : 0) + ((r - seg_arr[idr].st + 1) >= k ? 1 : 0);
    queries.push_back(qu);
  }
  for(int i = 1; i <= m; i++){
    bit[i] = 0;
  }
  std :: vector < std :: pair < int, int > > segs;
  for(int i = 1; i <= m; i++){
    segs.push_back({seg_arr[i].len, i});
  }
  std :: sort(segs.begin(), segs.end(), [](std :: pair < int, int > a, std :: pair < int, int > b){
    return a.first > b.first;
  });
  std :: sort(queries.begin(), queries.end(), [](query a, query b){
    return a.k > b.k;
  });
  int pos = 0;
  for(auto qu : queries){
    while(pos < (int)segs.size() and segs[pos].first >= qu.k){
      Bit_Update(segs[pos].second, 1, m);
      pos++;
    }
    int cnt = Bit_Range(qu.x, qu.y);
    ans[qu.idx] += cnt;
  }
  for(int i = 0; i < q; i++){
    std :: cout << ans[i] << '\n';
  }
}

signed main(){
  std :: ios_base :: sync_with_stdio(false);
  std :: cin.tie(0);
  freopen("calin.in", "r", stdin);
  freopen("calin.out", "w", stdout);
  Solve();
  return 0;
}