【权值分块】bzoj3570 DZY Loves Physics I

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

此证明有误。

DZY系列。

这题首先是几个性质：

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

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

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

a\cdot v = C

与这几个方程联立

a\cdotv=C

s=v\cdott;

v t 2= v 02 +2\cdota\cdots

解这个方程组，可以得到

v_t=√(2·C·t+v₀²)

那么

 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
",sqrt(2.0*CONST*T+sqr((double)Kth(K))));
58             }
59           else {V=R(); R(); R(); Insert(V);}
60       }
61     return 0;
62 }