洛谷P 1637三元上昇サブシーケンス(樹状配列)
3617 ワード
トリプルアップサブシーケンス
タイトルの説明
Erwinは最近「thair」というものに興味を持っています...
n個の整数を含むシーケンスa 1,a 2......anにおいて、
3つの数は「thair」と呼ばれ、i1つのシーケンスの中の“thair”の個数を求めます.
にゅうしゅつりょくけいしき
入力フォーマット:正の整数nを開始し、
以降n個数a 1~an.
出力形式:「thair」の個数
入出力サンプル
Input 4 2 1 3 4 Output 2 Input 5 1 2 2 3 4 Output 7のサンプル2に対する説明:7個の「thair」はそれぞれ1 2 3 1 2 4 1 2 2 3 1 2 4 4 3 4 4 4 4 4
説明
約30%のデータn<=100
60%のデータn<=2000
100%のデータn<=30000
ビッグデータランダム生成
0<=a[i]<=maxlongint
解析:i番目の数の前の小さい数と後ろの大きい数をツリー配列で統計し、最後に乗じて合計すればよい.
コード#コード#
タイトルの説明
Erwinは最近「thair」というものに興味を持っています...
n個の整数を含むシーケンスa 1,a 2......anにおいて、
3つの数は「thair」と呼ばれ、i
にゅうしゅつりょくけいしき
入力フォーマット:正の整数nを開始し、
以降n個数a 1~an.
出力形式:「thair」の個数
入出力サンプル
Input 4 2 1 3 4 Output 2 Input 5 1 2 2 3 4 Output 7のサンプル2に対する説明:7個の「thair」はそれぞれ1 2 3 1 2 4 1 2 2 3 1 2 4 4 3 4 4 4 4 4
説明
約30%のデータn<=100
60%のデータn<=2000
100%のデータn<=30000
ビッグデータランダム生成
0<=a[i]<=maxlongint
解析:i番目の数の前の小さい数と後ろの大きい数をツリー配列で統計し、最後に乗じて合計すればよい.
コード#コード#
#include 0;
while (x>0)
{
s+=c[x];
x-=x&(-x);
}
return s;
}
void change1(int x)
{
while (x<=n)
{
c[x]++;
x+=x&(-x);
}
}
ll sum2(ll x)
{
ll s=0;
while (x<=n)
{
s+=c[x];
x+=x&(-x);
}
return s;
}
void change2(int x)
{
while (x>0)
{
c[x]++;
x-=x&(-x);
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&p[i].a);
p[i].b=i;
}
sort(p,p+n+1,so);
for (int i=1;i<=n;i++)
{
a1[p[i].b]=sum1(p[i].b);
change1(p[i].b);
}
memset(c,0,sizeof c);
for (int i=n;i>=1;i--)
{
a2[p[i].b]=sum2(p[i].b);
change2(p[i].b);
}
for (int i=1;i<=n;i++)
ans+=a1[i]*a2[i];
printf("%lld
",ans);
}