[2020 우 객 알고리즘 경기 입문 과 9 교시 연습 문제] 코 도리 의 수열 이산 화 + 나무 모양 배열

제목 링크: 코 도리 의 수열
제목
n 이 있다× ( n + 1 ) 2 {\frac{n\times(n+1)}2} 2n×(n + 1) 키 구간 에서 각자 의 역순 대 개 수 를 구하 고 더 해서 출력 한다.
해제
먼저 우 리 는 한 단락 의 서열 중의 모든 역순 대 수 를 어떻게 구 하 는 지, 역순 대 수 를 구 하 는 지 살 펴 보 자. 우 리 는 앞의 i 개 수로 전환 할 수 있 고 a [i] 보다 큰 것 이 몇 개 있 는 지.우 리 는 통 정렬 처럼 길이 가 m a x (a i) {max (a i)} max (ai) 인 트 리 배열 을 유지 할 수 있 습 니 다. 먼저 트 리 배열 에 현재 a [i] 보다 몇 개의 숫자 가 있 는 지 통계 한 다음 에 a [i] 를 업데이트 하면 됩 니 다.
역순 대 수 를 어떻게 구 하 는 지 알 게 되 었 다. 이 문 제 는 우리 가 이미 반 을 해결 하 였 으 나, 나머지 반 의 난점 은 n 을 어떻게 구 하 느 냐 에 있다.× ( n + 1 ) 2 {\frac{n\times(n+1)}2} 2n×(n + 1) 개 구간 내의 역순 대 는 역순 대가 중복 계산 되 는 것 이 분명 하기 때문에 우 리 는 하나의 알고리즘 을 설계 하면 역순 대 개 수 를 통계 할 수 있 을 뿐만 아니 라 역순 대 구간 내 에 나타 난 횟수 도 통계 할 수 있 기 때문에 이 문 제 는 쉽게 풀 릴 수 있다.
우 리 는 배열 조합 을 통 해 매우 간단 한 규칙 을 발견 할 수 있다. 만약 (i, j) 이 역순 대 일 때 (i, j) 가 계 산 된 횟수 는 i * (n - j + 1) 이다. 우 리 는 이 역순 대 의 좌우 두 구간 이 각각 (1, i) 과 (j, n) 이 고 이 두 좌우 구간 의 길 이 는 i 와 (n - j + 1) 임 을 알 수 있다. 배열 조합 을 보면 알 수 있 듯 이 (i, j) 이 역순 대 는 계 산 된 횟수 는 i * (n - j + 1) 이다.(i 1, j), (i 2, j)..... (i x, j) {(i 1, j), (i 2, j), (i 2, j)... (i x, j)} (i1, j), (i2, j)... (ix, j) 가 역순 대 시 를 위해 정 답 에 기여 한 바 가 i 1 ∗ (n - j + 1) + i 2 ∗ (n - j + 1) +.... + i x ∗ (n - j + 1) = s u m (i) \8727m (i) ∗ (n - j + 2 ∗ (n - j + 1) +........ + i x ∗ (n - j + 1) = s - − j + 1) {i 1 * (n - j + 1) + i 2 * (n - j + 1) +... + i x * (n - j + 1) = sum (i) * (n - j + 1)}i1 ∗ (n - j + 1) + i2 ∗ (n - j + 1) +... + ix ∗ (n - j + 1) = sum (i) ∗ (n - j + 1), sum (i) 은 j 보다 큰 수의 아래 표 의 합 이다.
그래서 우 리 는 아래 표 시 된 a [i], 저 장 된 값 이 i 인 트 리 배열 을 유지 합 니 다. sum (n) - sum (a [i]) (a [i]) 을 계산 하여 i 의 아래 표 시 된 합 보다 큰 값 을 얻 을 수 있 습 니 다. 그러면 답 에 대한 공헌 은 (s u m (n) - s u m (a [i]) (n - i + 1) {(sum (n) - sum (n) - sum (a [i]) * (n - i + 1)} (n - i + 1) (n - i + 1) (n - i + 1)) (n - i + 1)} (n - i + 1))} (n - i + 1)} (n - i + 1)))))) (sum (n - i + 1)
조심해!!!이 문제 a [i] ≤ 1e9, 따라서 아래 표 시 된 a [i] 의 트 리 배열 을 직접 유지 할 수 없 으 며, 이산 화 를 진행 해 야 합 니 다.그리고 답 은 롱 롱 을 터 뜨 릴 수 있 습 니 다. 가 필요 합 니 다.int 128 저장.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
//extern "C"{void *__dso_handle=0;}
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair
#define pll pair
#define lowbit(x) x&-x

const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=1e6+10;
const int maxm=100+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);


inline void print(__int128 x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}

ll n,c[maxn];
ll a[maxn],b[maxn];
void add(int x,int num)
{
	if(x==0) return ;
	while(x<=n)
	{
		c[x]+=num;
		x+=lowbit(x);
	}
}

ll sum(int x)
{
	ll ans=0;
	while(x>0)
	{
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}

int main()
{
	scanf("%lld",&n);
	__int128 ans=0;
	for(int i=1;i<=n;i++)
	{ 
		scanf("%lld",&a[i]);
		b[i]=a[i];
	}
	sort(b+1, b+1+n);
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1, b+1+n, a[i])-b;
	for(int i=1;i<=n;i++)
	{
		ans+=(sum(n)-sum(a[i]))*(n-i+1);
		add(a[i],i);
	}
	print(ans);
}