首页 > 代码库 > hdu 5147 树状数组
hdu 5147 树状数组
http://acm.hdu.edu.cn/showproblem.php?pid=5147
Problem Description
Long long ago, there is a sequence A with length n. All numbers in this sequence is no smaller than 1 and no bigger than n, and all numbers are different in this sequence.
Please calculate how many quad (a,b,c,d) satisfy:
1.1≤a<b<c<d≤n
2.Aa<Ab
3.Ac<Ad
Please calculate how many quad (a,b,c,d) satisfy:
1.
2.
3.
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case begins with a line contains an integer n.
The next line follows n integersA1,A2,…,An .
[Technical Specification]
1 <= T <= 100
1 <= n <= 50000
1 <=Ai <= n
Each test case begins with a line contains an integer n.
The next line follows n integers
[Technical Specification]
1 <= T <= 100
1 <= n <= 50000
1 <=
Output
For each case output one line contains a integer,the number of quad.
Sample Input
1 5 1 3 2 4 5
Sample Output
4
/** hdu5147 树状数组 解题思路: 要统计四元组的数量我们可以通过枚举c,然后统计区间[1,c-1]有多少二元组(a,b)满足a<b且Aa<Ab,以及统计出区间[c+1,n]有多少d满足Ac<Ad, 根据乘法原理,把这两项乘起来就可以统计到答案里了.然后我们来处理子问题:区间[1,c-1]内有多少二元组(a,b).那么我们可以枚举b,然后统计 区间[1,b-1]内有多少a满足Aa<Ab,那么这个可以通过用树状数组询问前缀和来实现. 具体实现:b[i]和c[i]中存储的分别为以i结尾的Ax<Ay的对数和从i+1到n中Ax<Ay的对数,二者相乘即为答案。 时间复杂度是O(nlogn). */ #include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> using namespace std; typedef long long LL; int C[100005],b[100005],c[100005],a[100005]; int n; int lowbit(int x) { return x&(-x); } 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<=n) { C[x]+=d; x+=lowbit(x); } } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) scanf("%d",&a[i]); memset(C,0,sizeof(C)); for(int i=1;i<=n;i++) { b[i]=sum(a[i]); add(a[i],1); } memset(C,0,sizeof(C)); for(int i=n;i>=1;i--) { c[i]=sum(n)-sum(a[i])+c[i+1]; add(a[i],1); } LL ans=0; for(int i=2;i<=n-2;i++) { LL t1=b[i]; LL t2=c[i+1]; ans+=t1*t2; } printf("%I64d\n",ans); } return 0; }
hdu 5147 树状数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。