思路:
考虑函数 \(\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;
}
标签:typedef,ATC,ll,long,pair,Contact,CF924D,operatorname,define
From: https://www.cnblogs.com/rgw2010/p/18373297