首页 > 代码库 > hdu 5147 树状数组
hdu 5147 树状数组
题意：求满足a<b<c<d，A[a]<A[b]，A[c]<A[d]的所有四元组(a,b,c,d)的个数
看到逆序对顺序对之类的问题一开始想到了曾经用归并排序求逆序对，结果YY了半天无果而终。
其实用树状数组做也很方便。
比如对于序列1 3 2 4 5，设数组c：0 0 0 0 0
一开始读入1，add(a[1],1)，c：1 0 0 0 0
读入3，add(a[2],1)，c：1 0 1 0 0
这时sum(a[2])-1就是3前面比3小的数的个数。
下面同理，
读入2，add(a[3],1)，c：1 1 1 0 0
这时sum(a[3])-1就是2前面比2小的数的个数。
以此类推。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 int c[50010],f[50010],a[50010],g[50010]; 6 int n,T; 7 8 int lowbit(int x) 9 {10 return x&(-x);11 }12 13 int sum(int x)14 {15 int ret=0;16 while (x>0)17 {18 ret=ret+c[x];19 x=x-lowbit(x);20 }21 return ret;22 }23 24 void add(int x,int d)25 {26 while (x<=n)27 {28 c[x]=c[x]+d;29 x=x+lowbit(x);30 }31 }32 33 int main()34 {35 scanf("%d\n",&T);36 while (T--)37 {38 scanf("%d\n",&n);39 for (int i=1; i<=n; i++)40 scanf("%d\n",&a[i]);41 42 memset(c,0,sizeof(c));43 for(int i=1; i<=n; i++)44 {45 add(a[i],1);46 f[i]=sum(a[i])-1;47 }48 49 memset(c,0,sizeof(c));50 for(int i=n; i>=1; i--)51 {52 add(a[i],1);53 g[i]=n-i+1-sum(a[i]);54 }55 56 long long ans = 0;57 long long sum = 0;58 for(int i = 1; i <= n; i++)59 {60 ans += sum*g[i];61 sum += f[i];62 }63 printf("%lld\n",ans);64 }65 return 0;66 }
hdu 5147 树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。