Cod sursă (job #805410)

#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{
      int l, r;
      tie(l, r) = curr;
      int len = r-l+1;
      updates[len].push_back(curr);
      curr = {i, i};
    }
  }
  int l, r;
  tie(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 it: updates[i]){
      int l, r;
      tie(l, r) = it;
      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;
    };
    for(auto it: queries[i]){
      int l, r, idx;
      tie(l, r, idx) = it;
      int res = 0;
      if(isSet.query(l)){
        int endR = getR(l);
        if(endR-l+1 >= i){
          res++;
        }
        l = endR+1;
      }
      if(l <= r && isSet.query(r)){
        int beginL = getL(r);
        if(r-beginL+1 >= i){
          res++;
        }
        r = beginL-1;
      }
      res += cnt.range(l, r)/2;
      ans[idx] = res;
    }
  }
  for(int i = 1; i <= q; i++){
    fout << ans[i] << "\n";
  }
  return 0;
}