Nowcoder 7. E 코 도리 의 수열 역순 수, BIT
역순 수 (ia [j] 는 (i, j) 는 역순 수 쌍) 이다. n < = 1e6, a [i] < = 1e9.
아시아 [j] (i, j) 이 커 플 에 i * (n - j + 1) 번 이 나 타 났 습 니 다. 공헌 한 셈 입 니 다.
한 쌍 은 n ^ 2 쌍 이 라 고 할 수 있 습 니 다. 그러면 뒤에서 왼쪽 끝 점 i 를 들 어 BIT 로 [i + 1, n] a [i] 보다 작은 가중치 면 a [i] > a [j] 는 n - j + 1 을 누적 합 니 다.
정 답 은 ll 입 니 다. 여 기 는 를 사 용 했 습 니 다.int128
#include
using namespace std;
typedef __int128 ll;
const int N=1e6+5;
int n,a[N];
ll c[N*2];
vector b;
int getid(int x)
{
return lower_bound(b.begin(),b.end(),x)-b.begin()+1;
}
int lowbit(int x)
{
return x&-x;
}
void update(int x,ll val)
{
for(int i=x;i<=n;i+=lowbit(i))
c[i]+=val;
}
ll query(int x)
{
ll res=0;
for(int i=x;i>0;i-=lowbit(i))
res+=c[i];
return res;
}
vector aa;
void output(__int128 v){
if(v==0)puts("0");
else{
while(v){
aa.push_back(v%10);
v/=10;
}
reverse(aa.begin(),aa.end());
for(auto it:aa)printf("%d",it);puts("");
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),b.push_back(a[i]);
sort(b.begin(),b.end());
b.erase(unique(b.begin(),b.end()),b.end());
ll ans=0;
for(ll i=n;i>=1;i--)
{
int pos=getid(a[i]);
ll sj=query(pos-1);
ans+=i*sj;
update(pos,n-i+1);
}
output(ans);
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
