hrbust 1625 哈理工oj ikki的数字【树状数组】

ikki的数字

Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 29(16 users) Total Accepted: 13(12 users) Rating:  Special Judge: No

Description

ikki 最近对数字颇感兴趣。现在ikki在纸上写了连续的N个数字，每个数字都是[1,N]之间任意的一个数而且不重复，即这串数字 是数字1~N的一个排列，数字的序号从1到N，现在ikki想考你一下： 在这N个数字中能找出多少个3个数的组合满足:num[x]<num[z]<num[y]且x<y<z,其中x,y,z为这三个数字的下标。

Input

多组测试数据，第一行一个整数T 表示测试数据的个数。 对于每组数据，第一行输入一个整数N表示数列中数字的个数（1<=N<=5000） 第二行输入N个数字表示一个1~N的排列。

Output

对于每组数据，输出”Case #k: p” ,k表示第k组样例，p表示满足要求的3个数字的组合数目，每组输出占一行。 由于结果可能比较大，结果需对100000007取模。

Sample Input

2 6 1 3 2 6 5 4 5  3 5 2 4 1

Sample Output

Case #1: 10 Case #2: 1

Author

周洲@hrbust

按照题目要求来找到三元组。

思路：

我们直接举例说明：
对于样例1：

1 3 2 6 5 4

i==1时，位子小于i的比a【i】小的数据量为：0，位子大于i的比a【i】大的数据量为：5，我们在位子大于i比a【i】大的数据中随机挑出两个组成三元组：
（1 3 2）（1 3 6）（1 3 5）（1 3 4）（1 2 6）（1 2 5）（1 2 4）（1 6 5）（1 6 4）（1 5 4）这时候不要急，我们之后会去掉不合法的情况

然后我们去掉以i为中间值不合法的情况：0*5=0；

i==2时，位子小于i的比a【i】小的数据量为：1，位子大于i的比a【i】大的数据量为：3，我们在位子大于i比a【i】大的数据中随机挑出两个组成三元组：

（3 6 5）（3 6 4）（3 5 4）

然后我们去掉以i为中间值不合法的情况：1*3：

（1 3 6）（1 3 5）（1 3 4）

i==3时，位子小于i的比a【i】小的数据量为：1，位子大于i的比a【i】大的数据量为：3，我们在位子大于i比a【i】大的数据中随机挑出两个组成三元组：

................................省略

i==4时，位子小于i的比a【i】小的数据量为：3，位子大于i的比a【i】大的数据量为：0，我们在位子大于i比a【i】大的数据中随机挑出两个组成三元组：

.................................同省略

i==5时，位子小于i的比a【i】小的数据量为：3，位子大于i的比a【i】大的数据量为：0....................

i==6时，位子小于i的比a【i】小的数据量为：3，位子大于i的比a【i】大的数据量为：0....................

按照这种方式来求得最终的三元组数一共有：10个。

题目保证了数据一定是从1~N的情况，所以我们不需要离散化，而且利用树状数组求出比a【i】小的数据是很容易的事，那么求出在a【i】后边比a【i】大的数据也很容易了。

AC代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define mod 100000007
int n;
int a[5005];
int tree[100005];//树
int lowbit(int x)//lowbit
{return x&(-x);
}
int sum(int x)
{int sum=0;while(x>0){sum+=tree[x];x-=lowbit(x);}return sum;
}
void add(int x,int c)//加数据。
{while(x<=n){tree[x]+=c;x+=lowbit(x);}
}
int main()
{int kase=0;int t;scanf("%d",&t);while(t--){memset(tree,0,sizeof(tree));scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}int output=0;for(int i=1;i<=n;i++){int x=sum(a[i]);//求出在i之前比a[i]小的数据量个数add(a[i],1);int houda=n-a[i]-i+x+1;//推导出在i之后比a[i]大的数据量个数。output+=houda*(houda-1)/2;output-=x*houda;}printf("Case #%d: %d\n",++kase,output%mod);}
}