LA 4329 BIT 分治

#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define lowbit(x) x&-x

using namespace std;

int c[100010],a[20010],n,T,l[20010];

int sum(int x)
{
    int ret=0;
    while(x>0)
    {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}

void add(int x,int d)
{
    while(x<=100000)
    {
        c[x]+=d;
        x+=lowbit(x);
    }
}

int main()
{
    //freopen("/home/user/in","r",stdin);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        memset(c,0,sizeof(c));
        long long s=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            add(a[i],1);
        //    printf("%d
",c[i]);
            l[i]=sum(a[i]-1);//l[i]表示a[i]前面比a[i]小的数的个数
        }
        //for(int i=0;i<n;i++)
        //    printf("a[%d]=%d %d %d
",i,a[i],l[i],sum(a[i]));
        for(int i=0;i<n;i++)
        {
            int al=sum(a[i]-1);//al表示整个a数组中比a[i]小德数的个数
            s+=l[i]*(n-i-1-al+l[i])+(i-l[i])*(al-l[i]);
        }
        printf("%lld
",s);
    }
    return 0;
}

View Code

用BIT做的

 1 #include <cstdio>
 2 #include <queue>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <cstdlib>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <map>
 9 #include <set>
10 
11 using namespace std;
12 
13 struct Node
14 {
15     int i,x;
16     bool operator<(Node &a)const
17     {
18         return x<a.x;
19     }
20 };
21 
22 Node a[20010],t[20010];
23 int c[20010],n,T;
24 
25 void merge_sort(int l,int r)
26 { 
27     if(r-l>1)
28      { 
29         int m=l+(r-l)/2;
30         int p=l,q=m,i=l;
31         merge_sort(l,m);
32         merge_sort(m,r);
33         while(p<m||q<r)
34         {
35             if(q>=r||(p<m&&a[p]<a[q])) memcpy(&t[i++],&a[p++],sizeof(a[0]));
36             else
37             {
38                 memcpy(&t[i],&a[q],sizeof(a[0]));
39                 c[a[q].i]+=m-p;//c[i]记录在i前面的比i大的个数
40                 i++;q++;
41             }
42         }
43         for(int i=l;i<r;i++) memcpy(&a[i],&t[i],sizeof(a[0]));
44     }
45 }
46 
47 int main()
48 {
49     //freopen("/home/user/in","r",stdin);
50     int T;
51     scanf("%d",&T);
52     while(T--)
53     {
54         scanf("%d",&n);
55         for(int i=0;i<n;i++)
56         {
57             a[i].i=i;
58             scanf("%d",&a[i].x);
59         }
60         memset(c,0,sizeof(c[0])*(n+1));
61         merge_sort(0,n);
62         long long sum=0;
63         //for(int i=0;i<n;i++) printf("a[%d]=%d %d %d
",i,a[i].x,c[a[i].i],a[i].i-c[a[i].i]);
64         for(int i=0;i<n;i++)
65             sum+=c[a[i].i]*(i-a[i].i+c[a[i].i])+(a[i].i-c[a[i].i])*(n-i-1-c[a[i].i]);
66         printf("%lld
",sum); }
67     return 0;
68 }

View Code

用分治法求逆序对的方法做的