我的代码cdq一段复杂度应为 $O(n \log^2 n)$，其中 $n$ 是题干给的两倍，实测运行到cdq前耗时不超过400ms，到cdq后 TLE，cdq是模板题复制的，没发现复杂度有假

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,inf=2e9;
int n,n_;
struct node{
	int a,b,c;
	//l-r,-r,l(贡献)
	//-k,-l-k,r-k (查询)
	vector<int>id;
	int ans,cnt;
	friend bool operator ==(node x_,node y_){
		return x_.a==y_.a&&x_.b==y_.b&&x_.c==y_.c;
	}
};
bool cmp1(node x,node y){
	if(x.a!=y.a){
		return x.a<y.a;
	}
	if(x.b!=y.b){
		return x.b<y.b;
	}
	return x.c<y.c;
}
bool cmp2(node x,node y){
	if(x.b!=y.b){
		return x.b<y.b;
	}
	if(x.c!=y.c){
		return x.c<y.c;
	}
	return x.a<y.a;
}
vector<node>arr;
int tree[N];
int tmp[N];
int ans[N];
int lobit(int x){
	return x&(-x);
}
void add(int x,int val){
	for(int i=x;i<=n;i+=lobit(i)){
		tree[i]+=val;
	}
}
int query(int x){
	int res=0;
	for(int i=x;i;i-=lobit(i)){
		res+=tree[i];
	}
	return res;
}
void cdq(int l,int r){
	if(l==r){
		arr[l].ans+=arr[l].cnt-1;
		return;
	}
	int mid=(l+r)>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	sort(arr.begin()+l,arr.begin()+mid+1,cmp2);
	sort(arr.begin()+mid+1,arr.begin()+r+1,cmp2);
	int j=l;
	for(int i=mid+1;i<=r;i++){
		while(j<=mid&&arr[j].b<=arr[i].b){
			add(arr[j].c,arr[j].cnt);
			++j;
		}
		arr[i].ans+=query(arr[i].c);
	}
	for(int i=l;i<j;i++){
		add(arr[i].c,-arr[i].cnt);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("1.in","r",stdin); 
	cin>>n;
	n_=n;
	for(int i=1;i<=n;i++){
		int l,r,k;
		cin>>l>>r>>k;
		node tmp={l-r,-r,l,{},-inf,1};
		arr.push_back(tmp);
		tmp={-k,-l-k,r-k,{},0,0};
		tmp.id.push_back(i);
		arr.push_back(tmp);
	}
	sort(arr.begin(),arr.end(),cmp1);
	n<<=1;
	for(int i=1;i<n;i++){
		if(arr[i]==arr[i-1]){
			if(arr[i].cnt){
				arr[i-1].cnt++;
			}else{
				arr[i-1].id.push_back(arr[i].id[0]);
			}
			arr[i-1].ans=max(arr[i-1].ans,arr[i].ans);
			arr.erase(arr.begin()+i);
			--i;
			--n;
		}
	}
	arr.insert(arr.begin(),{0,0,0,{},0,0});
	for(int i=1;i<=n;i++){
		tmp[i]=arr[i].c;
	}
	sort(tmp+1,tmp+n+1);
	for(int i=1;i<=n;i++){
		arr[i].c=lower_bound(tmp+1,tmp+1+n,arr[i].c)-tmp;
	}
	cdq(1,n);
	for(int i=1;i<=n;i++){
		int lim=arr[i].id.size();
		for(int j=0;j<lim;j++){
			ans[arr[i].id[j]]=arr[i].ans;
		}
	}
	for(int i=1;i<=n_;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}