题目
题目大意
给定$n$个一维数轴上的点，每个点有两个值$r_i,q_i$，位于$x_i$，定义两个点$i,j$能匹配为$x_i-r_i\le x_j\le x_i+r_i,x_j-r_j\le x_i\le x_j+r_j$，且$\vert q_i-q_j\vert\le k$，$k$为给定的值
求有多少对点可以匹配
Example
input
3 2
3 6 1
7 3 10
10 5 8
output
1
题解
如果先按$r$排序，这样如果前面的能和后面的匹配，后面的也一定能和前面的匹配
如果把区间$[l,r]$分成$[l,mid]$和$[mid+1,r]$，只用考虑前后面区间对前面每个点的影响，每个区间按$q$值排序，这样前面区间的每个点对应着后面区间的一段连续的点（指$q$值相差不超过$k$），且端点单调递增，这个可以双指针移动解决，然后树状数组区间查询$[x_i-r_i,x_i+r_i]$
开始先按$q$排序再处理$r$，然后遇到$r$相等的情况就自闭了……
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=3e5+5;
struct p{
int x,id;
bool operator< (const p &a)
const{
return x<a.x;
}
}A[MAX];
int n,k,cnt,ID,Mr;
LL ans;
int s[MAX],nL[MAX],nR[MAX],nX[MAX],L[MAX],R[MAX],X[MAX],q[MAX],_[MAX],id[MAX],_id[MAX],a[MAX],b[MAX];
bool cmp(int a,int b) {return _[a]<_[b];}
int lowbit(int x) {return x&-x;}
void change(int x,int d)
{
for(int i=x;i<=ID;i+=lowbit(i))
s[i]+=d;
}
int ask(int x)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))
ans+=s[i];
return ans;
}
int ask(int l,int r) {return ask(r)-ask(l-1);}
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void Solve(int l=1,int r=n)
{
if(l==r) return;
int mid=(l+r>>1),_L=mid+1,_R=mid+1;
Solve(l,mid),Solve(mid+1,r);
for(int i=l;i<=r;++i)
id[i]=_id[i];
for(int i=l;i<=mid;++i)
{
while(_L<=r&&q[id[_L]]<q[id[i]]-k) change(X[id[_L]],-1),++_L;
while(_R<=r&&q[id[_R]]<=q[id[i]]+k) change(X[id[_R]],1),++_R;
ans+=ask(L[id[i]],R[id[i]]);
}
while(_L<_R) change(X[id[_L]],-1),++_L;
for(int i=l,L=l,R=mid+1;i<=r;++i)
{
if(L<=mid&&(q[id[L]]<=q[id[R]]||R>r)) _id[i]=id[L],++L;
else if(R<=r&&(q[id[L]]>q[id[R]]||L>mid)) _id[i]=id[R],++R;
}
}
int main()
{
n=read(),k=read();
for(int i=1;i<=n;++i)
_id[i]=i,nX[i]=read(),Mr=max(Mr,_[i]=read()),q[i]=read(),A[++cnt]=(p){nX[i],i},A[++cnt]=(p){nL[i]=max(nX[i]-_[i],0),i},A[++cnt]=(p){nR[i]=nX[i]+_[i],i};
sort(A+1,A+1+cnt),A[0].x=-1;
for(int i=1;i<=cnt;++i)
{
if(A[i].x!=A[i-1].x) ++ID;
if(nX[A[i].id]==A[i].x) X[A[i].id]=ID;
if(nL[A[i].id]==A[i].x) L[A[i].id]=ID;
if(nR[A[i].id]==A[i].x) R[A[i].id]=ID;
}
return sort(_id+1,_id+1+n,cmp),Solve(),printf("%I64d",ans),0;
}
