http://acm.hdu.edu.cn/showproblem.php?pid=2838&&逆シーケンスの応用
1385 ワード
これは比較的総合的な木状配列問題である.の
标题:ある農場主は乳牛をたくさん飼っていて、毎晩この農場主は乳牛のためにしなければならないが、どの乳牛にも気性があり、これは乳牛が農場主に牛を与える道具を壊す可能性がある.各乳牛の気性は等しくなく、このように農場主はある2つの牛の位置を交換することができ、乳牛が最も少ない道具を破壊することを求めることができる.2つの乳牛を動かすのにかかる時間は2つの乳牛の気性の和であることが知られている.最小限のツールを破壊する前提で最小限の時間を求めさせます.の
構想:ツリー配列には2つの要素があり、1つは現在のaより小さい数を記録し、1つは現在のaより小さい数を記録する和である.mintime=a*(i-Quary_cnt(a))+Quary_sum(n)-Quary_sum(a);
标题:ある農場主は乳牛をたくさん飼っていて、毎晩この農場主は乳牛のためにしなければならないが、どの乳牛にも気性があり、これは乳牛が農場主に牛を与える道具を壊す可能性がある.各乳牛の気性は等しくなく、このように農場主はある2つの牛の位置を交換することができ、乳牛が最も少ない道具を破壊することを求めることができる.2つの乳牛を動かすのにかかる時間は2つの乳牛の気性の和であることが知られている.最小限のツールを破壊する前提で最小限の時間を求めさせます.の
構想:ツリー配列には2つの要素があり、1つは現在のaより小さい数を記録し、1つは現在のaより小さい数を記録する和である.mintime=a*(i-Quary_cnt(a))+Quary_sum(n)-Quary_sum(a);
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#define M 100001
using namespace std;
typedef long long L;
int n;
typedef struct str
{ int cnt;
L sum;
}Node;
Node s[M];
inline int lowbit(int x)
{return x&(-x);}
void update(int x,int y)
{
while(x<=n)
{ s[x].sum+=y;
s[x].cnt++;
x+=lowbit(x);
}
}
L Quary_sum(int x)
{ L res=0;
while(x>0)
{ res+=s[x].sum;
x-=lowbit(x);
}
return res;
}
L Quary_cnt(int x)
{ L res=0;
while(x>0)
{ res+=s[x].cnt;
x-=lowbit(x);
}
return res;
}
int main()
{
while(~scanf("%d",&n))
{ memset(s,0,sizeof(s));
int a;
L s1=0;
for(int i=1;i<=n;++i)
{ scanf("%d",&a);
update(a,a);
L res=i-Quary_cnt(a);//
if(res!=0)
{ L k=Quary_sum(n)-Quary_sum(a);// a
s1+=(k+res*a);
}
}
printf("%I64d
",s1);
}return 0;
}