首页 > 代码库 > 【权值分块】bzoj3570 DZY Loves Physics I

【权值分块】bzoj3570 DZY Loves Physics I

2024-08-03 20:59:56   218人阅读

以下部分来自：http://www.cnblogs.com/zhuohan123/p/3726306.html

DZY系列。

这题首先是几个性质：

　　1.所有球质量相同，碰撞直接交换速度，而球又没有编号，那么就可以直接视作两个球没有碰撞。

　　2.所有的方向、初始位置都没有任何用处。

然后就是速度的问题了，根据题设

a⋅v=C
 
与这几个方程联立
 
a⋅v=C
s=v·t;
vt2=v02+2·a·s
 
解这个方程组，可以得到

vt=√(2·C·t+v02)

那么T时刻的速度vT的相对大小就直接由v0决定了，我们只需要找到第k小的v0，直接输出答案即可。

 

现在问题在于：支持插入，查询全局K大值。

平衡树显然可做，但是 权值线段树/权值树状数组 不是更快吗？

但是 权值分块 竟然更快呢？

可能是因为其极小的常数 以及 插入时O(1) 的复杂度吧。

 

 

 1 #include<cstdio> 2 #include<cmath> 3 using namespace std; 4 #define max(a,b) (((a)>(b))?(a):(b)) 5 int n,K,V,v[100001],m,b[100001],LIMIT,sz,sum,sumv[350],l[350],r[350],num[100001]; 6 bool op; 7 double CONST,T; 8 inline int R(){ 9     char c=0;int f=1,x;10     for(;c<‘0‘||c>‘9‘;c=getchar())if(c==‘-‘)f=-1;11     for(x=0;c>=‘0‘&&c<=‘9‘;c=getchar())(x*=10)+=(c-‘0‘);12     x*=f; return x;13 }14 void makeblock()15 {16     sz=sqrt(LIMIT); if(!sz) sz=1; r[0]=-1;17     for(sum=1;sum*sz<LIMIT;sum++)18       {19           l[sum]=r[sum-1]+1;20           r[sum]=sum*sz;21           for(int i=l[sum];i<=r[sum];i++) num[i]=sum;22       }23     l[sum]=r[sum-1]+1;24     r[sum]=LIMIT;25     for(int i=l[sum];i<=r[sum];i++) num[i]=sum;26 }27 void Insert(const int &x){b[x]++; sumv[num[x]]++;}28 inline int Kth(const int &x)29 {30     int cnt=0;31     for(int i=1;;i++)32       {33         cnt+=sumv[i];34         if(cnt>=x)35           {36             cnt-=sumv[i];37             for(int j=l[i];;j++)38             {cnt+=b[j]; if(cnt>=x) return j;}39           }40       }41 }42 inline double sqr(const double &x){return x*x;}43 int main()44 {45     n=R(); CONST=(double)R();46     for(int i=1;i<=n;i++)47       {48           v[i]=R(); R(); R();49           LIMIT=max(LIMIT,v[i]);50       } makeblock(); m=R();51     for(int i=1;i<=n;i++) Insert(v[i]);52     for(int i=1;i<=m;i++)53       {54           op=R(); if(op)55             {56                 T=(double)R(); K=R();57                 printf("%.3f\n",sqrt(2.0*CONST*T+sqr((double)Kth(K))));58             }59           else {V=R(); R(); R(); Insert(V);}60       }61     return 0;62 }

【权值分块】bzoj3570 DZY Loves Physics I


联系
我们