首页 > 代码库 > hdu 5147 Sequence II

hdu 5147 Sequence II

2024-10-21 12:34:39   202人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=5147

 题意：问有多少个这样的四元组(a,b,c,d),满足条件是 1<=a<b<c<d; Aa<Ab; Ac<Ad;

思路：用树状数组求，从右向左求在这个数之前形成多少个逆序数对记录在r数组里面，然后在从左向右求出在输入这个数之前形成多少个逆序数对存在l数组里面，然后枚举b就行；

技术分享
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 50001 5 #define ll long long 6 using namespace std; 7  8 int t; 9 int n;10 int a[maxn];11 int c[maxn];12 ll l[maxn],r[maxn],sum[maxn];13 14 int lowbit(int x)15 {16     return x&-x;17 }18 19 void insert(int x,int v)20 {21     while(x<maxn)22     {23         c[x]+=v;24         x+=lowbit(x);25     }26 }27 28 ll getsum(int x)29 {30     ll ans=0;31     while(x>0)32     {33         ans+=c[x];34         x-=lowbit(x);35     }36     return ans;37 }38 39 int main()40 {41     scanf("%d",&t);42     while(t--)43     {44         memset(sum,0,sizeof(sum));45         memset(a,0,sizeof(a));46         scanf("%d",&n);47         for(int i=1; i<=n; i++)48         {49             scanf("%d",&a[i]);50         }51         memset(c,0,sizeof(c));52         sum[n+1]=0;53         for(int i=n; i>=1; i--)54         {55             r[i]=getsum(n)-getsum(a[i]);56             insert(a[i],1);57             sum[i]=sum[i+1]+r[i];58         }59         memset(c,0,sizeof(c));60         for(int i=1; i<=n; i++)61         {62             l[i]=getsum(a[i]-1);63             insert(a[i],1);64         }65         ll ans=0;66         for(int i=2; i<=n; i++)67         {68             ans+=(l[i]*sum[i+1]);69         }70         printf("%lld\n",ans);71     }72     return 0;73 }
View Code

 

hdu 5147 Sequence II


联系
我们