介绍一种与众不同的分治方式，获得了目前的最优解！

Step 1

首先看这个题，要维护垂直且相交的线段对个数，如果没有 $T$ 的限制很好做，离线下来扫描线就可以了，而且离散化后还可以直接用树状数组。但现在有限制，考虑 cdq。如果直接分成第 $[l,mid],[mid+1,r]$ 条线段，算 $[l,mid]$ 给 $[mid+1,r]$ 的贡献，那么对于 $[mid+1,r]$ 前面的一段，在 $[l,mid]$ 中满足 $T$ 这个条件的线段区间也是不同的，感觉没法简单地这么做。

Step 2

因此，我们把区间 $[l,r]$（第 $[l,r]$ 条线段）分成这个样子：

从左到右分别称为左段、中段、右段。我们发现，贡献有三种：左段对右段、左段对中段、中段对右段。

其中左段对右段的贡献，因为中间隔了长为 $T-1$ 的中段，所以右段任意线段都可能与左段的任意线段产生贡献。所以忽略掉 $T$ 限制，对左段水平、垂直的线段各自离线下来，右段排序后扫描线得到左段对右段的贡献。

剩下的左段对中段、中段对右段的贡献，我们分别递归左段中段、中段右段这两个区间即可。如果区间长度小于等于 $T$ 就不可能再有贡献，返回。

Step 3

这个分治的递归有些诡异，我们来分析一下时间复杂度。下面的式子令题目中 $T$ 为 $l$，初始的 $n$ 为 $N$ 以便区分。则其时间复杂度有

$$T(n)= \begin{cases} 2T(\frac{n+l}{2}) + (n-l) \log N &n > l\\ 1 &n \le l \end{cases}$$

算一下得到，其时间复杂度为 $O((n-T)\log(n-T)\log n)$，那么总时间复杂度就是 $O((n-T)\log(n-T)\log n + n \log n)$，完全可以通过。

Step 4

放代码。

#include<bits/stdc++.h>
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define db long double
#define Pii pair<int,int>
#define fi first
#define se second
#define inline
#define f(x,y) fixed<<setprecision(y)<<x
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,rp,stdin),p1==p2)?EOF:*p1++)

using namespace std;
const int N=1e5+10;
const int rp=1e6+10;

int n,t,bx[N],by[N],cx[N],cy[N]; ll ans;
struct side{int xl,yl,xr,yr;}p[N],b[N];
struct node{int id,x,v;}ax[N],ay[N];
char buf[rp],*p1=buf,*p2=buf;

inline int read()
{
	int x=0,f=1; char c=0;
    while(!isdigit(c)) {if(c=='-') f=-1; c=gc();}
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=gc();
    return x*f;
}

inline char read_ch()
{
	char c=0;
	while((!isalpha(c))&&(!isdigit(c))) c=gc();
	return c;
}

inline bool cmp(node q,node w) {return q.id<w.id;}
inline bool cmp2(side q,side w)
{
	if((q.xl==q.xr)!=(w.xl==w.xr)) return q.xl==q.xr;//注意 cmp 要具有传递性！
	if(q.xl==q.xr) return q.xl<w.xl;//都垂直，按 x 排
	return q.yl<w.yl;//都水平，按 y 排
}

inline void upd(int c[],int x,int v)
{
	while(x<N) c[x]+=v,x+=x&-x;//普通树状数组
}

inline int get(int c[],int x)
{
	int v=0;
	while(x) v+=c[x],x-=x&-x;
	return v;
}

inline void solve(int L,int R)
{
	if(R-L+1<=t) return;//区间长度小于 T，不会有贡献
	int mi=(L+R)>>1,lmi=mi-t/2,rmi=mi+t/2;//分成三段
	int cntx=0,cnty=0,nwx=1,nwy=1;
	for(int i=L;i<=lmi;++i)//左端搞成扫描线形式
		if(p[i].yl==p[i].yr)//分讨水平垂直
		{
			//yl=yr
			ay[++cnty]={p[i].xl+1,p[i].yl,1};//注意线段端点不算！！！
			ay[++cnty]={p[i].xr,p[i].yl,-1};
		}
		else
		{
			//xl=xr
			ax[++cntx]={p[i].yl+1,p[i].xl,1};
			ax[++cntx]={p[i].yr,p[i].xl,-1};
		}
	sort(ax+1,ax+cntx+1,cmp);//排序
	sort(ay+1,ay+cnty+1,cmp);
	for(int i=rmi;i<=R;++i) b[i]=p[i];
	sort(b+rmi,b+R+1,cmp2);
	for(int i=rmi;i<=R;++i)//右端排序后扫描线查询
		if(b[i].xl==b[i].xr)//分讨水平垂直
		{
			//xl=xr
			while(nwy<=cnty&&ay[nwy].id<=b[i].xl)
				upd(cy,ay[nwy].x,ay[nwy].v),++nwy;//在她前面的全部做完
			ans+=get(cy,b[i].yr-1)-get(cy,b[i].yl);//注意线段端点不算！！！
		}
		else
		{
			//yl=yr
			while(nwx<=cntx&&ax[nwx].id<=b[i].yl)
				upd(cx,ax[nwx].x,ax[nwx].v),++nwx;
			ans+=get(cx,b[i].xr-1)-get(cx,b[i].xl);
		}
	while(nwx<=cntx) upd(cx,ax[nwx].x,ax[nwx].v),++nwx;//做完，相当于清空树状数组
	while(nwy<=cnty) upd(cy,ay[nwy].x,ay[nwy].v),++nwy;
	solve(L,rmi-1); solve(lmi+1,R);
}

signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	n=read(); t=read();
	for(int i=1;i<=n;++i)
	{
		p[i].xl=bx[i]=read();
		p[i].yl=by[i]=read();
	}
	sort(bx+1,bx+n+1); int cntx=unique(bx+1,bx+n+1)-bx-1;//离散化
	sort(by+1,by+n+1); int cnty=unique(by+1,by+n+1)-by-1;
	for(int i=1;i<=n;++i)
	{
		p[i-1].xr=p[i].xl=lower_bound(bx+1,bx+cntx+1,p[i].xl)-bx;
		p[i-1].yr=p[i].yl=lower_bound(by+1,by+cnty+1,p[i].yl)-by;
	}
	for(int i=1;i<n;++i)
	{
		if(p[i].xl>p[i].xr) swap(p[i].xl,p[i].xr);//判一下大小
		if(p[i].yl>p[i].yr) swap(p[i].yl,p[i].yr);
	}
	solve(1,n-1); cout<<ans;
	return 0;
}