Disharmony Trees 树状数组

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 #include <algorithm>
 5 using namespace std;
 6 #define ll long long
 7 typedef struct abcd
 8 {
 9     ll x,f,i;
10 } abcd;
11 abcd a[110000];
12 bool cmp1(abcd x,abcd y)
13 {
14     return x.x<y.x;
15 }
16 bool cmp2(abcd x,abcd y)
17 {
18     return x.f<y.f;
19 }
20 typedef struct abc
21 {
22     ll sum,ci;
23 }abc;
24 abc aa[110000];
25 ll need,need1,n;
26 ll lowbit(ll x)
27 {
28     return x&(-x);
29 }
30 void update(ll x)
31 {
32     ll y=x;
33     while(x<=n)
34     {
35         aa[x].ci++;
36         aa[x].sum+=y;
37         x+=lowbit(x);
38     }
39 }
40 ll fun(ll x,ll y)
41 {
42     ll  ans,nu=0,sum=0,z=x;
43     while(x>0)
44     {
45         nu+=aa[x].ci;
46         sum+=aa[x].sum;
47         x-=lowbit(x);
48     }
49     ans=y*((need-sum)-(need1-nu)*z)+y*(nu*z-sum);
50     return ans;
51 }
52 int main()
53 {
54     int i,j,now,noww;
55     ll ans;
56     while(~scanf("%d",&n))
57     {
58         for(i=0; i<n; i++)
59             scanf("%I64d%I64d",&a[i].x,&a[i].f);
60         sort(a,a+n,cmp1);
61         now=a[0].x,a[0].x=1,noww=2;
62         for(i=1; i<n; i++)
63         {
64             if(a[i].x==now)a[i].x=a[i-1].x;
65             else now=a[i].x,a[i].x=noww;
66             noww++;
67         }
68         sort(a,a+n,cmp2);
69         now=a[0].f,a[0].f=1,noww=2;
70         for(i=1; i<n; i++)
71         {
72             if(a[i].f==now)a[i].f=a[i-1].f;
73             else now=a[i].f,a[i].f=noww;
74             noww++;
75         }
76         need=0,need1=0;
77         ans=0;
78         memset(aa,0,sizeof(aa));
79         for(i=n-1;i>=0;i--)
80         {
81             ans+=fun(a[i].x,a[i].f);
82             update(a[i].x);
83             need+=a[i].x;
84             need1++;
85         }
86         cout<<ans<<endl;
87     }
88 }