Skip to content

13039: 【原3039】count

题目

题目描述

author: cherry 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3039

Description

小s在数学课上新学习了一个名词,叫逆序对。对于长度为N的序列{a1,a2…an},一个逆序对(i,j)需要满足

(1) i<j

(2) ai>aj 这两个条件。不过普通的数逆序对小s已经可以闭着眼睛数出来了~ 现在老师又加大了难度,重新定义了一种高级版逆序对。首先定义了函数F(x)=(2x+1)*(2x+1),然后高级版逆序对(i,j)需要满足

(1) i<j

(2) F(ai)>aj

这两个条件。小s数高级版逆序对数得意识模糊,想让你来帮帮她。现在给你一个长度为N的数列,请你告诉小s这里面有多少高级版逆序对。

Input Format

第一行,一个整数N,表示数列长度。

第二行至第N+1行,每行一个整数。第i+1行的整数表示ai

Output Format

一行,一个整数,表示高级版逆序对的个数。

Sample Input

5
2
4
99
5
6

Sample Output

8

Sample Explain

共5个数。F(a1)=25,F(a2)=81,F(a3)=39601,F(a4)=121,F(a5)=169

则有(1,2)(1,4)(1,5)(2,4)(2,5)(3,4)(3,5)(4,5)共8个高级版逆序对

About Testdata

50% 1<=N<=1,000,0<=ai<1,000,000

    80% 1<=N<=100,000,0<=ai<1,000,000

    100% 1<=N<=100,000,0<=ai<10^51

Limits

Time limit: 1000ms, memory limit: 50000kb.

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!