hdu4000 && hrbust1625
ikki的數字
Time Limit: 1000 MS
Memory Limit: 32768 K
Total Submit: 22(12 users)
Total Accepted: 9(8 users)
Rating:
Special Judge: No
Description
ikki 最近對數字頗感興趣。現在ikki在紙上寫了連續的N個數字，每個數字都是[1,N]之間任意的一個數而且不重復，即這串數字
是數字1~N的一個排列，數字的序號從1到N，現在ikki想考你一下：
在這N個數字中能找出多少個3個數的組合滿足:num[x]
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
隱藏著樹狀數組~~~根本沒看出來，其實主要是沒思路，思路出來了才能用樹狀數組求解
判斷滿足i
-
可以先求出（xyz，xzy)的總數量
-
只需出去x後面多少個比它大的個數n，C(n,2)就是了
-
然後求出xyz的個數，
-
對於a，求出比a小的個數low[a],比a大的個數high[a],low[a]*high[a]就是答案
-
可以借助樹狀數組求上述個數
注意了，整體求解！並不是說單獨考慮某個數
#include
#include
#include
using namespace std;
typedef long long LL;
const int mod = 100000007;
int T,n;
int c[5010];
int lowbit(int x)
{
return x & -x;
}
LL getsum(int x)
{
LL sum = 0;
while(x > 0)
{
sum += c[x];
x -= lowbit(x);
}
return sum;
}
void update(int x , int val)
{
while(x <= n)
{
c[x] += val;
x += lowbit(x);
}
}
int main()
{
#ifdef xxz
freopen("in.txt","r",stdin);
#endif // xxz
cin>>T;
int Case = 1;
while(T--)
{
memset(c,0,sizeof(c));
cin>>n;
LL ans = 0;
for(int i = 1; i <= n; i++)
{
int temp;
cin>>temp;
update(temp,1);
LL presmaller = getsum(temp - 1);
LL prebigger = i-1 - presmaller;
LL totbigger = n - temp;
LL afterbigger = totbigger - prebigger;
ans -= presmaller * afterbigger;
if(afterbigger >= 2)
{
ans += afterbigger*(afterbigger - 1)/2;
}
}
cout<<"Case #"<
