Cod sursă (job #805409)

#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e5+2;
const int LMAX = 20;
using pii = pair<int, int>;
using tii = tuple<int, int, int>;
int n,q,v[NMAX],ans[NMAX];
set<pii> s;
vector<tii> queries[NMAX];
vector<pii> updates[NMAX];

ifstream fin("calin.in");
ofstream fout("calin.out");

struct AIB {
  int n;
  vector<int> bit;
  AIB(){}
  AIB(int _n){
    n = _n;
    bit.resize(n+1);
  }
  int query(int pos){
    int ans = 0;
    for(int i = pos; i > 0; i -= (i&-i)){
      ans += bit[i];
    }
    return ans;
  }
  void update(int pos, int val){
    for(int i = pos; i <= n; i += (i&-i)){
      bit[i] += val;
    }
  }
  int range(int l, int r){
    if(l > r){
      return 0;
    }
    return query(r) - query(l-1);
  }
  int kth(int k){
    int pos = 0, sum = 0;
    for(int i = LMAX-1; i >= 0; i--){
      int nwpos = pos+(1<<i);
      if(nwpos <= n && sum+bit[nwpos] <= k){
        sum += bit[nwpos];
        pos = nwpos;
      }
    }
    return pos;
  }
};

int main() {
  fin >> n >> q;
  pii curr = {1, 0};
  for(int i = 1; i <= n; i++){
    fin >> v[i];
    if(v[i] == v[i-1]){
      curr.second = i;
    }else{
      auto [l, r] = curr;
      int len = r-l+1;
      updates[len].push_back(curr);
      curr = {i, i};
    }
  }
  auto [l, r] = curr;
  int len = r-l+1;
  updates[len].push_back(curr);

  for(int i = 1; i <= q; i++){
    int l, r, k;
    fin >> l >> r >> k;
    queries[k].push_back({l, r, i});
  }
  AIB cnt(n), isSet(n);
  for(int i = n; i >= 1; i--){
    for(auto [l, r]: updates[i]){
      cnt.update(l, 1);
      cnt.update(r, 1);
      isSet.update(l, 1);
      isSet.update(r+1, -1);
    }
    auto getR = [&](int l) -> int {
      int k = cnt.query(l);
      if(cnt.query(l)%2 == 0){
        k--;
      }
      return cnt.kth(k)+1;
    };
    auto getL = [&](int r) -> int {
      int k = cnt.query(r)-1;
      if(cnt.query(r)%2 == 0){
        k--;
      }
      return cnt.kth(k)+1;
    };
    /*cout << "@ i = " << i << "\n";
    cout << "cnt =   ";
    for(int j = 1; j <= n; j++){
      cout << cnt.query(j) - cnt.query(j-1) << " ";
    }
    cout << "\n";
    cout << "spcnt = ";
    for(int j = 1; j <= n; j++){
      cout << cnt.query(j) << " ";
    }
    cout << "\n";
    cout << "isSet = ";
    for(int j = 1; j <= n; j++){
      cout << isSet.query(j) << " ";
    }
    cout << "\n";*/
    for(auto [l, r, idx]: queries[i]){
      int res = 0;
      // cout << "query " << l << ", " << r << ": ";
      if(isSet.query(l)){
        int endR = getR(l);
        if(endR-l+1 >= i){
          res++;
        }
        // cout << "l <-- " << endR+1 << "\n";
        l = endR+1;
      }
      if(l <= r && isSet.query(r)){
        int beginL = getL(r);
        if(r-beginL+1 >= i){
          res++;
        }
        // cout << "r <-- " << beginL-1 << "\n";
        r = beginL-1;
      }
      // cout << l << ", " << r << "\n";
      res += cnt.range(l, r)/2;
      ans[idx] = res;
    }
  }
  for(int i = 1; i <= q; i++){
    fout << ans[i] << "\n";
  }
  return 0;
}
/**
111111111112222222222233333333333
100000000001000000000010000000000
[----------]   ...    [---------]
             [-----------]
**/