1.改高精度 ：float/double的精度为x位，小数部分最多x+x位(乘法和加法)，整数部分<1000000*1000000/2=5 * 10^11
2.分成整数部分和小数部分分别存储，貌似不可以
方法：离散化 + 每个位置的所有的值排序(上升)[避免采用树状数组时误算] + 树状数组统计之前比x大的数目( F(max_index) - F(x) )
话说：
1.125
printf("%.2lf“,x); output:1.12
用c++的setprecision也是输出1.12
话说如果真的是四舍五入的话，采用printf("%.2lf",x+0.005);
但这题不知道怎么样，应该直接printf("%.2lf“,x);就可以了~
下面代码未过，以后再改：
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <cmath> 5 #include <list> 6 #include <stack> 7 #include <vector> 8 #include <set> 9 #include <map> 10 #include <queue> 11 #include <algorithm> 12 #include <iomanip> 13 #include <iostream> 14 15 using namespace std; 16 17 struct node 18 { 19 long double p; 20 long long a; 21 }point[1000005]; 22 23 map<long,long> inde; 24 long long num[1000005]; 25 long d[1000005]; 26 long double f[1000005]; 27 long double re=0; 28 29 bool cmp(const node a,const node b) 30 { 31 return a.a<b.a; 32 } 33 34 int main() 35 { 36 long n,i,j,k,ind,gg,g; 37 scanf("%ld",&n); 38 for (i=1;i<=n;i++) 39 scanf("%ld",&d[i]); 40 41 gg=1; 42 for (i=1;i<=n;i++) 43 { 44 for (j=1;j<=d[i];j++,gg++) 45 { 46 scanf("%llf%lld",&point[gg].p,&point[gg].a); 47 // cin>>point[gg].p>>point[gg].a; 48 num[gg]=point[gg].a; 49 } 50 sort(point+gg-d[i],point+gg,cmp); 51 } 52 sort(num+1,num+gg); 53 54 inde.clear(); 55 g=0; 56 for (i=1;i<gg;i++) 57 if (i==1 || num[i]!=num[i-1]) 58 { 59 g++; 60 inde[num[i]]=g; 61 } 62 63 for (i=0;i<=g;i++) 64 f[i]=0; 65 66 gg=1; 67 for (i=1;i<=n;i++) 68 { 69 for (j=1;j<=d[i];j++,gg++) 70 { 71 ind=inde[point[gg].a]; 72 k=ind; 73 while (k>=1) 74 { 75 re=re-f[k]*point[gg].p; 76 k=k-(k & (-k)); 77 } 78 79 k=g; 80 while (k>=1) 81 { 82 re=re+f[k]*point[gg].p; 83 k=k-(k & (-k)); 84 } 85 86 k=ind; 87 while (k<=g) 88 { 89 f[k]=f[k]+point[gg].p; 90 k=k+(k & (-k)); 91 } 92 } 93 } 94 95 printf("%.2llf ",re+0.005);//?? 96 97 return 0; 98 } 99 /* 100 2 101 4 4 102 0.25 1 0.25 2 0.25 4 0.25 3 103 0.25 1 0.25 3 0.25 2 0.25 4 104 105 3 106 4 4 4 107 0.25 1 0.25 2 0.25 4 0.25 3 108 0.25 1 0.25 3 0.25 2 0.25 4 109 0.25 1 0.25 3 0.25 2 0.25 4 110 111 2 112 1 1 113 1 1 114 1 0 115 116 3 117 5 2 118 0.1 0 0.2 1 0.3 2 0.2 3 0.2 4 119 0.6 10 0.4 -5 120 121 122 3 123 5 2 124 0.3 1 0.3 1 0.2 2 0.1 0 0.1 4 125 0.7 2 0.3 1 126 127 10 128 1 1 1 1 1 1 1 1 1 1 129 1 10 130 1 9 131 1 8 132 1 7 133 1 6 134 1 5 135 1 4 136 1 3 137 1 2 138 1 1 139 140 5 141 1 1 1 1 1 142 1 1073741824 143 1 -1073741823 144 1 -1073741823 145 1 1073741824 146 1 1073741824 147 148 3 149 3 1 2 150 0.5 -1 0.25 1 0.25 0 151 1 2 152 0.5 -1 0.5 1 153 154 2 155 5 5 156 0.2 5 0.2 4 0.2 3 0.2 2 0.2 1 157 0.2 1 0.2 2 0.2 3 0.2 4 0.2 5 158 159 2 160 1 1 161 0.12345 2 162 0.34214 1 163 164 2 165 3 3 166 0 1 0 1 1 2 167 0 -1 1 1 0 -100 168 169 1 170 5 171 0.2 1 0.1 -2 0.3 -1 0.1 1 0.3 5 172 173 2 174 5 5 175 0.2 -10 0.2 -10 0.2 -10 0.2 -10 0.2 -10 176 0.2 -10 0.2 -10 0.1 -20 0.1 -20 0.4 30 177 178 */