牛客练习赛7 E珂朵莉的数列（树状数组+爆long long解决方法）

https://www.nowcoder.com/acm/contest/38/E

题意：

思路：

树状数组维护。从大佬那里学习了如何处理爆long long的方法。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int maxn = +;

 int n;

 int a[maxn],b[maxn];

 ll c[maxn];

 int lowbit(int x)

 {

     return x&(-x);

 }

 void add(int x ,int d)

 {

     while(x<maxn)

     {

         c[x] += d;

         x += lowbit(x);

     }

 }

 ll sum(int x)

 {

     ll ret = ;

     while(x>)

     {

         ret += c[x];

         x -= lowbit(x);

     }

     return ret;

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

         scanf("%d",&a[i]);

         b[i] = a[i];

     }

     sort(b+,b+n+);

     int num = unique(b+,b+n+)-(b+);

     ll ans1 = , ans2 = ;

     ll mx = 1e18;

     for(int i=;i<=n;i++)

     {

         a[i] = lower_bound(b+,b+n+,a[i])-(b+);

         a[i]++;

         ans1 += (ll)(n-i+)*(sum(n)-sum(a[i]));

         if(ans1>=mx)  ans2 += ans1/mx, ans1%=mx;

         add(a[i],i);

     }

     if(ans2)  printf("%lld%018lld\n",ans2,ans1);

     else printf("%lld\n",ans1);

     return ;

 }