codeforces 540 E. Infinite Inversions (分类思想+线段树求逆序对)

题目链接

题意:一个无穷数列,从1开始,初始第i个位置上为i,给出n个swap,每次交换两个位置的数。问交换n次以后得到的数列中,逆序对的数。

思路:

官方题解:

At first find the position of each element which is used in swap (using map). Now let’s find the answer. It consists of the two parts. First part is the number of inversions formed by only whose elements which took part in the swaps. They can be counted by one of the standard ways: mergesort or Fenwick tree. The second part is the number of inversions formed by pairs of elements where one element has been swapped even once, and the other element stayed at his position. Let’s consider the following test:

2

2 6

4 8

The global sequence will look as follows: [1 6 3 8 5 2 7 4 9 …], and here is the array of swapped elements: [6 8 2 4].

Let’s understand with which numbers the number 8 forms the inversions. The only elements that could do that are the elements between the initial position of the number 8 (where the number 4 is now) and its current position: [5 2 7]. There are two numbers on this segment which didn’t take part in swaps: 5 and 7. The number 2 should not be counted as it took part in the swaps and we have already counted it in the first part of the solution.

So we should take the count of numbers between 8’s indices in the global sequence (8 - 4 - 1 = 3) and subtract the count of numbers between its indices in the swaps array (4 - 2 - 1 = 1)(在交换序列中【6,8,2,4】4的位置在4,8的位置在2). We’ll get the number of inversions formed by the element 8 and the elements which haven’t moved at all, it’s 2. Counting this value for all elements which have been swapped at least once, we get the second part of the answer. All operations in the second part of the solution can be performed using sorts and binary searches.

 

讲真。。。题解写的真是不友好。。。。很多概念从天而降。。。公式中magic number不加说明。。。。差评。

我来说一下这道题的做法:

首先,由于交换的位置最大1E9,但是最多1E5个交换。。所以自然而然想到离散化。

需要注意的是,离散化后最多有2E5个,而不是1E5 (因此re #7

对于统计最后的逆序对数,我们分为两部分。

首先我们知道,对于两个没有被交换过的数,肯定不是一对逆序对。

因此答案分为,两个数都是被交换过的数产生的逆序对数 和 交换过的数和没被交换过的数之间产生的逆序对数。

First part is the number of inversions formed by only whose elements which took part in the swaps. They can be counted by one of the standard ways: mergesort or Fenwick tree. The second part is the number of inversions formed by pairs of elements where one element has been swapped even once, and the other element stayed at his position. Let’s consider the following test:

对于前者。。。。

就是普通的逆序对。。。直接BIT处理(故意写成线段树真是不美丽)

对于后者。。。我们的做法是。。。

处理两个数组。。。f[i]和p[i]

f[i]表示交换序列中,离散化后,处于第i个位置上面的值(也是离散化之前的位置)

p[i]表示现在在i位置上的数初始是在p[i]位置(位置是离散化后的从小到大的顺序,因此是对于交换序列的(因为只有交换序列才离散化了))

对于处于交换序列中的某个数,其初始位置和最终位置之间有多少个数,答案为:abs(f[p[i]]-f[i])-1

但是这两个位置之间,处于交换序列中的数在之前的第一部分已经算过了(也就是两个数都是被交换过的数)

所以我们需要减去 两个位置之间,已经处于交换序列的个数(不包含两个位置)

结果为abs(i-p[i])-1 (交换序列中 i和p[i]位置之间,有abs(i-p[i])-1个数)

两部分相间,答案为res = abs(f[p[i]-f[i]]-1 – (ans(i-p[i])-1) = abs(f[p[i]]-f[i]) – abs(i-p[i])

把每个处于交换序列中的数的res累加,就是最后的结果。

注意要开LL.

 

 

 

 

 

codeforces 220 E. Little Elephant and Inversions (树状数组+尺取)

题目链接

题意:

how many pairs of integers l and r are there, such that 1 ≤ l < rn and sequence b = a1a2alarar + 1an has no more than k inversions.

我花了两个小时才看懂题。。。。一直没懂b数列中a[l]和a[r]怎么就挨着了。。。

其实意思是。。。只保留a数列中1..l和r..n的。。。构成b数列。。。然后b数列的逆序对数小于等于k.问这样的l,r的对数。

思路:尺取+树状数组。

枚举l,每次找到最小的满足题意的r,对答案的贡献是n-r+1,然后用两个树状数组,分别维护增加或者减少一个树的时候,前半段和后半段对逆序数的影响。

 

 

codeforces 61 E. Enemy is weak (离散化+线段树求逆序三元组)

题目链接
题意:给出n个数,求满足 i<j<k且a[i]>a[j]>a[k]的三元组有多少个。

思路:对于这种要求三个数满足条件的题目,老司机的经验是考虑中间那个数,这道题也不例外。

我们枚举j,通过求两次逆序对求出对于每个a[j],满足a[i]>a[j]的i的个数,以及满足a[j]>a[k]的个数。

两个个数的乘积就是j作为中间数满足的三元组的个数,这样把所有的j累加就是答案。

其他的就是,要离散化,以及最后答案可能会爆long long?

1A,好爽啊哈哈哈。

 

 

codeforces 459 D. Pashmak and Parmida’s problem (离散化+线段树求逆序对数)

题目链接
题意:定义f(l, r, x)为区间[l,r]中x出现的次数。现在要求calculate the number of pairs of indicies i, j (1 ≤ i < jn) such thatf(1, i, ai) > f(j, n, aj).

思路:可以通过o(n)预处理出f(1,i,a[i])和f[j,n,a[j]],其实预处理的过程就是离散化的过程呢。。。

分别得到

1 1 2 3 2 3 4

4 3 3 2 2 1 1

所以答案其实就是第一组数在第二组数中找逆序数的过程。。。

我们不妨倒序处理。

需要注意的是,线段树维护的区间是0..mx,我整体增加了1.

线段树求逆序对和树状数组求逆序对是同样的思想。。。注意体会。。

 

 

hdu 1394 Minimum Inversion Number (树状数组 逆序对)

题目链接

题意:
这题是问一个长度为n的循环数组中,逆序对最少的个数。。。
我们可以先用树状数组求出初始的数列的逆序对。。。
然后其他的可以通过递推得到。。。。
当a[i]从处于位置1而被放到最后的时候。。。
cnt = cnt -a[i]+n-a[i]+1;
然后取所有cnt的最大值就行。