Subtask 2: All $k$ equal

The intervals with intersection at least $k$ with $[\ell_i, r_i]$ are all intervals besides those satisfying $r_j<\ell+k$ or $\ell_j>r-k$. Note that these inequalities can't hold simultaneously, as it would imply $r_j-\ell_j<\ell-r+2k<k$, contradicting the requirement that all intervals have length at least $k$.

So our answer is simply $N-1$ minus the number of intervals satisfying each inequality, which can be computed with sorting (and optionally, binary search).

Full Solution:

To count the number of intervals with intersection at least $k_i$ with $[\ell_i,r_i]$, count the number of intervals with length at least $k_i$, and subtract out those with right endpoint $<l_i+k_i$ or left endpoint $>r_i-k_i$. Since an interval with left endpoint $>r_i-k_i$ and right endpoint $<l_i+k_i$ must have length $<l_i-r_i+2k_i\le k_i$, no interval is subtracted more than once.

Since we may compute the counts in any order, let's sort them in decreasing order of $k$. Maintain lists of the left endpoints and right endpoints of the intervals with length at least $k$. As $k$ decreases, we need to efficiently add to the lists and answer queries of the form: how many elements in the list are $\le x$ for some given $x$? There are many ways to do this, such as using a binary indexed tree with coordinate compression, or an order statistic tree in C++.

Implementation with order statistic tree (Benjamin Chen):

#include <bits/stdc++.h>
using namespace std;

#define ar array

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mxN=2e5;
int n, l[mxN], r[mxN], k[mxN], ans[mxN], len_order[mxN], k_order[mxN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> l[i] >> r[i] >> k[i];
		len_order[i] = k_order[i] = i;
	}
	sort(len_order, len_order + n, [](int a, int b) { return make_pair(r[a]-l[a], a) > make_pair(r[b]-l[b], b); });
	sort(k_order, k_order + n, [](int a, int b) { return make_pair(k[a], a) > make_pair(k[b], b); });
	Tree<ar<int, 2>> left_endpoints, right_endpoints;
	for (int i = 0, j = 0; i < n; ++i) {
		for (; j < n && r[len_order[j]] - l[len_order[j]] >= k[k_order[i]]; ++j) {
			left_endpoints.insert({l[len_order[j]], j});
			right_endpoints.insert({r[len_order[j]], j});
		}
		ans[k_order[i]] = j - 1;
		ans[k_order[i]] -= j - left_endpoints.order_of_key({r[k_order[i]] - k[k_order[i]] + 1, -1});
	   	ans[k_order[i]]	-= right_endpoints.order_of_key({l[k_order[i]] + k[k_order[i]], -1});
	}
	for (int i=0; i<n; ++i)
		cout << ans[i] << "\n";
	return 0;
}

Implementation with binary indexed tree and coordinate compression (Brandon Wang):

#include <algorithm>
#include <iostream>
#include <map>
 
const int MAXN = 200005;
const int MAXT = 4 * MAXN + 5;
 
int N;
int l[MAXN];
int r[MAXN];
int k[MAXN];
 
std::map<int, int> cc;
std::vector<int> coords;
 
std::pair<int, std::pair<int, int>> keys[MAXN];
std::pair<std::pair<int,int>, std::pair<int,int>> queries[MAXN];
 
int ans[MAXN];
int lbit[MAXT];
int rbit[MAXT];
 
void input () {
	std::cin >> N;
	for (int i = 0; i < N; i++) {
		std::cin >> l[i] >> r[i] >> k[i];
	}
}
 
void compress () {
	for (int i = 0; i < N; i++) {
		coords.push_back(l[i]);
		coords.push_back(r[i]);
		coords.push_back(l[i] + k[i] - 1);
		coords.push_back(r[i] - k[i] + 1);
	}
	std::sort(coords.begin(), coords.end());
	int idx = 1;
	for (int i = 0; i < int(coords.size()); i++) {
		cc[coords[i]] = idx;
		idx++;
	}
}
 
void proc () {
	for (int i = 0; i < N; i++) {
		keys[i] = {r[i] - l[i], {cc[l[i]], cc[r[i]]}};
		queries[i] = {{k[i], i}, {cc[l[i]+k[i]-1], cc[r[i]-k[i]+1]}};
	}
	std::sort(keys, keys+N);
	std::sort(queries, queries+N);
}
 
void lupd (int x, int d) {
	while (x < MAXT) {
		lbit[x] += d;
		x += (x & (-x));
	}
}
 
void rupd (int x, int d) {
	while (x < MAXT) {
		rbit[x] += d;
		x += (x & (-x));
	}
}
 
int lqr (int x) {
	if (x == 0) return 0;
	return lbit[x] + lqr(x - (x & (-x)));
}
 
int rqr (int x) {
	if (x == 0) return 0;
	return rbit[x] + rqr(x - (x & (-x)));
}
 
void solve () {
	int qdx = N-1;
	for (int i = (N-1); i >= 0; i--) {
		while ((qdx >= 0) && (queries[qdx].first.first > keys[i].first)) {
			int idx = queries[qdx].first.second;
			ans[idx] += (N-2-i);
			ans[idx] -= rqr(queries[qdx].second.first);
			ans[idx] -= (lqr(MAXT-1) - lqr(queries[qdx].second.second - 1));
			// std::cout << queries[qdx].first.second << " " << queries[qdx].second.first << " " << queries[qdx].second.second << "\n";
			qdx--;
		}
		lupd(keys[i].second.first, 1);
		// std::cout << keys[i].second.first << " " << keys[i].second.second << "\n";
		rupd(keys[i].second.second, 1);
	}
	while (qdx >= 0) {
		int idx = queries[qdx].first.second;
		ans[idx] += (N-1);
		ans[idx] -= rqr(queries[qdx].second.first);
		ans[idx] -= (lqr(MAXT-1) - lqr(queries[qdx].second.second - 1));
		// std::cout << queries[qdx].first.second << " " << queries[qdx].second.first << " " << queries[qdx].second.second << "\n";
		qdx--;
	}
}
 
void print () {
	for (int i = 0; i < N; i++) {
		std::cout << ans[i] << "\n";
	}
}
 
int main () {
	std::cin.tie(0);
	std::ios_base::sync_with_stdio(0);
	input();
	compress();
	proc();
	solve();
	print();
}