5347 ProblemD数列-トレーニングキットT 10 T 3
1552 ワード
問題D:数列-訓練セット問題T 10 T 3
時間制限:4 Secメモリ制限:128 MBコミット:40解決:4
タイトルの説明
数列(sequence.pas/c/cpp)
問題の説明
簡単な数列問題:長さnの数列を与えて、このような3つの要素ai,aj,akの個数を求めて、aiakを満たして、i入力データ
最初の行は整数n(n<=50000)である.
2行目のn個の整数ai(0<=ai<=32767).
出力データ
aiak(iサンプル入力
5 1 2 3 4 1
サンプル出力
6
経験の総括
この問題は、ダイナミックプランニングを使用する場合(LIS)のメソッドは、タイムアウトします.ここではツリー配列を使用します.入力データはai=0を許可しますので、0の処理に注意してください.左から右へ遍歴して、配列の中で要素の左側でその要素より小さい要素の個数を求めます.右から左へ遍歴して、配列の中で要素の右側でその要素より小さい要素の個数を求めます.それから、2つの配列の対応する要素を乗算して、疲れます.加えて,最終的に得られるのは,問題の要求を満たすシーケンスの個数である.
正しいコード
時間制限:4 Secメモリ制限:128 MBコミット:40解決:4
タイトルの説明
数列(sequence.pas/c/cpp)
問題の説明
簡単な数列問題:長さnの数列を与えて、このような3つの要素ai,aj,akの個数を求めて、ai
最初の行は整数n(n<=50000)である.
2行目のn個の整数ai(0<=ai<=32767).
出力データ
ai
5 1 2 3 4 1
サンプル出力
6
経験の総括
この問題は、ダイナミックプランニングを使用する場合(LIS)のメソッドは、タイムアウトします.ここではツリー配列を使用します.入力データはai=0を許可しますので、0の処理に注意してください.左から右へ遍歴して、配列の中で要素の左側でその要素より小さい要素の個数を求めます.右から左へ遍歴して、配列の中で要素の右側でその要素より小さい要素の個数を求めます.それから、2つの配列の対応する要素を乗算して、疲れます.加えて,最終的に得られるのは,問題の要求を満たすシーケンスの個数である.
正しいコード
#include
#include
using namespace std;
#define lowbit(i) ((i)&(-i))
const int maxn=50010;
int c[maxn],sum1[maxn],sum2[maxn],a[maxn];
void update(int x,int v)
{
if(x==0)
c[0]+=v;
else
for(int i=x;i0;i-=lowbit(i))
sum+=c[i];
return sum+c[0];
}
int main()
{
int n;
long long ans;
while(~scanf("%d",&n))
{
if(n==0)
break;
memset(c,0,sizeof(c));
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
update(a[i],1);
sum1[i]=getsum(a[i]-1);
}
memset(c,0,sizeof(c));
for(int i=n;i>=1;--i)
{
update(a[i],1);
sum2[i]=getsum(a[i]-1);
}
ans=0;
for(int i=1;i<=n;++i)
{
ans+=(sum1[i]*sum2[i]);
}
printf("%lld
",ans);
}
}