## BestCoder Round #45 (2/4)

maksyuki 发表于 比赛 分类，标签:

# A.Dylans loves numbers

Problem Description

Who is Dylans?You can find his ID in UOJ and Codeforces. His another ID is s1451900 in BestCoder. And now today's problems are all about him.Dylans is given a number N.

He wants to find out how many groups of "1" in its Binary representation.

If there are some "0"（at least one）that are between two "1",
then we call these two "1" are not in a group,otherwise they are in a group.

Input

In the first line there is a number T.

T is the test number.

In the next T lines there is a number N.

0≤N≤1018,T≤1000

Output

For each test case,output an answer.

Sample Input

15

Sample Output

2

Source

BestCoder Round #45

# B.Dylans loves sequence

Problem Description

Dylans is given N numbers a[1]....a[N]

And there are Q questions.

Each question is like this (L,R)

his goal is to find the “inversions” from number L to number R.

more formally,his needs to find the numbers of pair（x,y）,
that L≤x,y≤R and x<y and a[x]>a[y]

Input

In the first line there is two numbers N and Q.

Then in the second line there are N numbers:a[1]..a[N]

In the next Q lines,there are two numbers L,R in each line.

N≤1000,Q≤100000,L≤R,1≤a[i]≤231−1

Output

For each query,print the numbers of "inversions”

Sample Input

3 23 2 11 21 3

Sample Output

13 Hint You shouldn't print any space in each end of the line in the hack data.

Source

BestCoder Round #45

if (a[j] > a[i]) dp[j][i] = dp[j+1][i] + 1; else dp[j][i] = dp[j+1][i];