HDU 5147 Sequence II 树状数组水题

浏览数：27 / 时间：2015年06月08日

无聊咯，学某y，水一发

给你n个数的排列，A[1]到A[n]，统计多少四元组(a,b,c,d)满足，1<=a<b<c<d<=n，且A[a]<A[b]，A[c]<A[d]

树状数组统计前缀和咯

技术分享 
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cctype>
 4 typedef long long ll;
 5 const int maxn=5e4+10;
 6 int T,n,a[maxn],c[maxn],l[maxn],r;
 7 ll ans;
 8 inline void modify(int x){while (x<=n) c[x]++,x+=x&-x;}
 9 inline int sum(int x)
10 {
11     int ret=0;
12     while (x>0) ret+=c[x],x-=x&-x;
13     return ret;
14 }
15 inline void read(int &x)
16 {
17     char ch;x=0;
18     while (!isdigit(ch=getchar()));
19     do x=x*10+ch-‘0‘;
20     while (isdigit(ch=getchar()));
21 }
22 int main()
23 {
24     read(T);
25     while (T--)
26     {
27         read(n);
28         for (int i=1;i<=n;i++) read(a[i]);
29         memset(c,0,sizeof(int)*(n+1));
30         for (int i=1;i<=n;i++)
31         {
32             l[i]=sum(a[i]);
33             modify(a[i]);
34         }
35         memset(c,0,sizeof(int)*(n+1));ans=r=0;
36         for (int i=n;i>=1;i--)
37         {
38             ans+=(ll)l[i]*r;
39             r+=sum(n-a[i]+1);
40             modify(n-a[i]+1);
41         }
42         printf("%I64d\n",ans);
43     }
44     return 0;
45 }
View Code

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢