考慮兩個質量均為m，速度分別v1、v2的小球發生完全彈性碰撞的影響：
由動能守恒得：
$\frac{1}{2}mv_1^2+\frac{1}{2}mv_2^2=\frac{1}{2}mv_1'^2+\frac{1}{2}mv_2'^2$
$v_1^2+v_2^2=v_1'^2+v_2'^2$
由動量守恒得：
$mv_1+mv_2=mv_1'+mv_2'$
$v_1+v_2=v_1'+v_2'$
$v_1^2+v_2^2+2v_1v_2=v_1'^2+v_2'^2+2v_1'v_2'$
所以
$v_1v_2=v_1'v_2'$
$v_1'=v_2$
$v_2'=v_1$
結論：兩個質量相同的小球發生完全彈性碰撞后交換速度。
?
由于詢問的是第k小的速率，并沒有要求是哪個小球，所以可以視為小球并沒有發生碰撞，而是直接按原速度穿過去，所以直接計算出每個小球在t時刻的速度就可以了。
?
現在考慮怎么求速度：
每一時刻加速度$av=C$
而加速度可以看做是速度函數的導數，
設$f(x)$為x時刻的速度，$f(0)=v$，$f(x)f'(x)=C$
解得
$f(x)=\sqrt{2Cx+v^2}$
?
因為在t時刻，影響最終速度排名的只有初速度v，所以只需要用數據結構維護v的順序就可以了。
時間復雜度$O((n+q)\log n)$
?
?
#include<cstdio>
#include<cmath>
#define N 200010
using namespace std;
typedef long long ll;
const double A=0.8;
int n,c,x,y,z,size[N],son[N][2],val[N],f[N],tot,root,data[N],id[N],cnt;
int ins(int x,int p){size[x]++;int b=p>=val[x];if(!son[x][b]){son[x][b]=++tot;f[tot]=x;size[tot]=1;val[tot]=p;return tot;}else return ins(son[x][b],p);
}
void dfs(int x){if(son[x][0])dfs(son[x][0]);data[++cnt]=val[x];id[cnt]=x;if(son[x][1])dfs(son[x][1]);
}
int build(int fa,int l,int r){int mid=(l+r)>>1,x=id[mid];f[x]=fa;son[x][0]=son[x][1]=0;size[x]=1;val[x]=data[mid];if(l==r)return x;if(l<mid)size[x]+=size[son[x][0]=build(x,l,mid-1)];if(r>mid)size[x]+=size[son[x][1]=build(x,mid+1,r)];return x;
}
inline int rebuild(int x){cnt=0;dfs(x);return build(f[x],1,cnt);
}
inline void insert(int p){if(!root){root=tot=size[1]=1;val[1]=p;return;}int x=ins(root,p);int deep=0;int z=x;while(f[z])z=f[z],deep++;if(deep<log(tot)/log(1/A))return;while((double)size[son[x][0]]<A*size[x]&&(double)size[son[x][1]]<A*size[x])x=f[x];if(!x)return;if(x==root){root=rebuild(x);return;}int y=f[x],b=son[y][1]==x,now=rebuild(x);son[y][b]=now;
}
inline int kth(int k){int x=root,sum;while(1){sum=size[son[x][0]]+1;if(k==sum)return val[x];if(k<sum)x=son[x][0];else k-=sum,x=son[x][1];}
}
inline void read(int&a){char c;bool f=0;a=0;while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));if(c!='-')a=c-'0';else f=1;while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';if(f)a=-a;
}
int main(){read(n);read(c);while(n--)read(x),read(y),read(z),insert(x);read(n);while(n--){read(x);if(x)read(y),read(z),z=kth(z),printf("%.3f\n",sqrt(2*(ll)c*(ll)y+(ll)z*(ll)z));else read(x),read(y),read(y),insert(x);}return 0;
}
?
?
)
)
)
)
