CF924D Contact ATC

思路：

考虑函数 \(\operatorname{F}(v_0)_i\) 表示风速为 \(v_0\) 时，\(i\) 到达原点的时间，易得：

\[\operatorname{F}(v_0)_i = \frac{x_i}{v_i+v_0} \]

则若 \((i,j)\) 满足条件，需要满足 \(\operatorname{F}(v_0)_i\) 与 \(\operatorname{F}(v_0)_j\) 的交点的横坐标在 \([-m,m]\) 间，那么若 \(\operatorname{F}(v_0)_i=\operatorname{F}(v_0)_j\)，即 \(\operatorname{F}(v_0)_i-\operatorname{F}(v_0)_j=0\)。

根据零点存在定理：若区间 \([l,r]\) 满足 \(\operatorname{f}(l) \le 0\) 且 \(\operatorname{f}(r) \ge 0\)，且函数连续，则 \([l,r]\) 至少有一个 \(\operatorname{f}(x)\) 的零点。

那么判定 \(\operatorname{F}(v_0)_i-\operatorname{F}(v_0)_j=0\) 在 \([-w,w]\) 是否有零点，只需要满足 \(\operatorname{F}(-w)_i-\operatorname{F}(-w)_j \le 0\) 且 \(\operatorname{F}(w)_i-\operatorname{F}(w)_j \ge 0\)

注意到 \(\operatorname{F}(x)_i\) 有单调性，则设 \(l_i=\operatorname{F}(-w)_i,r_i=\operatorname{F}(w)_i\)。

则需要满足 \(l_i \le l_j<0\) 即 \(l_i \le l_j\)，且 \(r_i-r_j \ge 0\) 即 \(r_i \ge r_j\)。

那么若 \([l_i,r_i]\) 将 \([l_j,r_j]\) 包含，则 \((i,j)\) 是有贡献的，这个问题是简单题，不作多说，直接树状数组维护即可。

时间复杂度为 \(O(N \log N)\)。

注意离散化。

完整代码：

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double ld;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=1e6+10;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
struct Node{
    ll l,r;
	bool operator<(const Node&rhs)const{
		if(r!=rhs.r)
		  return r<rhs.r;
		return l>rhs.l;
	}
}A[N];
ll T,n,m,l1,l2,ans;
ld L[N],R[N],h1[N],h2[N];
ll x[N],v[N],a[N];
void add(ll x){
	for(int i=x;i<=l1;i+=lowbit(i))
	  a[i]++;
}
ll query(ll x){
	ll ans=0;
	for(int i=x;i;i-=lowbit(i))
	  ans+=a[i];
	return ans;
}
void work(ld &x){
	x=floor(x*1e11)/1e11;
}
void solve(){
    l1=l2=ans=0;
    n=read(),m=read();
    For(i,1,n){
        x[i]=-read();
        v[i]=read();
        L[i]=(ld)x[i]/((ld)v[i]-m);
        R[i]=(ld)x[i]/((ld)v[i]+m);
        work(L[i]),work(R[i]);
        h1[++l1]=L[i];
        a[l1]=0;
        h2[++l2]=R[i];
    }
    sort(h1+1,h1+l1+1);
    l1=unique(h1+1,h1+l1+1)-(h1+1);
    sort(h2+1,h2+l2+1);
    l2=unique(h2+1,h2+l2+1)-(h2+1);
    For(i,1,n){
        A[i].l=lower_bound(h1+1,h1+l1+1,L[i])-h1;
        A[i].r=lower_bound(h2+1,h2+l2+1,R[i])-h2;
        //cerr<<A[i].l<<' '<<A[i].r<<'\n';
    }
    sort(A+1,A+n+1);
	for(int i=1;i<=n;i++){
		ans+=i-1-query(A[i].l-1);
		add(A[i].l);
	}
    write(ans);
    putchar('\n');
}
bool End;
int main(){
    //open("wind.in","wind.out");
    T=1;
    while(T--)
      solve();
	return 0;
}

原文链接：CF924D Contact ATC