首页 > 代码库 > hdu 5147 Sequence II (树状数组 求逆序数)
hdu 5147 Sequence II (树状数组 求逆序数)
题目链接
Sequence II
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 331 Accepted Submission(s): 151
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. 1≤a<b<c<d≤n
2. Aa<Ab
3. Ac<Ad
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 integers A1,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 A1,A2,…,An.
[Technical Specification]
1 <= T <= 100
1 <= n <= 50000
1 <= Ai <= n
Output
For each case output one line contains a integer,the number of quad.
Sample Input
151 3 2 4 5
Sample Output
4
题意：
很久很久以前，有一个长度为n的数列A，数列中的每个数都不小于1且不大于n，且数列中不存在两个相同的数.请统计有多少四元组(a,b,c,d)满足：1. 1≤a<b<c<d≤n2. Aa<Ab3. Ac<Ad
分析：
我的做法是把四元组分解成二元组来处理，分解的方法就是枚举把数组依次分为两部分，然后对每部分都用树状数组求逆序数，结果相乘就是满足条件的四元组的个数。
树状数组求逆序数的做法是，因为知道数列里的数是1-n，所以可以 以个数为c[]数组的元素，值为下标，通过求和来 求大于当前数 或者 小于当前数的个数
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <vector> 7 #include <algorithm> 8 #define LL __int64 9 const int maxn = 1e5 + 10;10 using namespace std;11 LL a[maxn], c[maxn], n, f[maxn];12 13 int lowbit(int x)14 {15 return x&(-x);16 }17 void add(int x,int d)18 {19 while(x <= n)20 {21 c[x] += d;22 x +=lowbit(x);23 }24 }25 LL sum(int x)26 {27 LL ret = 0;28 while(x > 0)29 {30 ret += c[x];31 x -= lowbit(x);32 }33 return ret;34 }35 36 int main()37 {38 int t;39 LL i, ans, tmp;40 scanf("%d", &t);41 while(t--)42 {43 ans = 0;44 scanf("%I64d", &n);45 46 memset(f, 0, sizeof(f));47 memset(c, 0, sizeof(c));48 for(i = 1; i <= n; i++)49 {50 scanf("%I64d", &a[i]);51 add(a[i], 1);52 f[i] = f[i-1] + sum(a[i]-1);53 }54 55 memset(c, 0, sizeof(c));56 tmp = 0;57 for(i = n; i >= 1; i--)58 {59 tmp = sum(n) - sum(a[i]);60 add(a[i], 1);61 ans += tmp*f[i-1];62 }63 printf("%I64d\n", ans);64 }65 return 0;66 }
hdu 5147 Sequence II (树状数组 求逆序数)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。